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

[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-999999, 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("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.

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).

-- 
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

------------ próxima parte ------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 473 bytes
Desc: OpenPGP digital signature
URL: <http://mail.python.org/pipermail/python-es/attachments/20171127/b8eda0bc/attachment.sig>