Mémoire Alternatives Efficaces à Python Dictionnaires

Question

Dans l'un de mes projets, je suis d'analyse par l'intermédiaire du texte à la recherche à la fréquence de mot de triplets. Dans mon premier aller, j'ai utilisé le dictionnaire par défaut trois niveaux de profondeur. En d'autres termes, topDictionary[mot1][mot2][terme3] renvoie le nombre de fois où ces mots apparaissent dans le texte, topdictionary[mot1][mot2] retourne un dictionnaire avec tous les mots qui sont apparues à la suite des mots 1 et 2, etc.

Cela fonctionne correctement, mais il est très gourmande en mémoire. Dans mes premiers essais, il a utilisé quelque chose comme 20 fois la quantité de mémoire de juste le stockage de triplets dans un fichier texte, ce qui semble être une quantité trop importante de la surcharge de la mémoire.

Mon soupçon est que beaucoup de ces dictionnaires sont créés avec beaucoup plus de logements que sont réellement utilisées, alors je veux remplacer les dictionnaires avec quelque chose d'autre qui est plus de mémoire efficace lorsqu'il est utilisé de cette manière. Je vous recommande de préférer une solution qui permet à la clé des recherches le long de la lignes de dictionnaires.

De ce que je sais de structures de données, l'équilibre binaire de recherche de l'arbre à l'aide de quelque chose comme le rouge et le noir ou AVL serait probablement l'idéal, mais je préfère vraiment ne pas mettre en place moi-même. Si possible, je préfère rester avec les standards de python, des bibliothèques, mais je suis ouvert à d'autres solutions de rechange si elles fonctionnent le mieux.

Donc, quelqu'un aurait-il des suggestions pour moi?

Edité pour ajouter:

Merci pour les réponses à ce jour. Quelques réponses ont suggéré l'utilisation de n-uplets, qui n'a pas vraiment faire beaucoup pour moi, quand j'ai condensé les deux premiers mots dans un tuple. J'hésite à utiliser tous les trois comme une clé car je veux qu'il soit facile de rechercher tous les mots étant donné que les deux premiers. (c'est à dire je veux quelque chose comme le résultat de topDict[mot1,mot2].keys() ).

Le dataset actuel je joue avec la version la plus récente de Wikipédia Pour les Écoles. Les résultats de l'analyse du premier millier de pages, par exemple, est quelque chose comme 11MO pour un fichier texte où chaque ligne est les trois mots et le nombre de tous séparées par des tabulations. Stocker le texte dans le format du dictionnaire, je suis maintenant en utilisant prend environ 185MB. Je sais qu'il y aura des surcharges supplémentaires pour les pointeurs et autres joyeusetés, mais la différence semble excessif.

Encore une fois, merci à tous pour les réponses à ce jour.

Answer 1

Certaines mesures. J'ai pris 10 mo de e-book gratuit de texte et calculée trigramme fréquences, la production d'un 24 mo de fichier. De le stocker dans les différentes simples Python structures de données a pris cette quantité d'espace dans la base de connaissances, mesurée en tant que flux RSS de l'exécution de ps, où d est un dict, les clés et les freqs sont des listes, et a,b,c,freq sont les champs d'un trigramme enregistrement:

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

Les entrées marquées [*] n'ont pas de moyen efficace pour rechercher une paire (a,b); elles sont indiquées uniquement parce que d'autres ont suggéré (ou des variantes de ces derniers). (J'étais agacé de cette parce que le haut-voté réponses n'étaient pas utiles, comme le montre le tableau.)

Paire de matrice' est le schéma ci-dessous originale dans ma réponse ("je commencerais avec le tableau avec les clés étant les deux premiers mots..."), où le tableau de valeurs pour chaque paire est représentée comme une seule chaîne. 'Pressé paire array' est la même, en laissant de côté les valeurs de fréquence sont égaux à 1 (le plus commun cas). 'Pressé de tableau unique" est comme pressé paire de tableau, mais gloms clé et de la valeur ensemble comme une seule chaîne de caractères (avec un caractère de séparation). Le pressé de tableau unique code:

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'))

Je n'ai pas écrit le code pour rechercher des valeurs à partir de cette structure (utiliser coupent, comme mentionné ci-dessous), ou mis en œuvre l'amateur comprimé structures décrites ci-dessous.

Réponse originale à cette question: Un simple tableau trié de chaînes de caractères, chaque chaîne étant séparées par un espace de concaténation de mots, recherche en utilisant le traversent, module, devrait être la peine d'essayer, pour commencer. Cela permet d'économiser de l'espace sur les pointeurs, etc. - Il encore gaspille de l'espace due à la répétition de mots; il y a un truc standard de bande ordinaires, les préfixes, avec un niveau de l'indice pour les récupérer, mais c'est un peu plus complexe et plus lent. (L'idée est de stocker de l'successives des morceaux de la matrice sous forme de comprimé qui doit être analysée de manière séquentielle, avec un accès aléatoire index pour chaque morceau. Les morceaux sont assez grand pour compresser, mais assez petit pour un accès raisonnable de temps. La méthode de compression en particulier applicable ici: si les entrées sont "bonjour george" et " bonjour le monde!', prendre la deuxième entrée être "6world" à la place. (6 étant la longueur du préfixe en commun.) Ou peut-être vous pourriez vous en sortir avec l'aide de la librairie zlib? De toute façon, vous pouvez en savoir plus dans cette veine en consultant un dictionnaire des structures utilisées dans la recherche de texte intégral.) Donc, précisément, j'aimerais commencer avec le tableau avec les clés étant les deux premiers mots, en parallèle avec une matrice dont la liste des entrées possibles tiers des mots et de leurs fréquences. Il pourrait encore sucer, mais -- je pense que vous pouvez être hors de la chance autant que les piles-inclus efficace de la mémoire d'options.

Aussi, arbre binaire structures ne sont pas recommandés pour l'efficacité de mémoire ici. E. g., ce document teste une variété de structures de données sur un problème similaire (unigrams au lieu de trigrammes), et trouve une table de hachage pour battre tous les structures en arbre par cette mesure.

J'aurais dû en parler, comme quelqu'un d'autre l'a fait, que le tableau trié pourrait être utilisé uniquement pour la liste de mots, pas bigrams ou trigrammes; ensuite, pour votre "réel", structure de données, quel qu'il soit, vous utilisez entier touches au lieu de chaînes-des indices dans la liste des mots. (Mais cela vous empêche de l'exploitation commune des préfixes, sauf dans la liste des mots lui-même. Peut-être que je ne devrais pas dire cela, après tout.)

Answer 2

L'utilisation des n-uplets.
Les Tuples peuvent être des touches de dictionnaires, de sorte que vous n'avez pas besoin de nid dictionnaires.

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

Aussi comme un plus, vous pouvez l'utiliser defaultdict

• de sorte que les éléments qui n'ont pas d'entrées de toujours retourner 0
• et donc que u peut dire d[w1,w2,w3] += 1 sans vérifier si la clé existe déjà ou pas

exemple:

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

Si vous avez besoin de trouver tous les mots "terme3" qui sont tupled avec (mot1,mot2) puis rechercher dans le dictionnaire.les touches() à l'aide de la liste de compréhension

si vous avez un n-uplet, t, vous pouvez obtenir les deux premiers éléments à l'aide de tranches:

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

un petit exemple pour la recherche de tuples avec les interprétations de la liste:

>>> 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]

Vous voyez ici, nous avons obtenu une liste de tous les éléments qui apparaissent comme le troisième élément dans les tuples qui commencent par (1,2)

Answer 3

Dans ce cas, la ZODB1 BTrees pourrait être utile, car ils sont beaucoup moins gourmandes en ressources. Utiliser un BTrees.OOBtree (Objet des clés à des valeurs de l'Objet) ou BTrees.OIBTree (clés de l'Objet avec des valeurs entières), et l'utilisation de 3-mot de tuples que votre clé.

Quelque chose comme:

from BTrees.OOBTree import OOBTree as BTree

L'interface est, plus ou moins, dict-comme, avec, en bonus (pour vous) .keys, .items, .iterkeys et .iteritems deux min, max arguments optionnels:

>>> 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')]

1 à Noter que si vous êtes sur Windows et travailler avec Python >2.4, je sais il y a des paquets pour les plus récentes versions de python, mais je ne peut pas se rappeler où.

PS: Ils existent dans la CheeseShop

Answer 4

Un couple tente:

Je suppose que vous êtes en train de faire quelque chose de similaire à ceci:

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)

Qui me donne ~88MB.

Changement de mode de stockage de

h[a, b, c] = 1

faut ~25MO

un stage a, b, et c fait prendre sur 31MB. Mon cas est un peu spécial parce que mes paroles ne se répètent jamais à l'entrée. Vous pouvez essayer certains des variations de vous-même et voir si l'un de ces, vous aide.

Answer 5

Êtes-vous à la mise en œuvre de Markovienne la génération de texte?

Si vos chaînes à la carte 2, les mots pour les probabilités de la troisième j'avais utiliser un dictionnaire mapping K-tuples à la 3ème-parole de l'histogramme. Un trivial (mais de mémoire-faim), de manière à mettre en œuvre l'histogramme serait d'utiliser une liste avec les répétitions, puis random.choice vous donne un mot avec la bonne probabilité.

Voici une mise en œuvre avec le K-tuple comme paramètre:

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,)