2017-11-27 20:12 GMT+01:00 Jesus Cea <[email protected]>:
> 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-999999, 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]: 8000016
# 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("XXXX", "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 4000000 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? 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).
Francesc
>
> --
> Jesús Cea Avión _/_/ _/_/_/ _/_/_/
> [email protected] - http://www.jcea.es/ _/_/ _/_/ _/_/ _/_/ _/_/
> Twitter: @jcea _/_/ _/_/ _/_/_/_/_/
> jabber / xmpp:[email protected] _/_/ _/_/ _/_/ _/_/ _/_/
> "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
> [email protected]
> https://mail.python.org/mailman/listinfo/python-es
>
>
--
Francesc Alted
_______________________________________________
Python-es mailing list
[email protected]
https://mail.python.org/mailman/listinfo/python-es
