Un artículo técnico del blog Stochastic analiza el comportamiento de algoritmos fundamentales de ordenación, hashing y sketches probabilísticos al aplicarlos a un vocabulario real de 370.103 palabras en inglés, extraídas del repositorio dwyl/english-words. El texto funciona como una guía práctica de los mecanismos que sostienen sistemas modernos como buscadores o cachés.
El trabajo parte de los fundamentos establecidos en una entrada previa, donde se estudiaron listas, diccionarios, conjuntos y recursión en Python. Ahora esos conocimientos se llevan a un conjunto de datos real: un único archivo de 21,63 MB que, tras limpieza, deja 370.103 palabras únicas. La distribución de longitudes se concentra entre 3 y 10 caracteres, con una cola larga que supera los 15, y la tasa de palabras fuera de vocabulario alcanza el 1,0 sobre una partición de prueba, lo que garantiza que las estructuras de membresía enfrentarán consultas completamente nuevas.
Antes de medir nada, el artículo repasa notación Big-O, Big-Theta y análisis amortizado. El sort integrado de Python sobre 50.000 palabras tarda 0,0011 segundos, y al duplicar la entrada el tiempo se duplica, confirmando el comportamiento n log n de Timsort. La inserción al inicio de una lista, en cambio, ilustra el coste O(n) frente a O(1) amortizado del append.
El recorrido continúa con la implementación manual de algoritmos clásicos como quicksort, la búsqueda binaria sobre un array ordenado y la construcción de tablas hash, tries y sketches. El resultado más llamativo: HyperLogLog estima el tamaño del vocabulario con solo un 2,71 % de error usando 4.096 registros, una eficiencia que ilustra por qué estas técnicas son la base de la infraestructura de datos actual.