Alternativas eficientes de memoria a los diccionarios de Python

En uno de mis proyectos paralelos actuales, estoy escaneando un texto mirando la frecuencia de los tríos de palabras. En mi primer bash, utilicé el diccionario predeterminado con tres niveles de profundidad. En otras palabras, topDict[word1][word2][word3] devuelve el número de veces que estas palabras aparecen 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, usaba algo así como 20 veces la memoria de solo almacenar los trillizos en un archivo de texto, lo que parece una sobrecarga de memoria demasiado grande.

Mi sospecha es que muchos de estos diccionarios se están creando con muchas más ranuras de las que realmente se usan, por lo que quiero reemplazar los diccionarios con otra cosa que sea más eficiente en memoria cuando se use de esta manera. Preferiría encarecidamente una solución que permita búsquedas de claves en la línea de los diccionarios.

Por lo que sé de estructuras de datos, un árbol de búsqueda binaria equilibrada que use algo como rojo-negro o AVL probablemente sería ideal, pero realmente preferiría no implementarlas yo mismo. Si es posible, preferiría seguir 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 añadir:

Gracias por las respuestas hasta el momento. Algunas de las respuestas hasta ahora han sugerido el uso de tuplas, que realmente no hicieron mucho por mí cuando condensé las dos primeras palabras en una tupla. Dudo en usar los tres como una clave, ya que quiero que sea fácil buscar las terceras 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 para escuelas . Los resultados de analizar las primeras mil páginas, por ejemplo, son algo así como 11MB para un archivo de texto donde cada línea es las tres palabras y la pestaña de conteo de todas las separadas. Almacenar el texto en el formato de diccionario que estoy usando ahora toma alrededor de 185MB. Sé que habrá una sobrecarga adicional para los punteros y otras cosas, pero la diferencia parece excesiva.

Algunas medidas. Tomé 10 MB de texto de libro electrónico gratuito y frecuencias de trigtwig calculadas, produciendo un archivo de 24 MB. El almacenamiento en diferentes estructuras de datos de Python tomó mucho espacio en kB, medido como RSS desde la ejecución de ps, donde d es un dict, las claves y las frecuencias son listas, y a, b, c, freq son los campos de un registro de trigtwig:

 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 manera eficiente de buscar un par (a, b); están listados solo porque otros los han sugerido (o variantes de ellos). (Me molesté en hacer esto porque las respuestas más votadas no fueron útiles, como muestra la tabla).

‘Matriz de pares’ es el esquema a continuación en mi respuesta original (“Comenzaría con la matriz con las primeras dos palabras …”), donde la tabla de valores para cada par se representa como una sola cadena. La “matriz de pares comprimidos” es la misma, omitiendo los valores de frecuencia que son iguales a 1 (el caso más común). ‘Matriz única comprimida’ es como una matriz de par comprimido, pero combina clave y valor como una sola cadena (con un carácter separador). El código de matriz única exprimido:

 import collections def build(file): pairs = collections.defaultdict(list) for line in file: # NB 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 (use bisect, como se menciona a continuación), ni he implementado las estructuras comprimidas más sofisticadas que también se describen a continuación.

Respuesta original: merece la pena probar un simple conjunto ordenado de cadenas, cada cadena es una concatenación de palabras separadas por espacios, buscadas con el módulo bisect, para comenzar. Esto ahorra espacio en los punteros, etc. Todavía desperdicia espacio debido a la repetición de palabras; hay un truco estándar para eliminar los prefijos comunes, con otro nivel de índice para recuperarlos, pero eso es bastante más complejo y lento. (La idea es almacenar los fragmentos sucesivos de la matriz en una forma comprimida que debe analizarse secuencialmente, junto con un índice de acceso aleatorio a cada fragmento. Los trozos son lo suficientemente grandes para comprimir, pero lo suficientemente pequeños para un tiempo de acceso razonable. La compresión en particular esquema aplicable aquí: si las entradas sucesivas son ‘hola george’ y ‘hola mundo’, 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, puede encontrar más información en este sentido buscando estructuras de diccionario utilizadas en la búsqueda de texto completo. Así que, específicamente, comenzaría con la matriz con las primeras dos palabras, con una matriz paralela cuyas entradas enumeran las posibles Terceras palabras y sus frecuencias. Sin embargo, aún podría apestar, creo que puede que no tenga mucha suerte en cuanto a las opciones de ahorro de memoria que incluyen las baterías.

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 en un problema similar (unigrams en lugar de trigrams) y encuentra una tabla hash para vencer a todas las estructuras de árbol según 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 bigtwigs o trigtwigs; luego, para su estructura de datos ‘real’, sea cual sea, use claves de números enteros en lugar de cadenas, índices en la lista de palabras. (Pero esto le impide explotar los prefijos comunes, excepto en la lista de palabras. Tal vez no debería sugerir esto después de todo).

Usa las 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 un plus, 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” que están mezcladas con (word1, word2), búsquelo en dictionary.keys () usando la comprensión de lista

Si tienes una tupla, t, puedes obtener los primeros dos artículos usando cortes:

 >>> 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 elementos que aparecen como el tercer elemento en las tuplas que comienzan con (1,2)

En este caso, ZODB ¹ BTrees puede ser útil, ya que tienen mucha menos memoria. Use un BTrees.OOBtree (Claves de objeto a valores de objeto) o BTrees.OIBTree (Claves de objeto a valores de 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 un dict, con la ventaja adicional (para usted) de que .keys , .items , .iterkeys y .iteritems tienen dos argumentos opcionales min, max .

 >>> 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 las versiones más recientes de Python, pero no puedo recordar dónde.

PS Existen en el CheeseShop ☺

Una pareja intenta:

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.

Cambiando el almacenamiento a

 h[a, b, c] = 1 

toma ~ 25MB

interning a, b, yc hace que tome aproximadamente 31MB. Mi caso es un poco especial porque mis palabras nunca se repiten en la entrada. Puede probar algunas variaciones usted mismo y ver si alguno de estos le ayuda.

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

Si sus cadenas asignan 2 palabras a las probabilidades del tercero, usaría un diccionario que asigna K-tuplas al histogtwig de 3a palabra. Una forma trivial (pero con hambre de memoria) de implementar el histogtwig sería usar una lista con repeticiones, y luego random.choice le da una palabra con la probabilidad adecuada.

Aquí hay una implementación con el K-tuple 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,) 

Podrías intentar usar el mismo diccionario, solo un nivel de profundidad.

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

El delimitador podría ser simple “”. (o uso (word1, word2, word3))

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

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

Para obtener eficiencia de memoria, debe subdividir ese espacio en subespacios con un número similar de entradas. (como un BTree). Así que una estructura de datos con:

  • firstWordRange
  • secondWordRange
  • tercer rango de palabras
  • número de entradas
  • Un bloque ordenado de entradas.
  • Bloques siguientes y anteriores en las 3 dimensiones.

Aquí hay una estructura de árbol que usa la biblioteca bisect 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 utiliza un valor ficticio en cada árbol y lista. Esto guarda interminables 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 sentencias if se desperdician para todas las otras n- 1 palabras.

Scipy tiene matrices dispersas, así que si puedes hacer que las primeras dos 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 

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

Podrías usar una matriz multidimensional numpy. Necesitará usar números en lugar de cadenas para indexar en la matriz, pero eso se puede resolver usando un solo dictado para asignar palabras a números.

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

Luego, para indexar en tu matriz, harías algo como:

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

Esa syntax no es hermosa, pero las matrices numpy son tan eficientes como cualquier cosa que puedas encontrar. Tenga en cuenta también que no he probado este código, por lo que es posible que no esté en algunos de los detalles. Sólo voy de memoria aquí.

Podrías poner todas las palabras en un diccionario. clave sería palabra y valor es número (índice).

Entonces lo usas 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)