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

[Francesc Alted]

Lo único que se me ocurre es que, para minimizar el uso de memoria uses
compresión para tus bloques binarios (dices que te llegan ordenados
numéricamente, así que seguro que se pueden obtener buenos ratios de
compresión).  Para las búsquedas puedes continuar usando hashes cuckoo,
pero sólo guardando las claves, no los valores, y así maximizas la
localidad de los accesos a memoria (durante la búsqueda no te sirve de nada
traer los valores a las lineas de cache).

Una vez localizado el lugar donde está el valor puedes acceder al bloque
comprimido que toque, descomprimir, y extraerlo.  Blosc te permite esta
clase de acceso de manera muy eficiente a través de la llamada
`blosc_getitem()` (
https://github.com/Blosc/c-blosc/blob/master/blosc/blosc.h#L290).  Si
eliges el tamaño de bloque lo suficientemente pequeño (digamos 4/8/16/32
KB), la descompresión normalmente sucede en la cache L1, así que es muy
rápido.

Francesc

2017-11-27 5:13 GMT+01:00 Jesus Cea <jcea en jcea.es>:

> 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 en jcea.es - http://www.jcea.es/     _/_/    _/_/  _/_/    _/_/  _/_/
> Twitter: @jcea                        _/_/    _/_/          _/_/_/_/_/
> jabber / xmpp:jcea en 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
>
>
> _______________________________________________
> Python-es mailing list
> Python-es en python.org
> https://mail.python.org/mailman/listinfo/python-es
>
>


-- 
Francesc Alted
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://mail.python.org/pipermail/python-es/attachments/20171127/fd4ba876/attachment.html>