Una tabla hash como contador en Java

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:

List<String> log = logOf(1000);
List<String> names = new ArrayList<>();
List<Integer> counts = new ArrayList<>();
long comparisons = 0;
for (String item : log) {
    int i = 0;
    while (i < names.size()) {
        comparisons++;
        if (names.get(i).equals(item)) break;
        i++;
    }
    if (i == names.size()) {
        names.add(item);
        counts.add(1);
    } else {
        counts.set(i, counts.get(i) + 1);
    }
}
System.out.println("pedidos: " + log.size());
System.out.println("productos: " + names.size());
System.out.println("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;
    List<String> log = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        log.add("SKU-" + (i * 7919) % catalog);
    }
    return log;
}

La idea

El mapa cuenta

En la lección «HashMap 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 = List.of(
    "ratón", "audífonos", "ratón", "monitor",
    "teclado", "ratón", "audífonos", "monitor",
    "ratón", "audífonos");
Map<String, Integer> counts = new HashMap<>();
for (String item : log) {
    counts.merge(item, 1, Integer::sum);
}
List<Map.Entry<String, Integer>> top =
    new ArrayList<>(counts.entrySet());
top.sort((x, y) -> y.getValue() - x.getValue());
for (var e : top.subList(0, 3)) {
    System.out.println(e.getKey() + " " + e.getValue());
}

ratón 4
audífonos 3
monitor 2

Map<String, Integer> counts = new HashMap<>();
for (String item : log) {
    counts.merge(item, 1, Integer::sum);
}
List<Map.Entry<String, Integer>> top =
    new ArrayList<>(counts.entrySet());
top.sort((x, y) -> y.getValue() - x.getValue());
for (var e : top.subList(0, 3)) {
    System.out.println(e.getKey() + " " + e.getValue());
}

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.

merge(item, 1, Integer::sum) pone 1 si la clave no está, y si no suma 1 al contador anterior. 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.merge(item, 1, );

merge recibe cómo combinar el contador anterior con el nuevo: Integer::sum.

Míralo

Las herramientas de tu lenguaje

En Java el contador es un HashMap<String, Integer>. getOrDefault con put hace lo mismo que merge, pero busca la clave dos veces. merge la busca una. Cuando necesitas las claves ordenadas, Collectors.groupingBy con un TreeMap y Collectors.counting() cuenta en un stream:

List<String> log = List.of(
    "ratón", "audífonos", "ratón", "monitor",
    "teclado", "ratón", "audífonos", "monitor",
    "ratón", "audífonos");
Map<String, Integer> counts = new HashMap<>();
for (String item : log) {
    counts.put(item, counts.getOrDefault(item, 0) + 1);
}
System.out.println(counts.get("ratón") + " " + counts.getOrDefault("tableta", 0));
Map<String, Long> sorted = log.stream()
    .collect(Collectors.groupingBy(item -> item, TreeMap::new, Collectors.counting()));
System.out.println(sorted);

4 0
{audífonos=3, monitor=2, ratón=4, teclado=1}

Míralo

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

Los mismos mil pedidos con el mapa:

List<String> log = logOf(1000);
Map<String, Integer> counts = new HashMap<>();
long updates = 0;
for (String item : log) {
    counts.merge(item, 1, Integer::sum);
    updates++;
}
System.out.println("pedidos: " + log.size());
System.out.println("productos: " + counts.size());
System.out.println("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.

Map<String, Integer> counts = new HashMap<>();
for (String item : log) {
    counts.merge(item, 1, Integer::sum);
}
List<Map.Entry<String, Integer>> top =
    new ArrayList<>(counts.entrySet());
top.sort((x, y) -> y.getValue() - x.getValue());
for (var e : top.subList(0, 3)) {
    System.out.println(e.getKey() + " " + e.getValue());
}

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 Java es un record CityItem(String city, String item): un record tiene equals y hashCode 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 boolean matches(List<String> kit, List<String> basket) {
    Map<String, Integer> need = new HashMap<>();
    for (String item : kit) need.merge(item, 1, Integer::sum);
    for (String item : basket) need.merge(item, -1, Integer::sum);
    for (int n : need.values()) {
        if (n != 0) return false;
    }
    return true;
}

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 = List.of(
    "monitor", "teclado", "ratón", "cable",
    "cable");
List<String> basket1 = List.of(
    "cable", "ratón", "monitor", "cable",
    "teclado");
List<String> basket2 = List.of(
    "monitor", "teclado", "ratón", "ratón",
    "cable");
System.out.println("carrito 1: " + (matches(kit, basket1) ? "kit completo" : "no coincide"));
System.out.println("carrito 2: " + (matches(kit, basket2) ? "kit completo" : "no coincide"));

Respuesta

carrito 1: no coincide
carrito 2: kit completo

carrito 1: kit completo
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) {
    Map<String, Integer> counts = new HashMap<>();
    for (String c : customers) counts.merge(c, 1, Integer::sum);
    for (String c : customers) {
        if (counts.get(c) == 1) return c;
    }
    return null;
}

List<String> customers = List.of(
    "C-17", "C-4", "C-17", "C-9",
    "C-4", "C-21", "C-9", "C-30");
System.out.println("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 HashMap no guarda ningún orden: recorrerlo va cubeta por cubeta. Un LinkedHashMap guarda el orden de inserción, y entonces recorrer el mapa también sirve.

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[] voucherPair(int[] prices, int voucher) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < prices.length; i++) {
        Integer j = seen.get(voucher - prices[i]);
        if (j != null) return new int[] { j, i };
        seen.put(prices[i], i);
    }
    return null;
}

int[] prices = { 27, 14, 33, 25, 8, 36, 19 };
int[] p = voucherPair(prices, 50);
System.out.println("productos " + p[0] + " y " + p[1] + ": " + prices[p[0]] + " € + " + prices[p[1]] + " €");

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 };
int[] p = voucherPair(prices, 50);
System.out.println("productos " + p[0] + " y " + p[1] + ": " + prices[p[0]] + " € + " + prices[p[1]] + " €");

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