Memoria eficientes mapa-cadena a cadena en Python (o C)

https://stackoverflow.com/questions/4026359

26-09-2019
|

Pregunta

Necesito una estructura de datos de memoria-eficiente para para el almacenamiento de aproximadamente un millón de clave - pares de valores, donde las claves son cadenas de alrededor de 80 bytes, y los valores son cadenas de alrededor de 200 bytes, la clave y el valor de tamaño total es aproximadamente 280MB . También necesito de búsqueda eficiente de valor mediante la llave, preferentemente un hash-mapa. La sobrecarga de la memoria debe ser tan poco como sea posible, por ejemplo, de 280MB de datos útiles, la estructura de datos no debe utilizar más de 300 MB de memoria virtual (incluidos los gastos generales malloc() y todo lo demás). El patrón de uso es el siguiente: comenzamos con una estructura de datos vacía y poblamos poco a poco, sin cambiar nunca teclas, y nunca cambiando la longitud de los valores. Como una ventaja, la estructura de datos puede soportar el cambio de la longitud de los valores, a expensas de un valor por encima del 100% (lo que significa que para bytes valor de x, x bytes podría sean consumidos en temporalmente en espacio de memoria intermedia no utilizado).

necesito un módulo de Python puro, o un módulo integrado en Python, o una aplicación C, preferiblemente con fijaciones (C) Python. Yo preferiría si era posible para serializar toda la estructura de datos en el disco, y para leer de nuevo muy rápidamente.

Sólo para demostrar que una pequeña sobrecarga es posible, he creado un diseño simple con direccionamiento abierto , la tabla de dispersión de 1,25 millones de elementos que contienen punteros de 4 bytes a bloques de datos de 1 MB, los bloques de datos que contienen las longitudes de clave y valor como base-128 varints . Este diseño tiene una limitación importante: no permite quitar o cambiar pares sin perder su área de memoria. Según mis cálculos con 1 millón de clave - pares de valores de 280 bytes cada uno, la sobrecarga es de menos de 3,6% (10 080 000 bytes). Los límites anteriores son más generoso, que permiten 20 000 000 bytes de sobrecarga.

Me acabo de encontrar http://www.pytables.org/ , que proporciona acceso rápido y embalaje de la memoria-eficiente de los datos. Tengo que examinar más de cerca para comprobar si se adapta a mis necesidades.

Solución 10

Como no podía encontrar las soluciones existentes que empacar firmemente la memoria, he decidido ponerlo en práctica en C para mí. Ver mi diseño con direccionamiento abierto en la pregunta.

Otros consejos

Ok, el enfoque de la suciedad simple.

El uso de un diccionario de Python para la estructura de datos. Llené un diccionario pitón con 1 millón de pares de clave y valor aleatorio donde la clave fue de 80 caracteres y el valor de 200 caracteres. Tomó 360 844 Kb en mi equipo, que está fuera de su especificación de no más de 300 MB, pero lo presento como una solución de todos modos porque todavía es bastante eficiente de memoria.

Esto también falla el requisito de tener una API C. No estoy seguro de por qué necesita C, pero a medida que la cuestión se marca Python y carece de una etiqueta C, voy a ofrecer el puro Python para ver si sólo podría caber la cuenta.

En cuanto a la persistencia. Utilice el módulo cPickle. Es muy rápido y, de nuevo, la suciedad simple. Para guardar el diccionario:

cPickle.dump(mydict, "myfile.pkl")

Para volver a cargar el diccionario:

mydict = cPickle.load("myfile.pkl")

Una segunda idea suciedad más sencilla es utilizar el módulo shelve, que es básicamente el diccionario de Python basado en disco. sobrecarga de la memoria es muy bajo (es todo en el disco). Pero también es mucho más lento.

Martijn mencionó esto en un comentario, (no sé por qué la gente comentario con respuestas) pero estoy de acuerdo: el uso de SQLite. Usted debe darle una oportunidad y ver si se adapta a sus necesidades.

Si no va a tener una gran cantidad de eliminaciones, entonces esto no es tan difícil. Elimina conducen a la fragmentación.

También es necesario comprometerse con una clave de longitud fija. Usted ha hablado de 80 bytes. Son sus llaves permite duplicar? Si no, es aún más fácil.

Así pues, aquí es lo que haces.

crear una matriz de:

struct {
    char value[80];
    char *data;
} key;

y continúa esta matriz ordenada.

Si teclas se pueden duplicar, entonces usted necesita:

struct link {
    char *data;
    link *next;
}

struct {
    char value[80];
    link *data;
} key;

(Mi C es oxidado, pero esta es la esencia de la misma) Este último tiene cada uno apuntando clave de una lista enlazada de valores.

A continuación, una búsqueda es una simple búsqueda binaria. El "dolor" es en el mantenimiento de esta matriz y la inserción / eliminación de claves. No es tan doloroso como suena, pero se ahorra una gran cantidad de memoria, especialmente en sistemas de 64 bits.

Lo que se quiere es reducir el número de punteros. Los punteros son caros cuando se tiene una gran cantidad de estructuras llenas de punteros. En un sistema de 64 bits, un puntero es de 8 bytes. Así que para un único puntero, ahí va 8 MB de memoria de su presupuesto.

Por lo tanto, el gasto es en la construcción de la matriz, copiar y compactación de la memoria (si "saber" que tendrá un millón de filas y puede comprometerse a que, a continuación, malloc (1000000 * sizeof (clave)) de inmediato, es ll ahorrar algo de copia durante la expansión).

Pero no tenga miedo de, una vez que esté en funcionamiento, el rendimiento es bastante bueno. CPU modernas son en realidad bastante bueno para copiar 100M bloques de memoria alrededor.

Como nota aparte, que acabo de hacer algo parecido a esto en Java. En una JVM de 64 bits, un mapa con las entradas 25M es 2G de memoria RAM. Mi solución (utilizando técnicas similares a este) tiene alrededor de 600 millones). Java utiliza más punteros que C, pero la premisa es la misma.

¿Ha intentado utilizar un diccionario sencillo? La mayoría de los datos están en cadenas, por lo que la sobrecarga podría encajar dentro de sus requisitos.

Puede utilizar el sha1 de la llave en lugar de la clave. Si las claves son únicas, entonces el hash sha1 de las claves es probable, también. Proporciona un ahorro de memoria para tratar de chillido en virtud de su límite.

from random import choice
from string import letters
from hashlib import sha1

def keygen(length):
    return "".join(choice(letters) for _ in xrange(length))

def gentestdata(n=1000*1000):
    # return dict((sha1(keygen(80)).digest(), keygen(200)) for _ in xrange(n))
    d = {}
    for _ in xrange(n):
        key = sha1(keygen(80)).digest()
        assert key not in d
        value = keygen(200)
        d[key] = value
    return d

if __name__ == '__main__':
    d = gentestdata()

En mi caja de Ubuntu, este alcanza un máximo de 304 MB de memoria:

2010-10-26 14:26:02 hbrown@hbrown-ubuntu-wks:~$ ps aux | grep python
[...]
hbrown   12082 78.2  7.5 307420 303128 pts/1   S+   14:20   4:47 python

Lo suficientemente cerca? Es pitón, no C.

Más tarde: También, si los datos es algo redundante, puede gzip los valores. Es un momento frente disyuntiva espacio.

El uso de SQLite es una idea buena. Una implementación rápida puede decir si usted es lo suficientemente rápido con poco esfuerzo.

Si determina que tiene que rodar su propia, recomiendo lo siguiente:

¿Qué tan bien se puede predecir el número de pares, o un límite superior para eso?
¿Qué tan bien se puede predecir el tamaño total de los datos, o un límite superior para eso?

Arena asignador para cuerdas y nudos. (Por lo general, usted trabajar en una lista de escenarios, por lo que no tiene que predecir el tamaño total).

La alineación depende de sus algoritmos, en principio se podía lo vuelven a byte apretado, y la única cabeza es su sobreasignación, que sólo mínimamente afecta a su conjunto de trabajo.

Sin embargo, si tiene que ejecutar cualquier cmp / copiar las operaciones etc., en estas cadenas, recordar que con las siguientes garantías, se puede exprimir un poco o mucho de estas operaciones de cadena:

todos los elementos están alineados palabra CPU
todos los bytes de relleno son (por ejemplo) 0
se puede leer de forma segura "más allá" de un extremo de la cuerda, siempre y cuando no se cruza una frontera de la CPU

tabla Hash para el índice. Un diccionario iba a funcionar, también, pero que tiene sentido sólo si el potencial de degradación / refrito sería un problema grave. Yo no conozco a ningún "reserva" aplicación tabla hash para C, pero no debería ser uno, ¿verdad? ¿Derecha? Basta con sustituir las asignaciones con las llamadas al asignador de arena.

Memoria Localidad

Si usted puede garantizar que las operaciones de búsqueda nunca se solicitará una cadena que no está en el mapa, se debe almacenar las claves en una arena por separado, ya que se necesitan sólo en las colisiones de condensación. Que pueden mejorar significativamente la localidad de memoria. (En ese caso, si alguna vez tiene una mesa de "final", incluso se podría copiar las claves chocan a una nueva arena, y tirar todos los demás. Los beneficios de los que probablemente son marginales, sin embargo.)

La separación puede ayudar o perjudicar, en función de sus patrones de acceso. Si normalmente utiliza el valor una vez después de cada búsqueda, tenerlos por pares en la misma arena es grande. Si, por ejemplo, mirar hacia arriba unas pocas teclas, a continuación, utilizar sus valores en repetidas ocasiones, arenas separadas tienen sentido.

Si usted tiene que apoyar "caracteres extraños" / Unicode, normalizar sus cadenas antes de almacenarlos.

Se podría utilizar módulo de estructura de paquete de datos binarios y descomprimirlo cuando sea necesario. Se puede implementar un almacenamiento eficiente de memoria utilizando este enfoque. Creo que el acceso sería un dolor.

http://docs.python.org/library/struct.html

Apache portátil Tiempo de ejecución (también conocido como APR) tiene una tabla hash basado en c. Se puede ver la documentación en http://apr.apache.org/docs/apr/ 0,9 / group_ abril _hash.html

Con apr_hash_t todo lo que tienda es void *. Por lo tanto, le da un control total sobre los valores. Así que si quiere puede almacenar puntero a un bloque de 100 bytes en lugar de la longitud real de la cadena.

Judy debe ser eficientes en la memoria: http://judy.sourceforge.net/
(Puntos de referencia: http://www.nothings.org/computer/judy/ , consulte " Estructura de datos Tamaño ").
Véase también: http://www.dalkescientific.com/Python/PyJudy.html

Además,

Para las claves de un tamaño fijo no es http://panthema.net/2007/stx-btree / en C ++ (estoy seguro de que con una costumbre encapsulamiento en C que se puede utilizar desde CPython). Si el conjunto de datos lo permite, se puede almacenar las claves de longitud variable en el valor y el uso de un hash o un prefijo de la clave de longitud variable como la clave de longitud fija.

La misma lógica se aplica a http://google-opensource.blogspot.ru/2013/01/c-containers-that-save-memory-and-time.html y http://code.google.com/p/sparsehash/ - Istead de usar una pesada std :: string como una clave, use una de 32 bits o la tecla de número entero de 64 bits, por lo que es de alguna manera de la clave de longitud variable real.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow