Desarrollo de un nuevo algoritmo de conteo eficiente
Introducción
- Imaginen que están realizando un monitoreo de fauna silvestre en un bosque virgen.
- Toman fotos de animales con una cámara digital y quieren saber cuántos animales no repetidos hay.
- Los métodos existentes requieren recordar y comparar todos los animales, pero eso es ineficiente.
La situación del problema
- En plataformas masivas como Facebook, es difícil contar cuántos usuarios únicos inician sesión cada día.
- Recientemente, científicos de la computación propusieron un nuevo método para estimar la cantidad de elementos únicos en listas largas.
- Este algoritmo solo necesita recordar una pequeña cantidad de elementos.
El algoritmo CVM
- El algoritmo CVM es un paso importante para resolver el problema de los elementos únicos, que se ha estudiado durante más de 40 años.
- Este algoritmo puede estimar de forma eficiente la cantidad de elementos únicos en un flujo de datos.
- "El nuevo algoritmo es sorprendentemente simple y fácil de implementar" - Andrew McGregor
Ejemplo: el audiolibro de Hamlet
- Hamlet tiene 30,557 palabras. Para saber cuántas de ellas son únicas, normalmente habría que recordar todas las palabras.
- El algoritmo CVM usa aleatorización para reducir el uso de memoria.
Cómo funciona el algoritmo CVM
- Primera ronda: se registran 100 palabras y las palabras duplicadas se eliminan con un lanzamiento de moneda.
- Segunda ronda: para que las palabras duplicadas sean aún más difíciles de conservar, se requieren dos lanzamientos de moneda.
- Tercera ronda: se requieren tres lanzamientos de moneda.
- Esto se repite hasta la ronda k para estimar la cantidad de palabras únicas.
Verificación de precisión
- La precisión varía según el tamaño de la memoria.
- La cantidad de palabras únicas en Hamlet es 3,967; con una memoria de 100, la estimación promedio fue 3,955, y con una memoria de 1,000, la estimación promedio fue 3,964.
Conclusión
- "Incluso en problemas fundamentales y muy estudiados, pueden existir soluciones simples pero poco intuitivas" - William Kuszmaul
La opinión de GN⁺
- Útil en escenarios de streaming de datos: el algoritmo CVM puede estimar de forma eficiente elementos únicos en grandes flujos de datos, por lo que resulta útil para análisis en tiempo real.
- Eficiencia de memoria: puede mantener una alta precisión minimizando el uso de memoria, lo que lo hace especialmente ventajoso en entornos con restricciones de memoria.
- La importancia de la aleatorización: el hecho de que permita resolver de forma simple un problema complejo sugiere un gran potencial de aplicación en otros campos.
- Consideraciones para su adopción: al incorporar este algoritmo, hay que considerar el equilibrio entre tamaño de memoria y precisión. Si no hay suficiente memoria, la precisión puede disminuir.
- Tecnologías relacionadas: vale la pena compararlo con otros algoritmos de estimación de elementos únicos como HyperLogLog. Es importante entender las ventajas y desventajas de cada algoritmo para elegir la solución óptima según el caso.
1 comentarios
Comentarios de Hacker News
Resumen de comentarios de Hacker News
Algoritmo similar a HyperLogLog
Se explica un algoritmo similar a HyperLogLog usando la racha de lanzamientos de moneda. Funciona de forma eficiente especialmente con datos en streaming y usa poca memoria.
Se señala un error en la explicación del algoritmo
Se indica que la explicación del algoritmo es incorrecta y se presenta el método correcto mediante un ejemplo de código. Guardar primero las palabras y luego eliminarlas produce resultados más precisos.
Recomendación del artículo académico
Se menciona que el artículo académico es tan fácil de leer como la publicación del blog y ofrece más información. Explica un algoritmo simple para estimar la cardinalidad de un conjunto en datos en streaming.
Ejemplo de implementación en Python
Se proporciona un ejemplo de implementación en Python de un algoritmo de streaming. Con código simple se puede entender y practicar el algoritmo.
Útil para refactorizar sistemas
Se menciona que, mientras se refactoriza un sistema que cuenta insertando visitas en una tabla, este método parece una alternativa interesante al enfoque de HyperLogLog.
Método eficiente en memoria
Se menciona que científicos de la computación inventaron un método eficiente en memoria para estimar el tamaño de subconjuntos.
Discusión sobre la cota de Chernoff
Se discute una variante de la cota de Chernoff usada en el artículo académico. Se menciona que no está claro si esta variante afecta la corrección de la demostración.
Diferencia entre estimar y contar elementos únicos
Se menciona que estimar la cantidad de elementos únicos y contarlos realmente son cosas muy distintas, y se señala que el título es inapropiado.
Introducción a algoritmos eficientes de streaming
Se presenta un algoritmo eficiente y fácil de implementar para encontrar los k elementos principales en un stream. Se recomienda el artículo de Karp, Shenker y Papadimitriou.
Importancia del pensamiento creativo
Se menciona que disfrutan los ejemplos de "pensar fuera de la caja" y se enfatiza que es importante encontrar la pregunta correcta para resolver un problema. Se espera poder interiorizar y aplicar el pensamiento creativo a través de varios ejemplos.