Python: Reduciendo el uso de memoria del diccionario

Estoy tratando de cargar un par de archivos en la memoria. Los archivos tienen cualquiera de los siguientes 3 formatos:

  • string TAB int
  • flotador de tabulación de cadena
  • int TAB float.

De hecho, son archivos ngram statics, en caso de que esto ayude con la solución. Por ejemplo:

i_love TAB 10
love_you TAB 12

Actualmente, el pseudocódigo de I'm doing right now es

loadData(file):
     data = {}
     for line in file:
        first, second = line.split('\t')
        data[first] = int(second) #or float(second)

     return data

Para gran sorpresa mía, mientras que el tamaño total de los archivos en disco es de aproximadamente 21 mb, cuando se cargan en memoria el proceso toma 120-180 mb de memoria! (toda la aplicación python no carga ningún otro dato en la memoria).

Hay menos de 10 archivos, la mayoría de ellos permanecerían estables en aproximadamente 50-80k líneas, excepto por un archivo que actualmente tiene millones de líneas.

Así que me gustaría pedir una técnica / estructura de datos para reducir el consumo de memoria:

  • ¿Algún consejo para las técnicas de compresión?
  • Si todavía uso dict, ¿hay alguna manera de reducir la la memoria? ¿Es posible establecer el" factor de carga " como en Java para Python dict?
  • Si usted tiene algunas otras estructuras de datos, 'm también dispuesto a negociar parte de la velocidad para reducir la memoria. Sin embargo, esta es una aplicación sensible al tiempo, por lo que una vez que los usuarios ingresan sus consultas, creo que no sería del todo razonable tardar más de unos segundos en devolver el resultado. Con respecto a esto, todavía estoy sorprendido por cómo Google logra hacer el Traductor de Google tan rápido: deben estar usando mucho de técnicas + mucha potencia de los servidores?

Muchas Gracias. Espero con interés su consejo.

Author: Paul Hoang, 2012-04-22
Source

6 answers

No puedo ofrecer una estrategia completa que ayude a mejorar la huella de memoria, pero creo que puede ayudar a analizar qué es exactamente lo que está tomando tanta memoria.

Si nos fijamos en la implementación de Python de dictionary (que es una implementación relativamente directa de una tabla hash), así como la implementación de los tipos de datos string y integer integrados, por ejemplo aquí (específicamente object.h, intobject.h, stringobject.h y dictobject.h, así como la correspondiente *.c archivos en ../ Objects), puede calcular con cierta precisión los requisitos de espacio esperados:

  1. Unentero es un objeto de tamaño fijo, es decir, contiene un recuento de referencia, un puntero de tipo y el entero real, en total típicamenteal menos 12 bytes en un sistema de 32 bits y24 bytes en un sistema de 64 bits, sin tener en cuenta el espacio adicional que posiblemente se pierda a través de la alineación.

  2. Un objeto string es de tamaño variable, lo que significa que contiene

    • recuento de referencia
    • puntero de tipo
    • información de tamaño
    • espacio para el código hash calculado perezosamente
    • state information (e. g. used for interned strings)
    • un puntero al contenido dinámico

    En total al menos 24 bytes en 32bit o 60 bytes en 64bit, sin incluir espacio para la cadena en sí.

  3. El diccionario mismo consta de un número de cubos, cada uno conteniendo

    • el código hash del objeto actualmente almacenado (que no es predecible desde la posición del bucket debido a la estrategia de resolución de colisiones utilizada)
    • un puntero al objeto clave
    • un puntero al objeto value

    En total al menos 12 bytes en 32bit y 24 bytes en 64bit.

  4. El diccionario comienza con 8 cubos vacíos y es redimensionado por duplicar el número de entradas cada vez que se alcanza su capacidad.

Realicé una prueba con una lista de 46,461 cadenas únicas (337,670 bytes de tamaño de cadena concatenado), cada una asociada con un entero - similar a su configuración, en una máquina de 32 bits. De acuerdo con el cálculo anterior, esperaría una huella de memoria mínima de

  • 46,461 * (24+12) bytes = 1.6 MB para las combinaciones string/integer
  • 337,670 = 0.3 MB para la cadena índice
  • 65,536 * 12 bytes = 1.6 MB para los cubos de hash (después de redimensionar 13 veces)

En total 2,65 MB. (Para un sistema de 64 bits el cálculo correspondiente produce 5.5 MB.)

Cuando se ejecuta el intérprete de Python idle, su huella de acuerdo con la herramienta ps es de 4.6 MB. Por lo tanto, el consumo total de memoria esperado después de crear el diccionario es aproximadamente 4.6 + 2.65 = 7.25 MB. La huella de memoria verdadera (según ps) en mi prueba fue 7,6 MB. Supongo que el ca extra. 0.35 MB fueron consumidos por la sobrecarga generada a través de la estrategia de asignación de memoria de Python(para arenas de memoria, etc.)

Por supuesto, muchas personas ahora señalarán que mi uso de ps para medir la huella de memoria es inexacto y mis suposiciones sobre el tamaño de los tipos de puntero y los enteros en sistemas de 32 bits y 64 bits pueden ser incorrectas en muchos sistemas específicos. Conceder.

Pero, sin embargo, las conclusiones clave , creo, son estos:

  • La implementación del diccionario Python consume una sorprendentemente pequeña cantidad de memoria
  • Pero el espacio ocupado por los muchos int y (en particular) string objects, para recuentos de referencia, códigos hash precalculados, etc., es más de lo que pensarías al principio
  • No hay apenas una manera de evitar la sobrecarga de memoria, siempre y cuando use Python y desee que las cadenas y los enteros se representen como objetos individuales-en al menos no veo cómo se podría hacer eso
  • Puede valer la pena buscar (o implementar usted mismo) una extensión Python-C que implemente un hash que almacene claves y valores como punteros C (en lugar de objetos Python). No se si eso existe; pero creo que se podría hacer y podría reducir la huella de memoria en más de la mitad.
 72
Author: jogojapan,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-04-22 05:11:57

1) SQLite en memoria suena como una gran solución, te permitirá consultar tus datos más fácilmente una vez que se cargue, lo cual es un placer

Sqlite3.conectar (': memoria:')

2) es probable que desee una tupla con nombre - Estoy bastante seguro de que son más ligeros que los diccionarios y puede acceder a las propiedades utilizando la notación de puntos (para la cual tengo una preferencia estética de todos modos).

Http://docs.python.org/dev/library/collections

3) es posible que desee echar un vistazo a Redis: https://github.com/andymccurdy/redis-py

Es RÁPIDO y le permitirá persistir las cosas fácilmente, lo que significa que no tiene que cargar todo el conjunto cada vez que desee usarlo.

4) un trie suena como una buena idea, pero añade cierta complejidad teórica al final del trabajo. Sin embargo, puede usar Redis para implementarlo y almacenarlo, lo que aumentará su velocidad aún más.

Pero en general, las tuplas nombradas son probablemente el truco aquí.

 8
Author: Moshe Bildner,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-08-22 14:56:27

En disco solo tiene cadenas, al cargar en Python el intérprete tiene que crear una estructura completa para cada cadena y para cada diccionario, además de la cadena en sí.

No hay forma de reducir la memoria utilizada por los dictados, pero hay otras formas de abordar el problema. Si está dispuesto a cambiar algo de velocidad por memoria, debería considerar almacenar y consultar las cadenas desde un archivo SQLite en lugar de cargar todo en diccionarios en memoria.

 6
Author: Pedro Werneck,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-04-22 03:31:11

Suena como un Trie ( http://en.m.wikipedia.org/wiki/Trie ) la estructura de datos podría adaptarse mejor a su deseo de eficiencia de memoria.

Actualización: la eficiencia de memoria de python dict ha sido planteada como un problema, aunque fue rechazada de la librería estándar dada la disponibilidad de bibliotecas de terceros. Véase: http://bugs.python.org/issue9520

 4
Author: Garrett,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-04-22 05:58:30

Puede reemplazar dict con blist.sorteddict para el acceso log(n) sin la sobrecarga de memoria. Es conveniente porque se comporta exactamente como un diccionario, es decir, implementa todos sus métodos, por lo que solo tiene que cambiar el tipo inicial.

 3
Author: ealfonso,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-10-29 18:47:17

Si está tratando de almacenar datos numéricos de forma compacta en python en la memoria, su mejor solución es probablemente Numpy.

Numpy ( http://numpy.org ) asigna estructuras de datos usando estructuras C nativas. La mayoría de sus estructuras de datos presumen que está almacenando un solo tipo de datos, por lo que esto no es para todas las situaciones (es posible que necesite almacenar null, etc.), pero puede ser muy, muy, muy rápido y es casi tan compacto como se podría pedir. Mucha ciencia se hace con él (véase también: SciPy).

Por supuesto, hay otra opción: zlib , si tienes:

  • Amplios ciclos de CPU, y
  • MUCHOS datos que no caben en la memoria

Simplemente podría declarar una 'página' de datos (por grande que desee) como una matriz, leer los datos, almacenarlos en la matriz, comprimirlos y luego leer algunos datos más, hasta que tenga todos los datos en la memoria que desee.

Luego, itere sobre las páginas, descomprima, convierta de nuevo a una matriz y realice sus operaciones según sea necesario. Por ejemplo:

def arrayToBlob(self, inArray):
    a = array.array('f', inArray)
    return a.tostring()

def blobToArray(self, blob, suppressWarning=False):
    try:
        out = array.array('f', [])
        out.fromstring(blob)
    except Exception, e:
        if not suppressWarning:
            msg = "Exception: blob2array, err: %s, in: %s" % (e, blob)
            self.log.warning(msg)
            raise Exception, msg
    return out

Una vez que tenga los datos como un blob, puede pasar este blob a zlib y comprimir los datos. Si tiene muchos valores repetidos, este blob puede comprimirse enormemente.

Por supuesto, es más lento que mantenerlo todo sin comprimir, pero si no puede caberlo en la memoria, sus opciones están limitadas para empezar.

Incluso con compresión, puede que no todo quepa en la memoria, momento en el que es posible que tenga que escribir las páginas comprimidas como cadenas o encurtidos, etc.

¡Buena suerte!

 3
Author: Kevin J. Rice,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-12-01 17:10:12