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

2017-11-28 Por tema Kiko 
El 28 de noviembre de 2017, 11:29, lasizoillo 
escribió:

>
>
> El 27 de noviembre de 2017, 23:37, Jesus Cea  escribió:
>
>>
>>
>> El objetivo es batir esas dos páginas de memoria por "lookup". ¿Ideas?.
>>
>>
> Probablemente diga una barbaridad, pero por si acaso no lo es la digo ;-)
>
> https://www.kernel.org/doc/Documentation/vm/transhuge.txt
>
> Si el tema es evitar los accesos a páginas de memoria porque se producen
> cache-miss en la tabla que mapea la memoria virtual con la física está la
> posibilidad de aumentar los tamaños de las páginas de memoria. No es gratis
> y no está exento de problemas, pero bajamdo al nivel que te gusta bajar es
> posible que te sirva de ayuda.
>
> No entro en la parte de la algorítmica porque parece que la tienes atada y
> no me ha dado tiempo a profundizar. De lo poco que he tenido tiempo de leer
> sobre el cuckoo hashing he visto que hablaban sobre límites de ocupación
> del hash ¿Puede ser eso problemático?
>
> Gracias a los dos por el hilo, está siendo un auténtico placer leeros.
>

+1
(desde la sombra de la ignorancia)


>
> Un abrazo,
>
> Javi
>
> ___
> Python-es mailing list
> Python-es@python.org
> https://mail.python.org/mailman/listinfo/python-es
>
>
___
Python-es mailing list
Python-es@python.org
https://mail.python.org/mailman/listinfo/python-es

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

2017-11-28 Por tema lasizoillo 
El 27 de noviembre de 2017, 23:37, Jesus Cea  escribió:

>
>
> El objetivo es batir esas dos páginas de memoria por "lookup". ¿Ideas?.
>
>
Probablemente diga una barbaridad, pero por si acaso no lo es la digo ;-)

https://www.kernel.org/doc/Documentation/vm/transhuge.txt

Si el tema es evitar los accesos a páginas de memoria porque se producen
cache-miss en la tabla que mapea la memoria virtual con la física está la
posibilidad de aumentar los tamaños de las páginas de memoria. No es gratis
y no está exento de problemas, pero bajamdo al nivel que te gusta bajar es
posible que te sirva de ayuda.

No entro en la parte de la algorítmica porque parece que la tienes atada y
no me ha dado tiempo a profundizar. De lo poco que he tenido tiempo de leer
sobre el cuckoo hashing he visto que hablaban sobre límites de ocupación
del hash ¿Puede ser eso problemático?

Gracias a los dos por el hilo, está siendo un auténtico placer leeros.

Un abrazo,

Javi
___
Python-es mailing list
Python-es@python.org
https://mail.python.org/mailman/listinfo/python-es

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

2017-11-28 Por tema Francesc Alted 
2017-11-27 23:37 GMT+01:00 Jesus Cea :

> On 27/11/17 21:38, Francesc Alted wrote:
> > De todas maneras, lo que intentaba era hacer ver
> > que una ordenación siempre suele aumentar el ratio de compresión.
> > Aquí
> > hay un ejemplo mejor de lo que quería decir:
> >
> > In [40]: b = np.random.randint(2**63, size=1000*1000)
>
> Estás usando 63 bits, no 64, pero vale :-)
>

​Bueno, la verdad es que confieso que mientras estaba intentando los 64 me
encontré con:

In [8]: b = np.random.randint(2**64, size=1000*1000)
---
ValueErrorTraceback (most recent call last)
 in ()
> 1 b = np.random.randint(2**64, size=1000*1000)

mtrand.pyx in mtrand.RandomState.randint
(numpy/random/mtrand/mtrand.c:16123)()

ValueError: high is out of bounds for int64

y me dije "bah, probablemente Jesús me va a perdonar 1 bit" :)​


>
> Ordenar mejora la compresión porque estamos reduciendo la entropía de
> los datos. En mi caso, si tengo 256000 valores diferentes, podrían
> ordenarse de 256000! maneras, un número de 1.4 millones de dígitos. Si
> de todas esas posibilidades me quedo exclusivamente con la versión
> ordenada numéricamente, me ahorro (por entropía) unos 4229911 bits
> (aproximación de Stirling del factorial). Es decir, un compresor
> perfecto comprimiría mis 8192000 bytes perfectamente aleatorios a
> 7663261 bytes. Una compresión teórica máxima del 6.45%. Si los datos son
> verdaderamente aleatorios y la única estructura que tenemos es que están
> ordenados, no podemos comprimir más que un 6.45%. Salvo error matemático
> por mi parte. (considerando 256000 valores de 256 bits aleatorios).
>
> Por tanto, insisto nuevamente, me centraría en buscar una estructura de
> datos que acceda al mínimo posible de páginas de RAM, no en comprimir,
> porque por la parte de compresión estoy limitado al 6.45% de un
> compresor ideal que no existe.
>
> Usemos la fórmula para analizar tu ejemplo. Un millón de valores son
> 1e6! de combinaciones de ordenación. Si me quedo solo con la variedad
> ordenada numéricamente, un compresor IDEAL podría ahorrar 18488874 bits.
> Tus datos ocupan 63 bits cada uno (no 64), así que en total suman
> 6300 bits. Con la compresión IDEAL salen 44511126 o 5563891 bytes.
> Como tú partes de 64 bits de mentirijillas y no 63 bits reales (jeje, te
> doy ventaja), el nivel de compresión máximo teórico cogiendo esos 64
> bits por elemento sería del 30.5%.
>

​Buena estimación.  Para ver que pasa con 64 bits he hecho la prueba fetén:

In [25]: b = np.random.randint(2**64, size=1000*1000, dtype=np.uint64)

In [26]: b.sort()

In [27]: %time len(blosc.compress(b))
CPU times: user 26.3 ms, sys: 0 ns, total: 26.3 ms
Wall time: 6.9 ms
Out[27]: 6324530

Lo cual nos deja la compresión en un ​21% (no 23% de 63 bits).  Usando el
codec más potente en blosc, el ztsd:

In [28]: %time len(blosc.compress(b, cname="zstd"))
CPU times: user 1.09 s, sys: 0 ns, total: 1.09 s
Wall time: 290 ms
Out[28]: 6050011

que representa el 25% de compresión (supongo que muy cerca del límite
teórico).



>
> La compresión que muestra blosc en ese mismo ejemplo es del 23%.
> Confieso que es una hazaña reseñable e inesperada y que mientras hacía
> las cuentas estaba nervioso por que la "práctica" contradijese la
> "teoría" matemática inviolable. A fin de cuentas yo soy ingeniero, no
> matemático :-).
>

​Bueno, mientras no se supere el límite teórico no hay ninguna 'hazaña'
reseñable ;)​


>
> > ​Probablemente ya lo habrás estudiado, pero con cosas como Cassandra o
> > HBase no podrías atacar estos problemas?​  Si éstos te parecen demasiado
> > 'pesados', a lo mejor un filesystem distribuido como Gluster
> > (https://en.wikipedia.org/wiki/Gluster) ayudaría.  Y si quieres más bajo
> > nivel todavía, qué tal un simple almacén de objetos? Hay un interesante
> > artículo sobre esto en:
> > https://www.digitalocean.com/community/tutorials/object-
> storage-vs-block-storage-services
> > (a mí me gusta la aproximación de Ceph en particular).
>
> La clave del asunto es que los nodos de almacenaje no corren ningún
> código especial. Imagina montar un sistema así con nodos tontos, simples
> almacenes de datos sin capacidad para ejecutar ningún tipo de código.
> Sus únicas operaciones son: escribir un objeto, leer un objeto y listar
> los objetos que almacena (de forma muy lenta, por cierto). Supón que tus
> nodos de almacenamiento son cosas como Google Drive o Dropbox, con una
> latencia estratosférica e incapacidad total para ejecutar ningún código
> más alla de GET, PUT, REMOVE o LIST.
>
> Los almacenes están completamente descoordinados y son TONTOS. Lo que yo
> tengo montado es la inteligencia que hay por encima que permite
> localizar y operar con los objetos A PESAR de que el almacenaje final no
> coopera. También la replicación y la verificación de la integridad de
> todo el sistema.
>
> Este proyecto tiene unos objetivos muy

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

2017-11-27 Por tema Jesus Cea 
On 27/11/17 21:38, Francesc Alted wrote:
>  En tu
> caso creí entender que ordenabas los valores de alguna manera, pero
> viendo los ratios que obtienes, y que son bastante más pobres que mi
> prueba, posiblemente no entiendo bien a que te refieres cuando dices
> 'ordenados'. ​

Ordeno los hashes de los bloques que tiene cada nodo. Esto tiene la
ventaja de que puedo hacer un MMAP de ese fichero y hacer un LOOKUP
directo mediante bisección. El problema de eso es que con 2000 páginas
por fichero, tengo que hacer 11 accesos a páginas diferentes. Los
primeros niveles muy posiblemente estén cacheados en RAM, pero los
niveles inferiores son aleatorios y poco cacheables. Muy lejos de los
dos accesos a páginas que me da un "cuckoo hash".

Otra ventajas de tener una lista ordenada de hashes es que operaciones
como la unión, la resta de conjuntos o la intersección son muy sencillos
y eficientes. Me basta con revisar un único elemento de cada conjunto y,
encima, en streaming secuencial. Eso les encanta a las cachés de la CPU :-).

Pasar eso a un "cuckoo hash" supone que, por ejemplo, una intersección,
una resta o una unión de conjuntos requieres dos accesos secuenciales y
un acceso aleatorio (en vez de dos accesos secuenciales). El acceso
aleatorio es costoso pero tolerable, y los "lookups" pasan de requerir
once accesos a páginas diferentes a requerir dos como mucho. La
complejidad en sí del algoritmo es pequeña.

La pregunta es... ¿Se puede hacer mejor?

-- 
Jesús Cea Avión _/_/  _/_/_/_/_/_/
j...@jcea.es - http://www.jcea.es/ _/_/_/_/  _/_/_/_/  _/_/
Twitter: @jcea_/_/_/_/  _/_/_/_/_/
jabber / xmpp:j...@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



signature.asc
Description: OpenPGP digital signature
___
Python-es mailing list
Python-es@python.org
https://mail.python.org/mailman/listinfo/python-es

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

2017-11-27 Por tema Jesus Cea 
On 27/11/17 21:38, Francesc Alted wrote:
> En tu
> caso creí entender que ordenabas los valores de alguna manera, pero
> viendo los ratios que obtienes, y que son bastante más pobres que mi
> prueba, posiblemente no entiendo bien a que te refieres cuando dices
> 'ordenados'. ​

Lo cierto es que puedes comprobarlo tú mismo:

>>> hashes = [sha256(b'%d' % i).digest() for i in range(256000)]
>>> hashes.sort()  # Ordeno los hashes
>>> b=blosc.compress(b''.join(hashes), typesize=32)
>>> len(b)
8045911
>>> 100*(1-8045911/(256000*32))
1.7833129882812493

1.78%. Clava a mis resultados con datos reales:

> Para quedarnos todos tranquilos, voy a ver mi caso real:
[...]> 1.7785873168091881
> 
> La compresión es del 1.78%.
-- 
Jesús Cea Avión _/_/  _/_/_/_/_/_/
j...@jcea.es - http://www.jcea.es/ _/_/_/_/  _/_/_/_/  _/_/
Twitter: @jcea_/_/_/_/  _/_/_/_/_/
jabber / xmpp:j...@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



signature.asc
Description: OpenPGP digital signature
___
Python-es mailing list
Python-es@python.org
https://mail.python.org/mailman/listinfo/python-es

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

2017-11-27 Por tema Jesus Cea 
On 27/11/17 21:38, Francesc Alted wrote:
> De todas maneras, lo que intentaba era hacer ver
> que una ordenación siempre suele aumentar el ratio de compresión.
> Aquí
> hay un ejemplo mejor de lo que quería decir:
> 
> In [40]: b = np.random.randint(2**63, size=1000*1000)

Estás usando 63 bits, no 64, pero vale :-)

Ordenar mejora la compresión porque estamos reduciendo la entropía de
los datos. En mi caso, si tengo 256000 valores diferentes, podrían
ordenarse de 256000! maneras, un número de 1.4 millones de dígitos. Si
de todas esas posibilidades me quedo exclusivamente con la versión
ordenada numéricamente, me ahorro (por entropía) unos 4229911 bits
(aproximación de Stirling del factorial). Es decir, un compresor
perfecto comprimiría mis 8192000 bytes perfectamente aleatorios a
7663261 bytes. Una compresión teórica máxima del 6.45%. Si los datos son
verdaderamente aleatorios y la única estructura que tenemos es que están
ordenados, no podemos comprimir más que un 6.45%. Salvo error matemático
por mi parte. (considerando 256000 valores de 256 bits aleatorios).

Por tanto, insisto nuevamente, me centraría en buscar una estructura de
datos que acceda al mínimo posible de páginas de RAM, no en comprimir,
porque por la parte de compresión estoy limitado al 6.45% de un
compresor ideal que no existe.

Usemos la fórmula para analizar tu ejemplo. Un millón de valores son
1e6! de combinaciones de ordenación. Si me quedo solo con la variedad
ordenada numéricamente, un compresor IDEAL podría ahorrar 18488874 bits.
Tus datos ocupan 63 bits cada uno (no 64), así que en total suman
6300 bits. Con la compresión IDEAL salen 44511126 o 5563891 bytes.
Como tú partes de 64 bits de mentirijillas y no 63 bits reales (jeje, te
doy ventaja), el nivel de compresión máximo teórico cogiendo esos 64
bits por elemento sería del 30.5%.

La compresión que muestra blosc en ese mismo ejemplo es del 23%.
Confieso que es una hazaña reseñable e inesperada y que mientras hacía
las cuentas estaba nervioso por que la "práctica" contradijese la
"teoría" matemática inviolable. A fin de cuentas yo soy ingeniero, no
matemático :-).

> ​Probablemente ya lo habrás estudiado, pero con cosas como Cassandra o
> HBase no podrías atacar estos problemas?​  Si éstos te parecen demasiado
> 'pesados', a lo mejor un filesystem distribuido como Gluster
> (https://en.wikipedia.org/wiki/Gluster) ayudaría.  Y si quieres más bajo
> nivel todavía, qué tal un simple almacén de objetos? Hay un interesante
> artículo sobre esto en:
> https://www.digitalocean.com/community/tutorials/object-storage-vs-block-storage-services
> (a mí me gusta la aproximación de Ceph en particular).

La clave del asunto es que los nodos de almacenaje no corren ningún
código especial. Imagina montar un sistema así con nodos tontos, simples
almacenes de datos sin capacidad para ejecutar ningún tipo de código.
Sus únicas operaciones son: escribir un objeto, leer un objeto y listar
los objetos que almacena (de forma muy lenta, por cierto). Supón que tus
nodos de almacenamiento son cosas como Google Drive o Dropbox, con una
latencia estratosférica e incapacidad total para ejecutar ningún código
más alla de GET, PUT, REMOVE o LIST.

Los almacenes están completamente descoordinados y son TONTOS. Lo que yo
tengo montado es la inteligencia que hay por encima que permite
localizar y operar con los objetos A PESAR de que el almacenaje final no
coopera. También la replicación y la verificación de la integridad de
todo el sistema.

Este proyecto tiene unos objetivos muy concretos. No pretende competir
con sistemas de almacenamiento distribuidos donde tienes el lujo de
ejecutar código en la máquina que te da el almacenamiento. En mi caso yo
no puedo ni siquiera confiar en que el almacenamiento no me mienta
descaradamente, como para entregarle alguna responsabilidad en la
gestión del sistema...

Mi sistema lleva funcionando años con una excelente trayectoria. A
medida que crece el espacio de almacenaje hay que evolucionar los
algoritmos. No por un tema específicamente de velocidad, que es buena
ahora mismo cuando no paginas, sino porque a medida que los índices
crecen y ocupan más, acabas paginando. El cambio a "cuckoo hashes"
reduciría mis necesidades de memoria respecto a la versión actual del
sistema a un tercio, aproximadamente. Es decir, con los recursos
actuales, puedo triplicar mi tamaño hasta volver a tropezarme con el
problema que empiezo a rozar ahora: paginar.

Ahora mismo estoy empezando a paginar en algunos momentos. Durante esos
"eventos", el rendimiento del sistema se va al garete y el problema
persiste durante dos o tres minutos por "evento". Reduciendo mis
necesidades de memoria a un tercio, puedo triplicar mi tamaño hasta que
vuelva a encontrarme en el mismo punto que estoy ahora, donde la
paginación "está empezando a molestar" (pero aún no es grave y supone
solo molestias esporádicas).

Con mi ritmo de crecimiento de los últimos años, esto me da unos dos o
tres años de vida,

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

2017-11-27 Por tema Francesc Alted 
2017-11-27 20:12 GMT+01:00 Jesus Cea :

> On 27/11/17 19:01, Francesc Alted wrote:
> > Sin embargo, antes de decidir si tu
> > conjunto comprime bien o no, nunca está de más hacer una prueba.  Lo que
> > me hacía pensar en que tus datos podrían ser comprimibles es
> > precisamente lo que decías de que los valores te llegaban ordenados, y
> > sé que eso puede afectar mucho al ratio de compresión.  Por ejemplo,
> > usando un conjunto de números aleatorios de 1 millón de enteros de 64
> > bits (en total 8 MB) se tiene:
>
> Estás siendo un poco tramposo, Francesc :-). En tu ejemplo, tus datos no
> ocupan 64 bits cada uno, ocupan 20 bits escasos. Además, como generas un
> millón de valores en el rango 0-99, la diferencia entre un valor y
> el siguiente es muy pequeño, incluso cero :-).


> Así no vale :-).
>
>

​Bueno, más que tramposo me faltaba información sobre la distribución de
tus datos; viendo que estás tratando con ​valores SHA256, ya veo de que
estamos hablando :)  De todas maneras, lo que intentaba era hacer ver que
una ordenación siempre suele aumentar el ratio de compresión.  Aquí hay un
ejemplo mejor de lo que quería decir:

In [40]: b = np.random.randint(2**63, size=1000*1000)

In [41]: %time len(blosc.compress(b))

CPU times: user 74.8 ms, sys: 2.2 ms, total: 77 ms

Wall time: 23 ms

Out[41]: 816
​ ​
# sin compresion​

In [42]: b.sort()

In [43]: %time len(blosc.compress(b))

CPU times: user 51.1 ms, sys: 1.93 ms, total: 53 ms

Wall time: 15.6 ms

Out[43]: 6165702
​   #
  hay compression​​

​En los dos casos los datos son aleatorios, pero en el segundo caso están
ordenados, y por tanto comprimen (un 23% de reducción en este caso,
bastante notable para datos pseudo-aleatorios como éste).  En tu caso creí
entender que ordenabas los valores de alguna manera, pero viendo los ratios
que obtienes, y que son bastante más pobres que mi prueba, posiblemente no
entiendo bien a que te refieres cuando dices 'ordenados'. ​


> Para quedarnos todos tranquilos, voy a ver mi caso real:
>
> >>> import blosc
> >>> # Eliminamos el número de versión y el hash final de integridad
> >>> data=open("", "rb").read()[1:-32]
> >>> len(data)
> 8041888
> >>> len(blosc.compress(data, typesize=32))
> 7898856
> >>> 100 * (1 - 7898856 / 8041888)
> 1.7785873168091881
>
> La compresión es del 1.78%. Es inferior al 3.3% de simplemente dividir
> la tabla en 256 tablas y eliminar el primer byte de cada valor en cada
> subtabla. Posiblemente se pueda llegar con facilidad al 3% con blosc
> usando prefiltros.
>

​Blosc usa el filtro de SHUFFLE por defecto, así que tus datos son
claramente *dificilmente comprimibles*.​


> Mis datos son verdaderamente aleatorios en sus 256 bits. Son el SHA256
> de bloques de datos cifrados con claves a azar. Más (pseudo)aleatorio
> imposible :-).
>
> Aplicar blosc a un filtro cuckoo donde los fingerprints son más pequeños
> (digamos, 32 bits) parece más prometedor, pero en ese caso los
> fingerprints no están ordenados, tendrán un orden aleatorio y tampoco
> los vas a poder comprimir. Por ejemplo:
>
> >>> b=np.random.randint(2**32, size=1000*1000)
> # NO HAGO EL 'SORT()' PORQUE EN UN FILTRO CUCKOO LOS FINGERPRINTS
> # ESTAN DESORDENADOS.
> >>> len(blosc.compress(b))
> 4018965
>
> Dado que los datos ocupan realmente 400 bytes, blocs los expande un
> 0.5%.
>
> Que conste que blosc me parece un proyecto espectacular. Sencillamente
> no parece aplicable en este caso.
>
> Dicho lo cual, las discusiones sobre algoritmos me encantan. Sigamos :-).
>
> De momento sigo pensando que lo mejor que puedo hacer es usar "hash
> cuckoo" con un posible "filtro cucko" con una pequeña tasa de falsos
> positivos para una parte concreta del proceso.
>
> Por si alguien se pregunta sobre el uso de todo esto, se trata de un
> sistema de localización de bloques de datos en un sistema de
> almacenamiento distribuido donde no puedes controlar dónde se almacena
> cada bloque, pero debes saber dónde está a la hora de buscarlo, o
> declarar taxativametne que ese bloque no existe en el sistema. No se
> controla dónde se guardan las cosas, no hay rebalanceo a posteriori ni
> tampoco puedes contar con meter inteligencia en los nodos de
> almacenamiento más allá de un WEBDAV para listar, leer y escribir
> bloques (inmutables).
>


> A la hora de localizar bloques podría tolerarse una pequeña tasa de
> falsos positivos, que te obligaría a buscar en dos servidores en vez de
> solo en uno. Molesto, pero tolerable. Pero hay otras tareas donde no
> puedo permitir falsos positivos, como es el caso de la replicación
> (salvo que los falsos positivos se aleatoricen y sean diferentes cada
> vez, aceptando que pueden ser necesario hacer varias replicaciones para
> asegurarnos de que realmente está todo replicado) o el control de
> integridad (verificar que no sobra ni falta ningún bloque en el sistema).
>

​Probablemente ya lo habrás estudiado, pero con cosas como Cassandra o
HBase no podrías atacar estos problemas?​

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

2017-11-27 Por tema Jesus Cea 
On 27/11/17 19:01, Francesc Alted wrote:
> Sin embargo, antes de decidir si tu
> conjunto comprime bien o no, nunca está de más hacer una prueba.  Lo que
> me hacía pensar en que tus datos podrían ser comprimibles es
> precisamente lo que decías de que los valores te llegaban ordenados, y
> sé que eso puede afectar mucho al ratio de compresión.  Por ejemplo,
> usando un conjunto de números aleatorios de 1 millón de enteros de 64
> bits (en total 8 MB) se tiene:

Estás siendo un poco tramposo, Francesc :-). En tu ejemplo, tus datos no
ocupan 64 bits cada uno, ocupan 20 bits escasos. Además, como generas un
millón de valores en el rango 0-99, la diferencia entre un valor y
el siguiente es muy pequeño, incluso cero :-).

Así no vale :-).

Para quedarnos todos tranquilos, voy a ver mi caso real:

>>> import blosc
>>> # Eliminamos el número de versión y el hash final de integridad
>>> data=open("", "rb").read()[1:-32]
>>> len(data)
8041888
>>> len(blosc.compress(data, typesize=32))
7898856
>>> 100 * (1 - 7898856 / 8041888)
1.7785873168091881

La compresión es del 1.78%. Es inferior al 3.3% de simplemente dividir
la tabla en 256 tablas y eliminar el primer byte de cada valor en cada
subtabla. Posiblemente se pueda llegar con facilidad al 3% con blosc
usando prefiltros.

Mis datos son verdaderamente aleatorios en sus 256 bits. Son el SHA256
de bloques de datos cifrados con claves a azar. Más (pseudo)aleatorio
imposible :-).

Aplicar blosc a un filtro cuckoo donde los fingerprints son más pequeños
(digamos, 32 bits) parece más prometedor, pero en ese caso los
fingerprints no están ordenados, tendrán un orden aleatorio y tampoco
los vas a poder comprimir. Por ejemplo:

>>> b=np.random.randint(2**32, size=1000*1000)
# NO HAGO EL 'SORT()' PORQUE EN UN FILTRO CUCKOO LOS FINGERPRINTS
# ESTAN DESORDENADOS.
>>> len(blosc.compress(b))
4018965

Dado que los datos ocupan realmente 400 bytes, blocs los expande un
0.5%.

Que conste que blosc me parece un proyecto espectacular. Sencillamente
no parece aplicable en este caso.

Dicho lo cual, las discusiones sobre algoritmos me encantan. Sigamos :-).

De momento sigo pensando que lo mejor que puedo hacer es usar "hash
cuckoo" con un posible "filtro cucko" con una pequeña tasa de falsos
positivos para una parte concreta del proceso.

Por si alguien se pregunta sobre el uso de todo esto, se trata de un
sistema de localización de bloques de datos en un sistema de
almacenamiento distribuido donde no puedes controlar dónde se almacena
cada bloque, pero debes saber dónde está a la hora de buscarlo, o
declarar taxativametne que ese bloque no existe en el sistema. No se
controla dónde se guardan las cosas, no hay rebalanceo a posteriori ni
tampoco puedes contar con meter inteligencia en los nodos de
almacenamiento más allá de un WEBDAV para listar, leer y escribir
bloques (inmutables).

A la hora de localizar bloques podría tolerarse una pequeña tasa de
falsos positivos, que te obligaría a buscar en dos servidores en vez de
solo en uno. Molesto, pero tolerable. Pero hay otras tareas donde no
puedo permitir falsos positivos, como es el caso de la replicación
(salvo que los falsos positivos se aleatoricen y sean diferentes cada
vez, aceptando que pueden ser necesario hacer varias replicaciones para
asegurarnos de que realmente está todo replicado) o el control de
integridad (verificar que no sobra ni falta ningún bloque en el sistema).

-- 
Jesús Cea Avión _/_/  _/_/_/_/_/_/
j...@jcea.es - http://www.jcea.es/ _/_/_/_/  _/_/_/_/  _/_/
Twitter: @jcea_/_/_/_/  _/_/_/_/_/
jabber / xmpp:j...@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



signature.asc
Description: OpenPGP digital signature
___
Python-es mailing list
Python-es@python.org
https://mail.python.org/mailman/listinfo/python-es

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

2017-11-27 Por tema Jesus Cea 
On 27/11/17 10:29, Francesc Alted wrote:
> 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).

En realidad la compresión es mínima y no compensa. Son valores
aleatorios de 256 bits. Aunque estén ordenados de forma numérica, la
ganancia es mínima.

Por ejemplo, un grupo típico tiene 256000 valores. Como cada valor tiene
256 bits, eso supone que cada fragmento de 1000 valores consecutivos
empieza con el mismo byte. Dividiendo esa tabla de 256000 valores en 256
tablas de 1000 valores cada una, ocupando cada entrada 31 bytes en vez
de 32 (porque el primer byte es implícito), la ganancia es de 32->31
bytes, es decir, apenas un 3%. Algo es algo, es verdad. Pero no sé si me
compensa picar código para ganar un 3%.

Además, si uso algo tipo "cuckoo hashing", no puedo aplicar esa
compresión en memoria, que es donde la necesitaría (para paginar lo
mínimo posible).

> Para las búsquedas puedes continuar usando hashes cuckoo,
> pero sólo guardando las claves, no los valores

Es cierto, no lo he explicado: Estoy usando esto para "conjuntos", no
para "diccionarios". Es decir, solo hay claves, no hay valores :). Pero
buen apunte para otra ocasión.

> clase de acceso de manera muy eficiente a través de la llamada
> `blosc_getitem()`

Valoré Blosc brevemente, pero considero que mis datos son
"incompresibles" en RAM. Estoy más interesado en la parte de la
estructura de datos a utilizar para que las búsquedas sean eficientes
considerando que tengo poca RAM, no hay localidad de acceso en las
búsquedas (los datos que se buscan son aleatorios y no hay correlación
entre ellos) y puedo necesitar paginar al SWAP. Por eso estoy tan
interesado en reducir al mínimo los accesos a páginas diferentes de 4096
bytes (La unidad de paginación). Los haskes cuckoo me garantizan un
máximo de dos accesos por búsqueda en el peor de los casos. Posiblemente
no sea mejorable y, básicamente me interesa que alguien me diga "pues
estás equivocado, Jesús, mírate el algoritmo XXX, que te garantiza un
único acceso a página".

De hecho en este caso existe una posibilidad más: Como los datos son
aleatorios y "bien repartidos", podría hacer una búsqueda "estimativa"
en plan: "me da en la nariz que el valor, si existe, está en esta zona"
y buscar directamente allí. Las búsquedas dentro de una página de 4096
bytes las considero "gratis". Lo que duele es la paginación. 4096 bytes
me dan para 128 entradas. Mirarlas una a una es "gratis" comparado con
tocar el disco duro.

Esto ya lo había pensado, pero lo cierto es que por necesidades del
sistema no puedo basarme en que los datos estén "bien repartidos". Ahora
mismo lo están, pero no es un requerimiento de diseño y puede no
cumplirse en el futuro. Necesito algo capaz de sobrevivir a "sesgos".

Otra posibilidad sería tener una tabla con el primer primer registro de
cada página de 4096 bytes. Es decir, 32 bytes por cada 128 registros
(4kbytes). Si mi conjunto tiene 256 entradas, son 2000 páginas de
4096 bytes. Puedo tener un índice de 2000 entradas (64000 bytes, 16
páginas de 4096 bytes). La búsqueda en el índice es binaria y podría
tocar 4 páginas, pero es razonable pensar que un índice de 64Kbytes sí
lo puedo mantener en RAM, incluso con un "MAP_LOCKED" o "mlock()".

Claro que el problema es que mis datos no miden 256000 entradas. Son
docenas de conjuntos, cada uno con 256000 entradas. No estamos hablando
de 64 kbytes en RAM para el índice, sino 64*número de conjuntos, y ese
numero de conjuntos va por los cientos y subiendo.

En fin, el asunto es engañosamente sencillo.

De momento va ganando el cuckoo hashing. Es una estructura sencilla y me
garantiza un máximo de dos accesos a página, por muy grandes o muy raros
que sean mis datos.

Mi esperanza es que alguien me sugiera algo mejor :-).

Para uno de los modos de uso del sistema, el que más me importa, estoy
valorando usar "filtros cuckoo", tolerando un pequeño nivel de falsos
positivos, del orden del UNO por millón. Sigo teniendo dos accesos por
búsqueda, pero como ahora la estructura es más pequeña es más factible
que el número de accesos al SWAP se reduzca (recordemos que lo que me
penaliza es la paginación, las búsquedas en memoria las considero
gratis). Esto complicaría ese caso de uso porque ahora podría tener
falsos positivos, lo que supone que una vez por millón de accesos voy a
ir a buscar el dato a un servidor, me va decir que no está ahí y luego
tengo que hacer un acceso al servidor "por defecto". Ese "error" es muy
costoso en recursos y tiempo, pero si solo ocurre una vez por millón de
accesos, el coste amortizado es bajo.

Decisiones, decisiones...

Gracias por responder, Francesc. Buen aporte.

-- 
Jesús Cea Avión _/_/  _/_/_/_/_/_/
j...@jcea.es - http://www.jcea.es/ _/_/_/_/  _/_/_/_/  _/_/
Twitter: @jcea

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

2017-11-27 Por tema 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 :

> 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 _/_/  _/_/_/_/_/_/
> j...@jcea.es - http://www.jcea.es/ _/_/_/_/  _/_/_/_/  _/_/
> Twitter: @jcea_/_/_/_/  _/_/_/_/_/
> jabber / xmpp:j...@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@python.org
> https://mail.python.org/mailman/listinfo/python-es
>
>


-- 
Francesc Alted
___
Python-es mailing list
Python-es@python.org
https://mail.python.org/mailman/listinfo/python-es

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

2017-11-26 Por tema 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 _/_/  _/_/_/_/_/_/
j...@jcea.es - http://www.jcea.es/ _/_/_/_/  _/_/_/_/  _/_/
Twitter: @jcea_/_/_/_/  _/_/_/_/_/
jabber / xmpp:j...@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



signature.asc
Description: OpenPGP digital signature
___
Python-es mailing list
Python-es@python.org
https://mail.python.org/mailman/listinfo/python-es