Una tabla hash como contador en C#

Problema

Los productos más vendidos del día

El panel de la tienda muestra los tres productos más vendidos del día. El registro es una lista de pedidos, uno por línea. El código mantiene dos listas, los nombres y los contadores, y para cada pedido busca el producto desde el principio de los nombres:

var log = LogOf(1000);
var names = new List<string>();
var counts = new List<int>();
long comparisons = 0;
foreach (var item in log)
{
    int i = 0;
    while (i < names.Count)
    {
        comparisons++;
        if (names[i] == item) break;
        i++;
    }
    if (i == names.Count)
    {
        names.Add(item);
        counts.Add(1);
    }
    else
    {
        counts[i]++;
    }
}
Console.WriteLine($"pedidos: {log.Count}");
Console.WriteLine($"productos: {names.Count}");
Console.WriteLine($"comparaciones: {comparisons}");

pedidos: 1000
productos: 251
comparaciones: 125255

Mil pedidos y 251 productos distintos: 125 255 comparaciones. El catálogo crece con la tienda, y con él la lista que recorre cada pedido. En un día grande con 100 000 pedidos el panel tarda minutos en cargar.

De dónde viene el registro

El registro sigue una fórmula, para que los programas en los cuatro lenguajes y la comparación del navegador de más abajo construyan exactamente el mismo. El catálogo tiene n / 4 + 1 productos:

static List<string> LogOf(int n)
{
    int catalog = n / 4 + 1;
    var log = new List<string>();
    for (int i = 0; i < n; i++)
    {
        log.Add($"SKU-{(i * 7919) % catalog}");
    }
    return log;
}

La idea

El mapa cuenta

En la lección «Dictionary y HashSet» contaste pedidos con un mapa. Aquí se convierte en una técnica: una tabla hash como contador (un mapa de frecuencias). La clave es lo que cuentas, el valor es cuántas veces lo has visto.

Una pasada por los datos. Para cada elemento: encontrar su contador (o 0) y sumar 1.
La búsqueda se hace en una tabla hash: O(1) en promedio, sean cuales sean los productos. En total O(n) en lugar de O(n · m).
Después respondes las preguntas con los contadores, no con los datos: cuál es el más frecuente, cuál aparece una vez, si dos cosas tienen los mismos contadores.

La memoria es O(m): un par por cada producto distinto.

Míralo

El contador se llena

List<string> log = [
    "ratón", "audífonos", "ratón", "monitor",
    "teclado", "ratón", "audífonos", "monitor",
    "ratón", "audífonos"
];
var counts = new Dictionary<string, int>();
foreach (var item in log)
{
    counts[item] = counts.GetValueOrDefault(item) + 1;
}
var top = counts.OrderByDescending(e => e.Value).Take(3);
foreach (var (item, n) in top)
{
    Console.WriteLine($"{item} {n}");
}

ratón 4
audífonos 3
monitor 2

var counts = new Dictionary<string, int>();
foreach (var item in log)
{
    counts[item] = counts.GetValueOrDefault(item) + 1;
}
var top = counts.OrderByDescending(e => e.Value).Take(3);
foreach (var (item, n) in top)
{
    Console.WriteLine($"{item} {n}");
}

Paso a paso, en palabras

Un mapa vacío: producto → cuántas veces se vendió. El registro tiene 10 pedidos.
Pedido 1: ratón. Todavía no está en el mapa, así que recibe un contador de 1.
Pedido 2: audífonos. Todavía no está en el mapa, así que recibe un contador de 1.
Pedido 3: ratón, 1 → 2. Una búsqueda en la tabla hash, sin recorrer los demás productos.
Pedido 4: monitor. Todavía no está en el mapa, así que recibe un contador de 1.
Pedido 5: teclado. Todavía no está en el mapa, así que recibe un contador de 1.
Pedido 6: ratón, 2 → 3. Una búsqueda en la tabla hash, sin recorrer los demás productos.
Pedido 7: audífonos, 1 → 2. Una búsqueda en la tabla hash, sin recorrer los demás productos.
Pedido 8: monitor, 1 → 2. Una búsqueda en la tabla hash, sin recorrer los demás productos.
Pedido 9: ratón, 3 → 4. Una búsqueda en la tabla hash, sin recorrer los demás productos.
Pedido 10: audífonos, 2 → 3. Una búsqueda en la tabla hash, sin recorrer los demás productos.
10 pedidos, 10 actualizaciones del contador. Se ordenan solo los 4 productos distintos por contador, no los pedidos.
Los tres primeros: ratón 4, audífonos 3, monitor 2.

GetValueOrDefault(item) devuelve 0 para un producto que todavía no está, así que el primer pedido da 1. Los tres primeros salen de ordenar los pares por contador: se ordenan solo los productos distintos, no los pedidos.

Pruébalo

Completa

La línea que cuenta:

counts[item] = counts.(item) + 1;

GetValueOrDefault devuelve el valor, o 0 para una clave que no está.

Míralo

Las herramientas de tu lenguaje

En C# el contador es un Dictionary<string, int>. TryGetValue lee sin excepción cuando falta la clave. counts[item] = counts.GetValueOrDefault(item) + 1 busca la clave dos veces: una para leer, otra para escribir. CollectionsMarshal.GetValueRefOrAddDefault da una referencia (ref) al valor dentro de la tabla, y lo aumentas en el sitio con una sola búsqueda. Desde .NET 9 LINQ también trae un conteo ya hecho, CountBy, en el orden de la primera aparición:

List<string> log = [
    "ratón", "audífonos", "ratón", "monitor",
    "teclado", "ratón", "audífonos", "monitor",
    "ratón", "audífonos"
];
var counts = new Dictionary<string, int>();
foreach (var item in log)
{
    ref int slot = ref CollectionsMarshal.GetValueRefOrAddDefault(counts, item, out _);
    slot++;
}
Console.WriteLine($"{counts["ratón"]} {(counts.TryGetValue("tableta", out int t) ? t : 0)}");
foreach (var (item, n) in log.CountBy(x => x))
{
    Console.WriteLine($"{item} {n}");
}

4 0
ratón 4
audífonos 3
monitor 2
teclado 1

Míralo

Mídelo: una lista de pares frente a un mapa

Los mismos mil pedidos con el mapa:

var log = LogOf(1000);
var counts = new Dictionary<string, int>();
long updates = 0;
foreach (var item in log)
{
    counts[item] = counts.GetValueOrDefault(item) + 1;
    updates++;
}
Console.WriteLine($"pedidos: {log.Count}");
Console.WriteLine($"productos: {counts.Count}");
Console.WriteLine($"actualizaciones del contador: {updates}");

pedidos: 1000
productos: 251
actualizaciones del contador: 1000

1000 actualizaciones en lugar de 125 255 comparaciones. Ejecuta las dos en el navegador. n es el número de pedidos, y el catálogo crece con él:

Una lista de pares de producto y cantidad O(n²)
Un mapa como contador O(n)

Algoritmo	n = 10	n = 1000	n = 100.000
Una lista de pares de producto y cantidad	16	125.255	≈ 1.252.550.000
Un mapa como contador	10	1000	100.000

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

var counts = new Dictionary<string, int>();
foreach (var item in log)
{
    counts[item] = counts.GetValueOrDefault(item) + 1;
}
var top = counts.OrderByDescending(e => e.Value).Take(3);
foreach (var (item, n) in top)
{
    Console.WriteLine($"{item} {n}");
}

Más precisamente, para curiosos

Los k primeros sin ordenarlo todo. Ordenar m productos distintos es O(m log m). Si hay millones de productos y necesitas los 10 primeros, mantienes un heap con como máximo k pares: cada par entra, y cuando hay k + 1 sale el más pequeño. Eso es O(m log k).

Una clave con varias partes. Cuentas ventas por ciudad y producto: la clave es el par. En C# es una tupla (city, item) o un record: ambos tienen Equals y GetHashCode sobre sus campos.

La idea

El carrito y el kit

El kit «oficina en casa» es un monitor, un teclado, un ratón y dos cables. El almacén comprueba que el carrito que se va a enviar es exactamente el kit: nada de más, nada de menos. El orden no importa, los contadores sí.

Un contador: +1 por cada producto del kit, −1 por cada producto del carrito. El carrito coincide si todos los contadores terminan en 0.

static bool Matches(List<string> kit, List<string> basket)
{
    var need = new Dictionary<string, int>();
    foreach (var item in kit) need[item] = need.GetValueOrDefault(item) + 1;
    foreach (var item in basket) need[item] = need.GetValueOrDefault(item) - 1;
    return need.Values.All(n => n == 0);
}

La misma comprobación encuentra anagramas: «listen» y «silent» tienen las mismas letras con los mismos contadores. El contador es sobre letras en lugar de productos.

Pruébalo

Predice la comprobación

List<string> kit = [
    "monitor", "teclado", "ratón", "cable",
    "cable"
];
List<string> basket1 = [
    "cable", "ratón", "monitor", "cable",
    "teclado"
];
List<string> basket2 = [
    "monitor", "teclado", "ratón", "ratón",
    "cable"
];
Console.WriteLine($"carrito 1: {(Matches(kit, basket1) ? "kit completo" : "no coincide")}");
Console.WriteLine($"carrito 2: {(Matches(kit, basket2) ? "kit completo" : "no coincide")}");

Respuesta

carrito 1: kit completo
carrito 2: kit completo

carrito 1: no coincide
carrito 2: kit completo

carrito 1: kit completo
carrito 2: no coincide

La idea

El primer cliente con un solo pedido

Marketing envía un vale de «vuelve» a los clientes que pidieron una sola vez. Quiere al primero en el tiempo. El contador da los contadores, pero no el orden:

static string? FirstSingle(List<string> customers)
{
    var counts = new Dictionary<string, int>();
    foreach (var c in customers) counts[c] = counts.GetValueOrDefault(c) + 1;
    foreach (var c in customers)
    {
        if (counts[c] == 1) return c;
    }
    return null;
}

List<string> customers = [
    "C-17", "C-4", "C-17", "C-9",
    "C-4", "C-21", "C-9", "C-30"
];
Console.WriteLine($"primer cliente con un solo pedido: {FirstSingle(customers)}");

primer cliente con un solo pedido: C-21

Dos pasadas: la primera cuenta, la segunda recorre el registro, en el orden de los pedidos, y se detiene en el primero con contador 1. O(n), sin bucle anidado.

Más precisamente, para curiosos

¿Por qué la segunda pasada recorre el registro y no el mapa? Un Dictionary en el .NET de hoy recorre en el orden de inserción mientras no se haya quitado nada, pero la documentación no lo promete. No cuentes con ello.

La idea

Dos productos por exactamente 50 €

El cliente tiene un vale de exactamente 50 € y quiere dos productos que lo agoten. Los precios del catálogo no están ordenados.

Recorres los precios y para cada uno preguntas: ¿he visto ya el precio que completa este hasta 50? El mapa guarda los precios vistos hasta ahora y sus posiciones:

static (int, int)? VoucherPair(int[] prices, int voucher)
{
    var seen = new Dictionary<int, int>();
    for (int i = 0; i < prices.Length; i++)
    {
        if (seen.TryGetValue(voucher - prices[i], out int j)) return (j, i);
        seen[prices[i]] = i;
    }
    return null;
}

int[] prices = { 27, 14, 33, 25, 8, 36, 19 };
var (a, b) = VoucherPair(prices, 50).Value;
Console.WriteLine($"productos {a} y {b}: {prices[a]} € + {prices[b]} €");

productos 1 y 5: 14 € + 36 €

Una pasada: O(n) de tiempo y O(n) de memoria. Con dos punteros funciona sin mapa, con memoria O(1), pero los precios tienen que estar ordenados. Si no lo están, ordenar cuesta O(n log n) y se pierde la posición de cada producto en el catálogo. Así que: datos ordenados, dos punteros; datos sin ordenar, un mapa.

Pruébalo

Encuentra el error

Alguien intercambió dos líneas. Ahora, para un vale de 50 €, el programa ofrece un producto dos veces:

int[] prices = { 27, 14, 33, 25, 8, 36, 19 };
var (a, b) = VoucherPair(prices, 50).Value;
Console.WriteLine($"productos {a} y {b}: {prices[a]} € + {prices[b]} €");

productos 3 y 3: 25 € + 25 €

Elige la línea con el error.

Ejercicio

Quién gasta más

Resuelve la tarea en tu propio editor.

Ingresos por cliente. El registro tiene pares de cliente e importe: C-4 con 30 €, C-17 con 55 €, C-4 con 20 €, C-9 con 80 €, C-17 con 10 € y C-4 con 45 €. Suma los importes por cliente con un mapa (el valor es una suma, no un contador) e imprime los dos que más gastaron:

C-4: 95 €
C-9: 80 €

Más tareas

Anagramas. Escribe una comprobación de si dos palabras son anagramas («listen» y «silent») contando las letras con un mapa. ¿Cuántas operaciones necesita para palabras de longitud n?
La primera repetición. Encuentra el primer pedido cuyo cliente ya había pedido antes. ¿Necesitas un contador o basta un conjunto?
Periodos con contadores iguales. Con las sumas prefijas sabes contar periodos con una suma dada. Cuenta los periodos de días consecutivos en los que el número de pedidos devueltos es igual al de entregados.

Test

Ponte a prueba

1. El registro tiene 100 000 pedidos y 25 000 productos distintos. ¿Cuántas actualizaciones del contador hace el mapa?100 000: una por pedido100 000 · 25 00025 000: una por producto

2. ¿Cómo compruebas con un mapa que el carrito es exactamente el kit?Ordenar las dos listas y compararlas, sin mapa+1 por cada producto del kit, −1 por cada producto del carrito, y todos los contadores tienen que ser 0Comprobar que cada producto del carrito está en el kit

3. En voucherPair el precio entra en el mapa después de buscar su pareja. ¿Por qué no antes?Si no, un producto de 25 € se encuentra a sí mismo para un vale de 50 €Por la velocidadNo importa

4. ¿Cuándo son mejores dos punteros para una pareja con una suma dada?NuncaCuando los precios ya están ordenados: sin mapa y sin memoria adicionalSiempre, porque son más rápidos

5. Necesitas los 10 primeros de 2 000 000 de productos distintos. ¿Qué es lo más barato?Ordenar los 2 000 000 de paresUn heap con como máximo 10 elementos: O(m log k)Buscar el mayor diez veces

Una tabla hash como contador

Cookies