Temario Lección 77 de 148 · Límites raros
Límites raros

Memoria fija

Por qué importa "Cuenta cuántas veces ocurre cada cosa" es un diccionario, hasta que el número de cosas no tiene límite y la memoria sí. Una cuenta aproximada con un límite garantizado suele valer mucho más que una cuenta exacta que no te puedes permitir.

Una pasarela de API marca a los usuarios que más la usan. Ve cada petición, puede haber cualquier número de usuarios y cada proceso de la pasarela recibe un trozo fijo de memoria para este trabajo. La marca solo es un aviso para que una persona mire, así que contar un poco de más está bien; contar de menos podría esconder a un usuario intensivo, así que no.

Sketch: un resumen de tamaño fijo de un flujo que responde preguntas de forma aproximada, con un límite de error conocido. Un sketch count-min, por ejemplo, guarda unas pocas filas de contadores y asigna con un hash cada elemento a un contador por fila; el más pequeño de esos contadores nunca está por debajo de la cuenta real.

import zlib
row_index = zlib.crc32(f"{row}:{item}".encode()) % width   # same on every run
Tu turno

Escribe class ApproxCounter con add(item) (los elementos son cadenas) y estimate(item) (un número entero).

Límites. Después de 30,000 eventos de hasta 10,000 usuarios distintos, el contador puede guardar como mucho 3,500 elementos (kept() sobre el contador). Las estimaciones nunca deben estar por debajo de la cuenta real, y para al menos el 95% de los usuarios (incluidos los que nunca se vieron) deben ser como mucho la cuenta real más 300 (el 1% de los eventos). Los resultados deben repetirse igual en cada ejecución y dispositivo: no uses hash() (cambia en cada ejecución) ni números aleatorios; zlib.crc32 o hashlib con semillas fijas sirven.

¿Has visto un problema en esta lección? Avísanos · Preguntar sobre esta lección

Este ejercicio se abre pronto

Termina la lección anterior y esta se desbloquea. Todo el curso es gratis, no hace falta cuenta, y puedes leer esta lección ahora mismo.