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 2560000 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 _/_/ _/_/ _/_/_/_/_/ 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
