<div dir="ltr">¿algún imprevisto hasta ahora o acertaste con las previsiones?<div class="gmail_extra">
<br><div class="gmail_quote">El 27 de noviembre de 2017, 11:00, <span dir="ltr"><<a href="mailto:madrid-request@lists.es.python.org" target="_blank">madrid-request@lists.es.python.org</a>></span> escribió:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Send Madrid mailing list submissions to<br>
<a href="mailto:madrid@lists.es.python.org">madrid@lists.es.python.org</a><br>
<br>
To subscribe or unsubscribe via the World Wide Web, visit<br>
<a href="https://lists.es.python.org/listinfo/madrid" rel="noreferrer" target="_blank">https://lists.es.python.org/<wbr>listinfo/madrid</a><br>
or, via email, send a message with subject or body 'help' to<br>
<a href="mailto:madrid-request@lists.es.python.org">madrid-request@lists.es.<wbr>python.org</a><br>
<br>
You can reach the person managing the list at<br>
<a href="mailto:madrid-owner@lists.es.python.org">madrid-owner@lists.es.python.<wbr>org</a><br>
<br>
When replying, please edit your Subject line so it is more specific<br>
than "Re: Contents of Madrid digest..."<br>
<br>
<br>
Today's Topics:<br>
<br>
1. ¿Propuesta de algoritmo o estructura de datos para conjuntos<br>
aleatorios con pocos cambios? (Jesus Cea)<br>
2. Re: ¿Propuesta de algoritmo o estructura de datos para<br>
conjuntos aleatorios con pocos cambios? (<a href="mailto:piranna@gmail.com">piranna@gmail.com</a>)<br>
<br>
<br>
------------------------------<wbr>------------------------------<wbr>----------<br>
<br>
Message: 1<br>
Date: Mon, 27 Nov 2017 05:12:46 +0100<br>
From: Jesus Cea <<a href="mailto:jcea@jcea.es">jcea@jcea.es</a>><br>
To: Python Madrid <<a href="mailto:madrid@lists.es.python.org">madrid@lists.es.python.org</a>><br>
Subject: [Py-MAD] ¿Propuesta de algoritmo o estructura de datos para<br>
conjuntos aleatorios con pocos cambios?<br>
Message-ID: <<a href="mailto:21b781af-8800-e645-3d50-c974a036bfff@jcea.es">21b781af-8800-e645-3d50-<wbr>c974a036bfff@jcea.es</a>><br>
Content-Type: text/plain; charset="iso-8859-15"<br>
<br>
Requisitos:<br>
<br>
Tengo millones de bloques binarios de 256 bits. Estos millones de<br>
bloques están divididos aleatoriamente en grupos, digamos de un millón<br>
de elementos.<br>
<br>
Las operaciones básicas que debo soportar son:<br>
<br>
1. Creación de un grupo. Una vez creado un grupo, no necesita ser<br>
actualizado. Ni para añadir ni para eliminar.<br>
<br>
2. Comprobar si un elemento pertenece a un grupo concreto.<br>
<br>
3. Generar un grupo nuevo como unión de dos o más grupos.<br>
<br>
4. Generación de un grupo nuevo como intersección de dos o más grupos.<br>
<br>
5. Iterar sobre un grupo. El orden no es importante.<br>
<br>
A nivel de limitaciones, la más importante es que la sobrecarga en<br>
memoria debe ser lo mínimo posible. Cada elemento ocupa 32 bytes (256<br>
bits). La segunda más importante es que el algoritmo debe ser "cache<br>
friendly", sobre todo en la parte de búsqueda de pertenencia. En<br>
realidad solo necesito que el número de bloques de memoria de 4096 bytes<br>
que se revisan para buscar un elemento sea lo más bajo posible, porque<br>
el entorno de trabajo tiene muy poca memoria RAM pero se puede tirar de<br>
SWAP.<br>
<br>
No puedo tolerar falsos positivos, así que no puedo usar filtros bloom o<br>
filtros cuckoo. De momento la estructura de datos que va ganando son los<br>
hashes cuckoo: La ocupación de memoria es prácticamente óptima y solo<br>
requiere acceder a dos bloques de 4096 bytes.<br>
<br>
En cuanto a los datos en sí, son valores de 256 bits aleatorios. Ahora<br>
mismo los recibo en orden numérico, pero podría generar cualqueir otra<br>
estructura. Por ejemplo, podrían almacenarse directamente como un hash<br>
cuckoo para no tener que regenerarlos en tiempo de ejecución cada vez.<br>
<br>
Buscando en PYPI veo un par de proyectos que implementan filtros cuckoo.<br>
En principio no me sirven porque están escritos en Python nativo sin<br>
prestar atención al uso de memoria y porque no tolero falsos positivos.<br>
<br>
Dado que tengo los datos ya ordenados en la entrada, una opción evidente<br>
sería usar MMAP para verlos en memoria y hacer búsquedas mediante<br>
bisección. Esto sería óptimo en consumo de memoria, pero teniendo grupos<br>
de 8 megabytes, estaría tocando unos 11 bloques de 4096 bytes por cada<br>
comprobación de pertenencia. Aún suponiendo que los bloques más<br>
"calientes" estén cacheados en RAM, es preferible que el almacenamiento<br>
nativo sea un chuckoo hash, que nos garantiza un máximo de acceso a dos<br>
bloques de 4096 bytes.<br>
<br>
Usar un "set()" nativo de Python me garantiza un acceso típico de uno o<br>
dos bloques de 4096 bytes (bien) pero la ocupación en memoria es<br>
importante: entre dos y tres veces el tamaño de los datos originales.<br>
<br>
¿Alguna sugerencia?.<br>
<br>
Gracias por vuestras neuronas :-).<br>
<br>
Cuckoo hashing: <a href="https://en.wikipedia.org/wiki/Cuckoo_hashing" rel="noreferrer" target="_blank">https://en.wikipedia.org/wiki/<wbr>Cuckoo_hashing</a><br>
<br>
Cuento con programar el algoritmo en C o en Cython, si no encuentro nada<br>
hecho.<br>
<br>
--<br>
Jesús Cea Avión _/_/ _/_/_/ _/_/_/<br>
<a href="mailto:jcea@jcea.es">jcea@jcea.es</a> - <a href="http://www.jcea.es/" rel="noreferrer" target="_blank">http://www.jcea.es/</a> _/_/ _/_/ _/_/ _/_/ _/_/<br>
Twitter: @jcea _/_/ _/_/ _/_/_/_/_/<br>
jabber / <a href="mailto:xmpp%3Ajcea@jabber.org">xmpp:jcea@jabber.org</a> _/_/ _/_/ _/_/ _/_/ _/_/<br>
"Things are not so easy" _/_/ _/_/ _/_/ _/_/ _/_/ _/_/<br>
"My name is Dump, Core Dump" _/_/_/ _/_/_/ _/_/ _/_/<br>
"El amor es poner tu felicidad en la felicidad de otro" - Leibniz<br>
<br>
-------------- next part --------------<br>
A non-text attachment was scrubbed...<br>
Name: signature.asc<br>
Type: application/pgp-signature<br>
Size: 473 bytes<br>
Desc: OpenPGP digital signature<br>
URL: <<a href="https://lists.es.python.org/pipermail/madrid/attachments/20171127/cda02ae1/attachment-0001.bin" rel="noreferrer" target="_blank">https://lists.es.python.org/<wbr>pipermail/madrid/attachments/<wbr>20171127/cda02ae1/attachment-<wbr>0001.bin</a>><br>
<br>
------------------------------<br>
<br>
Message: 2<br>
Date: Mon, 27 Nov 2017 10:02:17 +0100<br>
From: "<a href="mailto:piranna@gmail.com">piranna@gmail.com</a>" <<a href="mailto:piranna@gmail.com">piranna@gmail.com</a>><br>
To: Python Madrid <<a href="mailto:madrid@lists.es.python.org">madrid@lists.es.python.org</a>><br>
Subject: Re: [Py-MAD] ¿Propuesta de algoritmo o estructura de datos<br>
para conjuntos aleatorios con pocos cambios?<br>
Message-ID:<br>
<<a href="mailto:CAKfGGh11Ru5FkvCYbGjQDZG69PR%2B4KOKuf%2BAhNwmFN5EYuX8rA@mail.gmail.com">CAKfGGh11Ru5FkvCYbGjQDZG69PR+<wbr>4KOKuf+AhNwmFN5EYuX8rA@mail.<wbr>gmail.com</a>><br>
Content-Type: text/plain; charset="UTF-8"<br>
<br>
el MMAP seria algo a tener muy en cuenta, quizas con un indice/hash<br>
aparte. Teniendo en cuenta son valores multiplo de 64 bits, podrias<br>
dividir los bloques o los hashes utilizando prefijos. Creo que Ext4<br>
ahora soporta 2⁶4 entradas en cada directorio, con lo que con un arbol<br>
de directorios en 3 o 4 niveles usando los prefijos como nombres de<br>
los direcotorios lo tendrias, y despues tirar de MMAP y la RAM como<br>
cache. No se si sera lo mas optimo pero quizas te de una idea...<br>
<br>
El día 27 de noviembre de 2017, 5:12, Jesus Cea <<a href="mailto:jcea@jcea.es">jcea@jcea.es</a>> escribió:<br>
> Requisitos:<br>
><br>
> Tengo millones de bloques binarios de 256 bits. Estos millones de<br>
> bloques están divididos aleatoriamente en grupos, digamos de un millón<br>
> de elementos.<br>
><br>
> Las operaciones básicas que debo soportar son:<br>
><br>
> 1. Creación de un grupo. Una vez creado un grupo, no necesita ser<br>
> actualizado. Ni para añadir ni para eliminar.<br>
><br>
> 2. Comprobar si un elemento pertenece a un grupo concreto.<br>
><br>
> 3. Generar un grupo nuevo como unión de dos o más grupos.<br>
><br>
> 4. Generación de un grupo nuevo como intersección de dos o más grupos.<br>
><br>
> 5. Iterar sobre un grupo. El orden no es importante.<br>
><br>
> A nivel de limitaciones, la más importante es que la sobrecarga en<br>
> memoria debe ser lo mínimo posible. Cada elemento ocupa 32 bytes (256<br>
> bits). La segunda más importante es que el algoritmo debe ser "cache<br>
> friendly", sobre todo en la parte de búsqueda de pertenencia. En<br>
> realidad solo necesito que el número de bloques de memoria de 4096 bytes<br>
> que se revisan para buscar un elemento sea lo más bajo posible, porque<br>
> el entorno de trabajo tiene muy poca memoria RAM pero se puede tirar de<br>
> SWAP.<br>
><br>
> No puedo tolerar falsos positivos, así que no puedo usar filtros bloom o<br>
> filtros cuckoo. De momento la estructura de datos que va ganando son los<br>
> hashes cuckoo: La ocupación de memoria es prácticamente óptima y solo<br>
> requiere acceder a dos bloques de 4096 bytes.<br>
><br>
> En cuanto a los datos en sí, son valores de 256 bits aleatorios. Ahora<br>
> mismo los recibo en orden numérico, pero podría generar cualqueir otra<br>
> estructura. Por ejemplo, podrían almacenarse directamente como un hash<br>
> cuckoo para no tener que regenerarlos en tiempo de ejecución cada vez.<br>
><br>
> Buscando en PYPI veo un par de proyectos que implementan filtros cuckoo.<br>
> En principio no me sirven porque están escritos en Python nativo sin<br>
> prestar atención al uso de memoria y porque no tolero falsos positivos.<br>
><br>
> Dado que tengo los datos ya ordenados en la entrada, una opción evidente<br>
> sería usar MMAP para verlos en memoria y hacer búsquedas mediante<br>
> bisección. Esto sería óptimo en consumo de memoria, pero teniendo grupos<br>
> de 8 megabytes, estaría tocando unos 11 bloques de 4096 bytes por cada<br>
> comprobación de pertenencia. Aún suponiendo que los bloques más<br>
> "calientes" estén cacheados en RAM, es preferible que el almacenamiento<br>
> nativo sea un chuckoo hash, que nos garantiza un máximo de acceso a dos<br>
> bloques de 4096 bytes.<br>
><br>
> Usar un "set()" nativo de Python me garantiza un acceso típico de uno o<br>
> dos bloques de 4096 bytes (bien) pero la ocupación en memoria es<br>
> importante: entre dos y tres veces el tamaño de los datos originales.<br>
><br>
> ¿Alguna sugerencia?.<br>
><br>
> Gracias por vuestras neuronas :-).<br>
><br>
> Cuckoo hashing: <a href="https://en.wikipedia.org/wiki/Cuckoo_hashing" rel="noreferrer" target="_blank">https://en.wikipedia.org/wiki/<wbr>Cuckoo_hashing</a><br>
><br>
> Cuento con programar el algoritmo en C o en Cython, si no encuentro nada<br>
> hecho.<br>
><br>
> --<br>
> Jesús Cea Avión _/_/ _/_/_/ _/_/_/<br>
> <a href="mailto:jcea@jcea.es">jcea@jcea.es</a> - <a href="http://www.jcea.es/" rel="noreferrer" target="_blank">http://www.jcea.es/</a> _/_/ _/_/ _/_/ _/_/ _/_/<br>
> Twitter: @jcea _/_/ _/_/ _/_/_/_/_/<br>
> jabber / <a href="mailto:xmpp%3Ajcea@jabber.org">xmpp:jcea@jabber.org</a> _/_/ _/_/ _/_/ _/_/ _/_/<br>
> "Things are not so easy" _/_/ _/_/ _/_/ _/_/ _/_/ _/_/<br>
> "My name is Dump, Core Dump" _/_/_/ _/_/_/ _/_/ _/_/<br>
> "El amor es poner tu felicidad en la felicidad de otro" - Leibniz<br>
><br>
><br>
> ______________________________<wbr>_________________<br>
> Asociación Python España: <a href="http://www.es.python.org/" rel="noreferrer" target="_blank">http://www.es.python.org/</a><br>
> Python Madrid: <a href="http://www.python-madrid.es/" rel="noreferrer" target="_blank">http://www.python-madrid.es/</a><br>
> Madrid mailing list<br>
> <a href="mailto:Madrid@lists.es.python.org">Madrid@lists.es.python.org</a><br>
> <a href="https://lists.es.python.org/listinfo/madrid" rel="noreferrer" target="_blank">https://lists.es.python.org/<wbr>listinfo/madrid</a><br>
<br>
<br>
<br>
--<br>
"Si quieres viajar alrededor del mundo y ser invitado a hablar en un<br>
monton de sitios diferentes, simplemente escribe un sistema operativo<br>
Unix."<br>
– Linus Tordvals, creador del sistema operativo Linux<br>
<br>
<br>
------------------------------<br>
<br>
Subject: Digest Footer<br>
<br>
______________________________<wbr>_________________<br>
Asociación Python España: <a href="http://www.es.python.org/" rel="noreferrer" target="_blank">http://www.es.python.org/</a><br>
Python Madrid: <a href="http://www.python-madrid.es/" rel="noreferrer" target="_blank">http://www.python-madrid.es/</a><br>
Madrid mailing list<br>
<a href="mailto:Madrid@lists.es.python.org">Madrid@lists.es.python.org</a><br>
<a href="https://lists.es.python.org/listinfo/madrid" rel="noreferrer" target="_blank">https://lists.es.python.org/<wbr>listinfo/madrid</a><br>
<br>
------------------------------<br>
<br>
End of Madrid Digest, Vol 55, Issue 2<br>
******************************<wbr>*******<br>
</blockquote></div><br></div></div>