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

[Jesus Cea]

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 473 bytes
Desc: OpenPGP digital signature
URL: <https://lists.es.python.org/pipermail/madrid/attachments/20171127/cda02ae1/attachment.bin>