una subconjunto potencia palabra lista elemento ejemplo conjuntos conjunto cardinalidad buscar python optimization memcached set cardinality

potencia - subconjunto python



¿Cómo se cuenta la cardinalidad de conjuntos de datos muy grandes de manera eficiente en Python? (2)

He estado jugando en el trabajo con algunos conjuntos muy grandes de datos, por lo general, varios miles de millones de elementos, que se mantienen en una nube memcached y se vuelcan periódicamente en archivos, y para una de mis tareas estoy tratando de contar la cardinalidad de este conjunto.

Para algunos contextos, cada elemento contiene una IP y algunos otros atributos que identifican a una persona y está codificada en base64, el tamaño del elemento es de 20 bytes. No es posible reducir el tamaño de un elemento eliminando algunos campos.

Aquí hay algo que emula mi conjunto de datos como una versión en memoria (gracias a esta publicación para la generación de cadenas):

import base64, os dataset_size = 10000000000 # that''s 10 billion, be careful if you run it ! big_dataset = [base64.b64encode(os.urandom(10)) for i in range(dataset_size)]

Mi primer acercamiento fue usar un hashset como este:

uniques = set(big_dataset) print "Cardinality: %d" % len(uniques)

Si bien esto, en teoría, funciona bien en un pequeño conjunto de datos, como se puede adivinar, hay un tropiezo:

  • No puedo hacer ninguna suposición sobre la singularidad de mis datos. Podría tener el 50% de mi conjunto de datos que es único, o podría tener el 100% igual de bien. Esto se genera dinámicamente en intervalos de tiempo regulares y varía dependiendo de muchos factores (por ejemplo, la hora del día)
  • Tamaño del conjunto de datos en 10 mil millones. Cada elemento codificado en la base 64 es de 20 bytes, multiplicado por 10 mil millones en algunos cientos de gigabytes en promedio. Desafortunadamente, ¡no tengo acceso a una máquina con tanta RAM!

He hecho mi tarea y he encontrado, en el mejor de los casos, algunos trabajos de investigación, o algunas bibliotecas oscuras, pero parte del objetivo de esto es entender qué enfoque funciona y por qué.

Así que les llamo usuarios de Python, ¿conocen algún algoritmo que me ayude a estimar la cardinalidad de manera eficiente? Por complejidad quiero decir que no me importa mucho la complejidad del tiempo de ejecución, pero estoy más centrado en la complejidad del espacio. No me importa sacrificar un poco la precisión si aumenta el rendimiento tremendamente (por lo que no necesariamente necesito saber el número exacto de muestras únicas, incluso si eso fuera ideal, pero probablemente no sea un enfoque viable). Yo diría que hasta un 5% sería aceptable. Estoy buscando algo específicamente en Python para este proyecto.

Gracias por cualquier ayuda que usted nos pueda proporcionar !

Como señalaron algunas personas, podría usar Hadoop / MR, pero para este tipo de proyectos específicos no queremos ir por MR, y nos gustaría explorar algoritmos para hacer esto en una sola máquina de manera eficiente, ya que esto podría aplicarse a un algunos otros proyectos diferentes.

Te aconsejo que pruebes con un filtro de floración. Incluso con tal cantidad de datos, puede lograr tasas de error extremadamente bajas con requisitos de sistema modestos. Dado que usará la (aproximadamente) óptima k = ln (2) * (tamaño del filtro de floración en bits) / (10 billones) puede calcular el tamaño del filtro de floración en bits como - ((10billones) * ln (falso positivo deseado) tasa)) / ln (2) ^ 2.

Por ejemplo, con menos de 2 gigas de memoria, puede obtener una tasa de error del 0.1%. Una implementación muy rápida y extremadamente simple de todo esto es http://mike.axiak.net/python-bloom-filter/docs/html/