data - Alternativas de memoria eficiente a los diccionarios de Python

malloc free en python

Question

En uno de mis proyectos paralelos actuales, estoy escaneando algunos textos que miran la frecuencia de trillizos de palabras. En mi primer intento, utilicé el diccionario predeterminado tres niveles de profundidad. En otras palabras, topDict[word1][word2][word3] devuelve el número de veces que aparecen estas palabras en el texto, topDict[word1][word2] devuelve un diccionario con todas las palabras que aparecen después de las palabras 1 y 2, etc.

Esto funciona correctamente, pero requiere mucha memoria. En mis pruebas iniciales, utilizó algo así como 20 veces la memoria de simplemente almacenar los trillizos en un archivo de texto, lo que parece una gran cantidad de memoria sobrecarga.

Mi sospecha es que muchos de estos diccionarios se están creando con muchos más espacios que en realidad se están utilizando, por lo que quiero reemplazar los diccionarios con otra cosa que sea más eficiente desde el punto de vista de la memoria cuando se utiliza de esta manera. Preferiría mucho una solución que permita búsquedas clave a lo largo de las líneas de los diccionarios.

Por lo que sé de las estructuras de datos, un árbol de búsqueda binaria equilibrado que use algo como rojo-negro o AVL probablemente sería ideal, pero realmente preferiría no implementarlo yo mismo. Si es posible, preferiría quedarme con las bibliotecas estándar de Python, pero definitivamente estoy abierto a otras alternativas si funcionan mejor.

Entonces, ¿alguien tiene alguna sugerencia para mí?

Editado para agregar:

Gracias por las respuestas hasta el momento. Algunas de las respuestas hasta ahora han sugerido el uso de tuplas, que realmente no me ayudó mucho cuando condensé las dos primeras palabras en una tupla. Dudo en utilizar los tres como clave, ya que quiero que sea fácil buscar todas las palabras de los dos primeros. (es decir, quiero algo como el resultado de topDict[word1, word2].keys() ).

El conjunto de datos actual con el que estoy jugando es la versión más reciente de Wikipedia For Schools . Los resultados de analizar las primeras mil páginas, por ejemplo, son algo así como 11 MB para un archivo de texto en el que cada línea es de tres palabras y se separa la pestaña de conteo total. Almacenar el texto en el formato de diccionario Ahora estoy usando tomas de alrededor de 185MB. Sé que habrá una sobrecarga adicional para los punteros y otras cosas, pero la diferencia parece excesiva.

Answer 1

¿Estás implementando la generación de texto Markovian?

Si tus cadenas asignan 2 palabras a las probabilidades de la tercera, usaría un diccionario mapeando K-tuplas al histograma de 3ª palabra. Una forma trivial (pero hambrienta de memoria) de implementar el histograma sería usar una lista con repeticiones, y luego random.choice te da una palabra con la probabilidad adecuada.

Aquí hay una implementación con la K-tupla como parámetro:

import random

# can change these functions to use a dict-based histogram
# instead of a list with repeats
def default_histogram():          return []
def add_to_histogram(item, hist): hist.append(item)
def choose_from_histogram(hist):  return random.choice(hist)

K=2 # look 2 words back
words = ...
d = {}

# build histograms
for i in xrange(len(words)-K-1):
  key = words[i:i+K]
  word = words[i+K]

  d.setdefault(key, default_histogram())
  add_to_histogram(word, d[key])

# generate text
start = random.randrange(len(words)-K-1)
key = words[start:start+K]
for i in NUM_WORDS_TO_GENERATE:
  word = choose_from_histogram(d[key])
  print word,
  key = key[1:] + (word,)

Answer 2

Algunas medidas Tomé 10MB de texto libre de e-book y frecuencias de trigram calculadas, produciendo un archivo de 24MB. Almacenarlo en diferentes estructuras de datos simples de Python tomó tanto espacio en kB, medido como RSS desde correr ps, donde d es un dict, keys y freqs son listas, y a, b, c, freq son los campos de un trigram record:

295760     S. Lott''s answer
237984     S. Lott''s with keys interned before passing in
203172 [*] d[(a,b,c)] = int(freq)
203156     d[a][b][c] = int(freq)
189132     keys.append((a,b,c)); freqs.append(int(freq))
146132     d[intern(a),intern(b)][intern(c)] = int(freq)
145408     d[intern(a)][intern(b)][intern(c)] = int(freq)
 83888 [*] d[a+'' ''+b+'' ''+c] = int(freq)
 82776 [*] d[(intern(a),intern(b),intern(c))] = int(freq)
 68756     keys.append((intern(a),intern(b),intern(c))); freqs.append(int(freq))
 60320     keys.append(a+'' ''+b+'' ''+c); freqs.append(int(freq))
 50556     pair array
 48320     squeezed pair array
 33024     squeezed single array

Las entradas marcadas con [*] no tienen una forma eficiente de buscar un par (a, b); están listados solo porque otros los han sugerido (o variantes de ellos). (Me molestó bastante hacer esto porque las respuestas mejor votadas no fueron útiles, como lo muestra la tabla).

''Pair array'' es el siguiente esquema en mi respuesta original ("Comenzaría con la matriz con las dos primeras palabras ..."), donde la tabla de valores para cada par se representa como una sola cadena. ''Arreglo de par comprimido'' es el mismo, dejando fuera los valores de frecuencia que son 1 (el caso más común). ''Squeezed single array'' es como una matriz de pares comprimidos, pero combina la clave y el valor juntos como una cadena (con un carácter de separación). El código de matriz única exprimido:

import collections

def build(file):
    pairs = collections.defaultdict(list)
    for line in file:  # N.B. file assumed to be already sorted
        a, b, c, freq = line.split()
        key = '' ''.join((a, b))
        pairs[key].append(c + '':'' + freq if freq != ''1'' else c)
    out = open(''squeezedsinglearrayfile'', ''w'')
    for key in sorted(pairs.keys()):
        out.write(''%s|%s/n'' % (key, '' ''.join(pairs[key])))

def load():
    return open(''squeezedsinglearrayfile'').readlines()

if __name__ == ''__main__'':
    build(open(''freqs''))

No he escrito el código para buscar valores de esta estructura (uso de bisect, como se menciona a continuación) o implementado las estructuras comprimidas más elegantes también descritas a continuación.

Respuesta original: una secuencia ordenada simple de cadenas, cada cadena que es una concatenación de palabras separada por espacios, buscada usando el módulo bisect, debería valer la pena intentarlo para empezar. Esto ahorra espacio en los punteros, etc. Todavía desperdicia espacio debido a la repetición de las palabras; hay un truco estándar para eliminar prefijos comunes, con otro nivel de índice para recuperarlos, pero eso es bastante más complejo y más lento. (La idea es almacenar trozos sucesivos de la matriz en una forma comprimida que debe escanearse secuencialmente, junto con un índice de acceso aleatorio para cada fragmento. Los trozos son lo suficientemente grandes como para comprimirlos, pero lo suficientemente pequeños para un tiempo de acceso razonable. esquema aplicable aquí: si las entradas sucesivas son ''hello george'' y ''hello world'', haga que la segunda entrada sea ''6world'' en su lugar. (6 es la longitud del prefijo en común.) ¿O tal vez podría salirse con la suya usando zlib ? De todos modos, puedes encontrar más en este sentido buscando las estructuras de los diccionarios que se usan en la búsqueda de texto completo. Así que específicamente, comenzaría con la matriz con las dos primeras palabras, con una matriz paralela cuyas entradas enumeran la posible Terceras palabras y sus frecuencias. Sin embargo, todavía podría ser una mierda, creo que puede que no tenga suerte en cuanto a las baterías, incluidas las opciones de ahorro de memoria.

Además, las estructuras de árbol binario no se recomiendan para la eficiencia de la memoria aquí. Por ejemplo, este documento prueba una variedad de estructuras de datos sobre un problema similar (sin embargo, unigrams en lugar de trigrams) y encuentra una tabla hash para vencer todas las estructuras del árbol por esa medida.

Debería haber mencionado, como lo hizo otra persona, que la matriz ordenada podría usarse solo para la lista de palabras, no para bigramas o trigramas; luego, para su estructura de datos "real", sea lo que sea, utiliza claves enteras en lugar de cadenas, índices en la lista de palabras. (Pero esto le impide explotar prefijos comunes, excepto en la lista de palabras en sí. Tal vez no debería sugerir esto después de todo).

Answer 3

Aquí hay una estructura de árbol que usa la biblioteca de bisección para mantener una lista ordenada de palabras. Cada búsqueda en O (log2 (n)).

import bisect

class WordList( object ):
    """Leaf-level is list of words and counts."""
    def __init__( self ):
        self.words= [ (''/xff-None-'',0) ]
    def count( self, wordTuple ):
        assert len(wordTuple)==1
        word= wordTuple[0]
        loc= bisect.bisect_left( self.words, word )
        if self.words[loc][0] != word:
            self.words.insert( loc, (word,0) )        
        self.words[loc]= ( word, self.words[loc][1]+1 )
    def getWords( self ):
        return self.words[:-1]

class WordTree( object ):
    """Above non-leaf nodes are words and either trees or lists."""
    def __init__( self ):
        self.words= [ (''/xff-None-'',None)  ]
    def count( self, wordTuple ):
        head, tail = wordTuple[0], wordTuple[1:]
        loc= bisect.bisect_left( self.words, head )
        if self.words[loc][0] != head:
            if len(tail) == 1:
                newList= WordList()
            else:
                newList= WordTree()
            self.words.insert( loc, (head,newList) )
        self.words[loc][1].count( tail )
    def getWords( self ):
        return self.words[:-1]

t = WordTree()
for a in ( (''the'',''quick'',''brown''), (''the'',''quick'',''fox'') ):
    t.count(a)

for w1,wt1 in t.getWords():
    print w1
    for w2,wt2 in wt1.getWords():
        print " ", w2
        for w3 in wt2.getWords():
            print "  ", w3

Para simplificar, esto usa un valor ficticio en cada árbol y lista. Esto ahorra infinitas declaraciones if para determinar si la lista estaba realmente vacía antes de hacer una comparación. Solo está vacío una vez, por lo que las declaraciones if se desperdician para todas las n -1 palabras.

Answer 4

En este caso, ZODB ¹ BTrees podría ser útil, ya que están mucho menos hambrientos de memoria. Utilice un BTrees.OOBtree (Claves de objeto para valores de objeto) o BTrees.OIBTree (Claves de objeto para valores enteros), y use tuplas de 3 palabras como su clave.

Algo como:

from BTrees.OOBTree import OOBTree as BTree

La interfaz es, más o menos, similar a dict, con la ventaja añadida (para ti) de que .keys , .items , .iterkeys y .iteritems tienen dos argumentos .iteritems min, max opcionales:

>>> t=BTree()
>>> t[''a'', ''b'', ''c'']= 10
>>> t[''a'', ''b'', ''z'']= 11
>>> t[''a'', ''a'', ''z'']= 12
>>> t[''a'', ''d'', ''z'']= 13
>>> print list(t.keys((''a'', ''b''), (''a'', ''c'')))
[(''a'', ''b'', ''c''), (''a'', ''b'', ''z'')]

¹ Tenga en cuenta que si está en Windows y trabaja con Python> 2.4, sé que hay paquetes para versiones más recientes de Python, pero no puedo recordar dónde.

PD: existen en la CheeseShop ☺

Answer 5

Ok, entonces básicamente estás tratando de almacenar un espacio 3D disperso. El tipo de patrones de acceso que desea para este espacio es crucial para la elección del algoritmo y la estructura de datos. Teniendo en cuenta su fuente de datos, ¿desea alimentar esto a una grilla? Si no necesita acceso O (1):

Para obtener la eficacia de la memoria, debe subdividir ese espacio en subespacios con un número similar de entradas. (como un BTree). Entonces una estructura de datos con:

• firstWordRange
• secondWordRange
• thirdWordRange
• número de entradas
• un bloque de entradas ordenadas.
• bloques siguiente y anterior en las 3 dimensiones

Answer 6

Podría tratar de usar el mismo diccionario, solo un nivel de profundidad.

topDictionary[word1+delimiter+word2+delimiter+word3]

delimiter podría ser simple "". (o uso (palabra1, palabra2, palabra3))

Esto sería más fácil de implementar. Creo que verán una pequeña mejora, si no es suficiente ... ... pensaré en algo ...

Answer 7

Podría usar una matriz multidimensional numpy. Tendrá que usar números en lugar de cadenas para indexar en la matriz, pero eso se puede resolver usando una única dicción para asignar palabras a los números.

import numpy
w = {''word1'':1, ''word2'':2, ''word3'':3, ''word4'':4}
a = numpy.zeros( (4,4,4) )

Luego, para indexar en su matriz, haría algo como:

a[w[word1], w[word2], w[word3]] += 1

Esa sintaxis no es hermosa, pero los arreglos numpy son casi tan eficientes como cualquier cosa que puedas encontrar. Tenga en cuenta también que no he probado este código, por lo que puede estar apagado en algunos de los detalles. Solo voy de memoria aquí.

Answer 8

Podrías poner todas las palabras en un diccionario. la clave sería word, y value es number (index).

Entonces lo usa así:

Word1=indexDict[word1]
Word2=indexDict[word2]
Word3=indexDict[word3]

topDictionary[Word1][Word2][Word3]

Insertar en indexDict con:

if word not in indexDict:
    indexDict[word]=len(indexDict)

Answer 9

Scipy tiene matrices dispersas, así que si puedes hacer que las dos primeras palabras sean una tupla, puedes hacer algo como esto:

import numpy as N
from scipy import sparse

word_index = {}
count = sparse.lil_matrix((word_count*word_count, word_count), dtype=N.int)

for word1, word2, word3 in triple_list:
    w1 = word_index.setdefault(word1, len(word_index))
    w2 = word_index.setdefault(word2, len(word_index))
    w3 = word_index.setdefault(word3, len(word_index))
    w1_w2 = w1 * word_count + w2
    count[w1_w2,w3] += 1

Answer 10

Si la memoria simplemente no es lo suficientemente grande, pybsddb puede ayudar a almacenar un mapa persistente en el disco.

Answer 11

Un par de intentos:

Me imagino que estás haciendo algo similar a esto:

from __future__ import with_statement

import time
from collections import deque, defaultdict

# Just used to generate some triples of words
def triplegen(words="/usr/share/dict/words"):
    d=deque()
    with open(words) as f:
        for i in range(3):
            d.append(f.readline().strip())

        while d[-1] != '''':
            yield tuple(d)
            d.popleft()
            d.append(f.readline().strip())

if __name__ == ''__main__'':
    class D(dict):
        def __missing__(self, key):
            self[key] = D()
            return self[key]
    h=D()
    for a, b, c in triplegen():
        h[a][b][c] = 1
    time.sleep(60)

Eso me da ~ 88MB.

Cambiar el almacenamiento a

h[a, b, c] = 1

toma ~ 25MB

las prácticas a, byc hacen que tome alrededor de 31MB. Mi caso es un poco especial porque mis palabras nunca se repiten en la entrada. Puede intentar algunas variaciones usted mismo y ver si alguno de estos le ayuda.

Answer 12

Usa tuplas
Las tuplas pueden ser claves para los diccionarios, por lo que no es necesario anidar diccionarios.

d = {}
d[ word1, word2, word3 ] = 1

También como una ventaja, podrías usar defaultdict

• para que los elementos que no tienen entradas siempre devuelvan 0
• y para que pueda decir d[w1,w2,w3] += 1 sin verificar si la clave ya existe o no

ejemplo:

from collections import defaultdict
d = defaultdict(int)
d["first","word","tuple"] += 1

Si necesita encontrar todas las palabras "word3" con tuplas (word1, word2) luego búscalas en dictionary.keys () usando list comprehension

si tiene una tupla, t, puede obtener los dos primeros elementos usando rebanadas:

>>> a = (1,2,3)
>>> a[:2]
(1, 2)

un pequeño ejemplo para buscar tuplas con listas de comprensión:

>>> b = [(1,2,3),(1,2,5),(3,4,6)]
>>> search = (1,2)
>>> [a[2] for a in b if a[:2] == search]
[3, 5]

Usted ve aquí, tenemos una lista de todos los artículos que aparecen como el tercer elemento en las tuplas que comienzan con (1,2)