[Py-MAD] Madrid Digest, Vol 55, Issue 2
Uxío Prego
uprego at madiva.com
Wed Jan 10 12:03:29 CET 2018
¿algún imprevisto hasta ahora o acertaste con las previsiones?
El 27 de noviembre de 2017, 11:00, <madrid-request at lists.es.python.org>
escribió:
> Send Madrid mailing list submissions to
> madrid at lists.es.python.org
>
> To subscribe or unsubscribe via the World Wide Web, visit
> https://lists.es.python.org/listinfo/madrid
> or, via email, send a message with subject or body 'help' to
> madrid-request at lists.es.python.org
>
> You can reach the person managing the list at
> madrid-owner at lists.es.python.org
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of Madrid digest..."
>
>
> Today's Topics:
>
> 1. ¿Propuesta de algoritmo o estructura de datos para conjuntos
> aleatorios con pocos cambios? (Jesus Cea)
> 2. Re: ¿Propuesta de algoritmo o estructura de datos para
> conjuntos aleatorios con pocos cambios? (piranna at gmail.com)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Mon, 27 Nov 2017 05:12:46 +0100
> From: Jesus Cea <jcea at jcea.es>
> To: Python Madrid <madrid at lists.es.python.org>
> Subject: [Py-MAD] ¿Propuesta de algoritmo o estructura de datos para
> conjuntos aleatorios con pocos cambios?
> Message-ID: <21b781af-8800-e645-3d50-c974a036bfff at jcea.es>
> Content-Type: text/plain; charset="iso-8859-15"
>
> 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-0001.bin>
>
> ------------------------------
>
> Message: 2
> Date: Mon, 27 Nov 2017 10:02:17 +0100
> From: "piranna at gmail.com" <piranna at gmail.com>
> To: Python Madrid <madrid at lists.es.python.org>
> Subject: Re: [Py-MAD] ¿Propuesta de algoritmo o estructura de datos
> para conjuntos aleatorios con pocos cambios?
> Message-ID:
> <CAKfGGh11Ru5FkvCYbGjQDZG69PR+4KOKuf+AhNwmFN5EYuX8rA at mail.
> gmail.com>
> Content-Type: text/plain; charset="UTF-8"
>
> 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
>
>
> ------------------------------
>
> Subject: Digest Footer
>
> _______________________________________________
> 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
>
> ------------------------------
>
> End of Madrid Digest, Vol 55, Issue 2
> *************************************
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.es.python.org/pipermail/madrid/attachments/20180110/d3f2a380/attachment.html>
More information about the Madrid
mailing list