Una tabla hash como contador
En resumen: Un mapa usado como contador (dict o collections.Counter en Python) cuenta cuántas veces aparece cada elemento en una sola pasada: O(n) en lugar de O(n²) al buscar en una lista.
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:
log = log_of(1000)names = []counts = []comparisons = 0for item in log: i = 0 while i < len(names): comparisons += 1 if names[i] == item: break i += 1 if i == len(names): names.append(item) counts.append(1) else: counts[i] += 1print(f"pedidos: {len(log)}")print(f"productos: {len(names)}")print(f"comparaciones: {comparisons}")pedidos: 1000productos: 251comparaciones: 125255Mil 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:
def log_of(n): catalog = n // 4 + 1 return [f"SKU-{(i * 7919) % catalog}" for i in range(n)]La idea
El mapa cuenta
En la lección «dict y set» 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
from collections import defaultdict
log = [ "ratón", "audífonos", "ratón", "monitor", "teclado", "ratón", "audífonos", "monitor", "ratón", "audífonos",]counts = defaultdict(int)for item in log: counts[item] += 1top = sorted(counts.items(), key=lambda e: e[1], reverse=True)for item, n in top[:3]: print(item, n)ratón 4audífonos 3monitor 2counts = defaultdict(int)for item in log: counts[item] += 1top = sorted(counts.items(), key=lambda e: e[1], reverse=True)for item, n in top[:3]: print(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.
defaultdict(int) crea un contador en 0 la primera vez que se lee una clave nueva, así que counts[item] += 1 también funciona para un producto nuevo. 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 = defaultdict()defaultdict(int) llama a int() para una clave nueva, y int() es 0.Míralo
Las herramientas de tu lenguaje
Python tiene un contador ya hecho: collections.Counter. Toma la lista y cuenta por sí solo, da 0 para una clave que falta, y most_common(k) devuelve los k primeros por contador. Los contadores iguales se quedan en el orden de la primera aparición:
from collections import Counter
log = [ "ratón", "audífonos", "ratón", "monitor", "teclado", "ratón", "audífonos", "monitor", "ratón", "audífonos",]counts = Counter(log)print(counts["ratón"], counts["tableta"])print(counts.most_common(3))4 0[('ratón', 4), ('audífonos', 3), ('monitor', 2)]defaultdict(int) es la herramienta más general: el mismo contador, pero el valor también puede ser una suma o una lista.
Míralo
Mídelo: una lista de pares frente a un mapa
Los mismos mil pedidos con el mapa:
log = log_of(1000)counts = defaultdict(int)updates = 0for item in log: counts[item] += 1 updates += 1print(f"pedidos: {len(log)}")print(f"productos: {len(counts)}")print(f"actualizaciones del contador: {updates}")pedidos: 1000productos: 251actualizaciones del contador: 10001000 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 |
counts = defaultdict(int)for item in log: counts[item] += 1top = sorted(counts.items(), key=lambda e: e[1], reverse=True)for item, n in top[:3]: print(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 Python es una tupla (city, item): es inmutable y tiene un hash.
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.
def matches(kit, basket): return Counter(kit) == Counter(basket)Counter se compara con == por sus contadores, así que toda la comprobación es una línea.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
from collections import Counter
kit = ["monitor", "teclado", "ratón", "cable", "cable"]basket1 = ["cable", "ratón", "monitor", "cable", "teclado"]basket2 = ["monitor", "teclado", "ratón", "ratón", "cable"]print(f"carrito 1: {'kit completo' if matches(kit, basket1) else 'no coincide'}")print(f"carrito 2: {'kit completo' if matches(kit, basket2) else 'no coincide'}")El primer carrito tiene los mismos cinco productos en otro orden: cada contador pasa a 0. El segundo tiene dos ratones y un cable: el ratón se queda en −1, el cable en +1, así que no coincide, aunque sean cinco productos.
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:
def first_single(customers): counts = Counter(customers) for c in customers: if counts[c] == 1: return c return Nonefrom collections import Counter
customers = [ "C-17", "C-4", "C-17", "C-9", "C-4", "C-21", "C-9", "C-30",]print(f"primer cliente con un solo pedido: {first_single(customers)}")primer cliente con un solo pedido: C-21Dos 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 dict guarda el orden de inserción (garantizado desde Python 3.7), así que aquí recorrer counts daría la misma respuesta. El registro sigue siendo más claro: el orden viene de él.
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:
def voucher_pair(prices, voucher): seen = {} for i, price in enumerate(prices): j = seen.get(voucher - price) if j is not None: return j, i seen[price] = i return Noneprices = [27, 14, 33, 25, 8, 36, 19]a, b = voucher_pair(prices, 50)print(f"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:
prices = [27, 14, 33, 25, 8, 36, 19]a, b = voucher_pair(prices, 50)print(f"productos {a} y {b}: {prices[a]} € + {prices[b]} €")productos 3 y 3: 25 € + 25 €Elige la línea con el error.
El precio entra en el mapa antes de buscar su pareja. El producto de 25 € busca 50 − 25 = 25 y se encuentra a sí mismo. La escritura debe ir después de la búsqueda: entonces el mapa contiene solo los productos anteriores al actual, y el programa encuentra 14 € + 36 €.
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