[Py-MAD] ¿Propuesta de algoritmo o estructura de datos para conjuntos aleatorios con pocos cambios?

[piranna at gmail.com]

el MMAP seria algo a tener muy en cuenta, quizas con un indice/hash
aparte. Teniendo en cuenta son valores multiplo de 64 bits, podrias
dividir los bloques o los hashes utilizando prefijos. Creo que Ext4
ahora soporta 2⁶4 entradas en cada directorio, con lo que con un arbol
de directorios en 3 o 4 niveles usando los prefijos como nombres de
los direcotorios lo tendrias, y despues tirar de MMAP y la RAM como
cache. No se si sera lo mas optimo pero quizas te de una idea...

El día 27 de noviembre de 2017, 5:12, Jesus Cea <jcea at jcea.es> escribió:
> Requisitos:
>
> Tengo millones de bloques binarios de 256 bits. Estos millones de
> bloques están divididos aleatoriamente en grupos, digamos de un millón
> de elementos.
>
> Las operaciones básicas que debo soportar son:
>
> 1. Creación de un grupo. Una vez creado un grupo, no necesita ser
> actualizado. Ni para añadir ni para eliminar.
>
> 2. Comprobar si un elemento pertenece a un grupo concreto.
>
> 3. Generar un grupo nuevo como unión de dos o más grupos.
>
> 4. Generación de un grupo nuevo como intersección de dos o más grupos.
>
> 5. Iterar sobre un grupo. El orden no es importante.
>
> A nivel de limitaciones, la más importante es que la sobrecarga en
> memoria debe ser lo mínimo posible. Cada elemento ocupa 32 bytes (256
> bits). La segunda más importante es que el algoritmo debe ser "cache
> friendly", sobre todo en la parte de búsqueda de pertenencia. En
> realidad solo necesito que el número de bloques de memoria de 4096 bytes
> que se revisan para buscar un elemento sea lo más bajo posible, porque
> el entorno de trabajo tiene muy poca memoria RAM pero se puede tirar de
> SWAP.
>
> No puedo tolerar falsos positivos, así que no puedo usar filtros bloom o
> filtros cuckoo. De momento la estructura de datos que va ganando son los
> hashes cuckoo: La ocupación de memoria es prácticamente óptima y solo
> requiere acceder a dos bloques de 4096 bytes.
>
> En cuanto a los datos en sí, son valores de 256 bits aleatorios. Ahora
> mismo los recibo en orden numérico, pero podría generar cualqueir otra
> estructura. Por ejemplo, podrían almacenarse directamente como un hash
> cuckoo para no tener que regenerarlos en tiempo de ejecución cada vez.
>
> Buscando en PYPI veo un par de proyectos que implementan filtros cuckoo.
> En principio no me sirven porque están escritos en Python nativo sin
> prestar atención al uso de memoria y porque no tolero falsos positivos.
>
> Dado que tengo los datos ya ordenados en la entrada, una opción evidente
> sería usar MMAP para verlos en memoria y hacer búsquedas mediante
> bisección. Esto sería óptimo en consumo de memoria, pero teniendo grupos
> de 8 megabytes, estaría tocando unos 11 bloques de 4096 bytes por cada
> comprobación de pertenencia. Aún suponiendo que los bloques más
> "calientes" estén cacheados en RAM, es preferible que el almacenamiento
> nativo sea un chuckoo hash, que nos garantiza un máximo de acceso a dos
> bloques de 4096 bytes.
>
> Usar un "set()" nativo de Python me garantiza un acceso típico de uno o
> dos bloques de 4096 bytes (bien) pero la ocupación en memoria es
> importante: entre dos y tres veces el tamaño de los datos originales.
>
> ¿Alguna sugerencia?.
>
> Gracias por vuestras neuronas :-).
>
> Cuckoo hashing: https://en.wikipedia.org/wiki/Cuckoo_hashing
>
> Cuento con programar el algoritmo en C o en Cython, si no encuentro nada
> hecho.
>
> --
> Jesús Cea Avión                         _/_/      _/_/_/        _/_/_/
> jcea at jcea.es - http://www.jcea.es/     _/_/    _/_/  _/_/    _/_/  _/_/
> Twitter: @jcea                        _/_/    _/_/          _/_/_/_/_/
> jabber / xmpp:jcea at jabber.org  _/_/  _/_/    _/_/          _/_/  _/_/
> "Things are not so easy"      _/_/  _/_/    _/_/  _/_/    _/_/  _/_/
> "My name is Dump, Core Dump"   _/_/_/        _/_/_/      _/_/  _/_/
> "El amor es poner tu felicidad en la felicidad de otro" - Leibniz
>
>
> _______________________________________________
> Asociación Python España: http://www.es.python.org/
> Python Madrid: http://www.python-madrid.es/
> Madrid mailing list
> Madrid at lists.es.python.org
> https://lists.es.python.org/listinfo/madrid



-- 
"Si quieres viajar alrededor del mundo y ser invitado a hablar en un
monton de sitios diferentes, simplemente escribe un sistema operativo
Unix."
– Linus Tordvals, creador del sistema operativo Linux