HyperLogLog estima 370.103 palabras con solo 2,71% de error
Sorting, hashing, and sketches on 370,103 words
En este post, ponemos a prueba las estructuras de datos de Python con un conjunto real de 370.103 palabras únicas. Las ordenamos de seis maneras, las insertamos en cuatro estructuras diferentes y las resumimos con cuatro algoritmos probabilísticos, midiendo tiempo y memoria. El resultado más destacado: HyperLogLog estima el tamaño del vocabulario con solo un 2,71% de error usando 4.096 registros. También analizamos la complejidad de las operaciones y mostramos cómo los análisis asintóticos predicen el comportamiento real cuando las constantes son honestas.
Esa brecha es toda la lección: el análisis asintótico predice el comportamiento real cuando las constantes se mantienen honestas.