[Python-es] ¿Propuesta de algoritmo o estructura de datos para conjuntos aleatorios con pocos cambios?
Francesc Alted
faltet en gmail.com
Mar Nov 28 03:01:49 EST 2017
2017-11-27 23:37 GMT+01:00 Jesus Cea <jcea en jcea.es>:
> 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)
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
<ipython-input-8-43513dff6db1> in <module>()
----> 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
> 63000000 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 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, tiempo suficiente para un cambio tecnológico, para
> que el proyecto se vuelva irrelevante o para una rearquitectura.
>
> En realidad, hay muchas vías de escape, estoy lejos de tropezarme con un
> muro insalvable. Un "cuckoo hash" es un proyecto de dos tardes a cambio
> de dos o tres años de relax. Lo que estoy intentando es ver si algún
> compañero conoce un algoritmo mejor para invertir en él cinco tardes a
> cambio de la salvación eterna :-p
>
> Conozco Celph. De hecho uno de los nodos de almacenamiento de los que
> hablo corre Celph por debajo, pero no puedo permitirme el lujo de
> aprovecharme de ello. Ahora dime también cuánta memoria necesitas en el
> directorio CELPH para mapear cien millones de objetos. No me cabe en mi
> Raspberry PI con un gigabyte de RAM compartida con otros demonios :).
>
> Esta discusión está siendo muy interesante, Francesc. Sigamos :-).
>
> Centrémonos en la parte de acceso mínimo a páginas, ya que la parte de
> compresión es un dead-end en este caso concreto. Tengo blosc en mi
> arsenal para otros proyectos, puedes estar seguro de ello.
>
> Situación actual: con un cuckoo hash solo necesito el acceso a dos
> páginas de memoria en el peor de los casos, por cada "lookup". El tiempo
> de generación de los cuckoo hash es bastante irrelevante y se hace
> offline, no en cada escritura de objetos. Me da igual que tarde 15
> horas. Básicamente el terabyte de objetos más recientes se gestiona de
> otra manera diferente, que no describo en estos emails, el cuckoo hash
> es solo para los petabytes "fríos".
>
Vale, ahora ya veo tu caso de uso con más claridad. La verdad es que me
interesa mucho tu proyecto; si lo tienes en abierto nos podrías decir
dónde está? Me gustaría 'jugar' un poco :)
Francesc
>
> El objetivo es batir esas dos páginas de memoria por "lookup". ¿Ideas?.
>
> --
> 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
>
>
> _______________________________________________
> Python-es mailing list
> Python-es en python.org
> https://mail.python.org/mailman/listinfo/python-es
>
>
--
Francesc Alted
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://mail.python.org/pipermail/python-es/attachments/20171128/da8debb3/attachment.html>
Más información sobre la lista de distribución Python-es