Память эффективные альтернативы словарям Python

Используйте кортежи.
Кортежи могут быть ключами к словарям, таким образом, Вы не должны вкладывать словари.

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

Также как плюс, Вы могли использовать defaultdict

• так, чтобы элементы, которые не имеют записей всегда, возвратились 0
• и так, чтобы можно было сказать d[w1,w2,w3] += 1, не проверяя, существует ли ключ уже или не

пример:

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

, Если необходимо найти все слова "word3", которые являются tupled с (word1, word2) тогда, ищут его в dictionary.keys () использующий понимание списка

, если у Вас есть кортеж, t, можно получить первые два объекта с помощью частей:

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

небольшой пример для поиска кортежей с пониманиями списка:

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

Вы видите здесь, мы получили список всех объектов, которые появляются как третий объект в кортежах, которые запускаются с (1,2)

В этом случае B-деревья ZODB В№ могли бы быть полезными, так как они являются намного менее требующими много памяти. Используйте B-деревья. OOBtree (Объектные ключи для Возражения значениям) или B-деревья. OIBTree (Объектные ключи к Целочисленным значениям), и используют кортежи с 3 словами в качестве Вашего ключа.

Что-то как:

from BTrees.OOBTree import OOBTree as BTree

интерфейс, более или менее, подобен dict с добавленной премией (для Вас), что .keys, .items, .iterkeys и .iteritems имеют два 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')]

Примечание В№, что, если Вы находитесь в Windows и работаете с Python> 2.4, я знаю, существует пакеты для более свежих версий Python, но я не могу вспомнить где.

пз Они существуют в CheeseShop ☺

Пара попыток:

я полагаю, что Вы делаете что-то подобное этому:

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)

, Который дает мне ~88MB.

Изменение устройства хранения данных к

h[a, b, c] = 1

берет ~25MB

, интернирующий a, b, и c заставляет его взять приблизительно 31 МБ. Мой случай является немного особенным, потому что мои слова никогда не повторяются на входе. Вы могли бы попробовать некоторые изменения сами и видеть, помогает ли один из них Вам.

Вы реализуете Марковское порождение текста?

, Если бы Ваши слова карты 2 цепочек к вероятностям третьего я использовал бы словарь, отображающий K-кортежи на гистограмму 3-го слова. Тривиальное (но требующий много памяти) способ реализовать гистограмму состоял бы в том, чтобы использовать список с повторениями, и затем random.choice дает Вам слово с надлежащей вероятностью.

Вот реализация с K-кортежем в качестве параметра:

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

Вы могли попытаться использовать тот же словарь, только один уровень глубоко.

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

разделитель мог быть простым "". (или используйте (word1, word2, word3))

Это было бы самым легким реализовать. Я полагаю, что Вы будете видеть немного улучшения, если это будет недостаточно......, то я буду думать о чем-то...

Хорошо, таким образом, Вы в основном пытаетесь сохранить редкое 3D пространство. Вид схем доступа, которые Вы хотите к этому пространству, крайне важен для выбора алгоритма и структуры данных. При рассмотрении источника данных Вы хотите подать это к сетке? Если Вам не нужен O (1) доступ:

для получения эффективности памяти, Вы хотите подразделить то пространство на подпространства с подобным количеством записей. (как B-дерево). Так структура данных с:

• firstWordRange
• secondWordRange
• thirdWordRange
• numberOfEntries
• отсортированный блок записей.
• следующие и предыдущие блоки во всех 3 размерах

Scipy имеет разреженные матрицы, поэтому если можно сделать первые два слова кортежем, можно сделать что-то вроде этого:

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

Если память является просто не достаточно большой, , pybsddb может помочь сохранить персистентную диском карту.

Вы могли использовать numpy многомерный массив. Необходимо будет использовать числа, а не строки для индексации в массив, но это может быть решено при помощи единственного dict для отображения слов на числа.

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

Затем для индексации в массив Вы сделали бы что-то как:

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

, Что синтаксис не красив, но массивы numpy, почти так же эффективны как что-либо, что Вы, вероятно, найдете. Обратите внимание также, что я не испытал этот код, таким образом, я могу быть выключен в некоторых деталях. Просто движение из памяти здесь.

Вот древовидная структура, которая пользуется разделить пополам библиотекой для ведения отсортированного списка слов. Каждый поиск в 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

Для простоты, это использует фиктивное значение в каждом дереве и списке. Это сохраняет бесконечные операторы "if", чтобы определить, был ли список на самом деле пуст, прежде чем мы сделаем сравнение. Это только пусто однажды, таким образом, операторы "if" потрачены впустую для всего n-1 другие слова.

Вы могли поместить все слова в словарь. ключ был бы словом, и значение является числом (индекс).

Тогда Вы используете его как это:

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

topDictionary[Word1][Word2][Word3]

Вставляют в indexDict с:

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