有效的内存替代Python字典
在我目前的一个项目中，我正在阅读一些文字，看三字组的频率。 在我第一次使用它的时候，我使用了三层深度的默认字典。 换句话说， topDict[word1][word2][word3]返回这些单词在文本中出现的次数， topDict[word1][word2]返回一个字典，其中所有单词出现在单词1和2之后。
这function正常，但它是非常内存密集型的。 在我最初的testing中，它使用了像存储三元组的文本文件20倍的内存，这似乎是一个过多的内存开销。
我的怀疑是，这些字典中的许多字段的创build数量比实际使用的字段多，所以我想用这种方式replace字典中更有记忆效率的其他字典。 我强烈希望有一个解决scheme，允许沿着字典的关键查找。
从我所了解的数据结构来看，使用类似红黑或AVL的平衡二叉search树可能是理想的，但我真的不希望自己实现它们。 如果可能的话，我宁愿坚持使用标准的Python库，但如果他们能够最好地工作，我绝对可以接受其他的select。
那么，有没有人对我有任何build议？
编辑添加：
感谢迄今的回应。 到目前为止，答案中的一些已经build议使用元组，当我将前两个单词压缩成元组时，这些元组并没有太多的用处。 我不愿意把这三个字作为一个关键字，因为我希望能够容易地查看前两个字的所有第三个字。 （即我想要的东西像topDict[word1, word2].keys() ）的结果。
我正在玩的当前数据集是维基百科学校的最新版本。 例如，parsing第一千页的结果对于文本文件是11MB，其中每行是三个词并且所有的tab都是分开的。 以字典格式存储文本我现在使用大约185MB。 我知道指针和额外的开销会有一些额外的开销，但差异似乎过大。
一些测量。 我花了10MB的免费电子书文本和计算三字母频率，产生一个24MB的文件。 将它存储在不同的简单Python数据结构中占用了这么多的kB空间，从运行ps的RSS来衡量，其中d是字典，keys和freq是列表，a，b，c，freq是trigramlogging的字段：
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
标有[*]的条目没有有效的方式来查找一对（a，b）; 他们只是因为其他人build议他们（或他们的变体）列出。 （我这样做是因为得票最高的答案没有帮助，如表所示。
'对数组'是在我原来的答案（“我会开始数组与键是前两个单词…”），其中每个对的值表被表示为一个单一的string。 “挤压对数组”是相同的，省略等于1的频率值（最常见的情况）。 “挤压单个arrays”就像挤压对arrays一样，但是将键和值一起作为一个string（带有分隔符）。 挤压单arrays代码：
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'))
我没有编写代码来查找这个结构中的值（如下所述，使用二等分），或者实现了也在下面描述的发烧友压缩结构。
原始答案：一个简单的有序string数组，每个string都是空格分隔的字串，使用平分模块进行search，值得一试。 这节省了指针等的空间，由于重复的单词，它仍然浪费空间。 有一个标准的技巧去除通用的前缀，用另一个索引级别来取回它们，但是这样做更为复杂和慢。 （这个想法是将数组的连续块以压缩的forms存储起来，这些数据块必须按顺序扫描，同时为每个块指定一个随机访问索引。块足够大以便压缩，但足够小以便访问时间合理。scheme适用于这里：如果连续的条目是“hello george”和“hello world”，改为第二个条目是'6world'（6是前缀的长度）。或者你可以使用zlib ？无论如何，通过查找全文search中使用的字典结构，你可以find更多的内容。）具体来说，我将从数组开始，键是前两个字，并行数组的条目列表可能第三个字和它们的频率。 尽pipe如此，它可能仍然很糟糕 – 我认为就电池供电的内存效率选项而言，您可能并不走运。
此外，二进制树结构不build议在这里的内存效率。 例如， 本文testing了类似问题上的各种数据结构（尽pipeunigrams代替了卦），并且find了一个散列表来打败所有的树结构。
我应该像其他人那样提到，sorting后的数组只能用于单词列表，而不能用于bigrams或trigrams; 那么对于你的“真正的”数据结构，不pipe它是什么，你使用整数键而不是string – 索引到单词表中。 （但是这样可以避免使用通用的前缀，除非在wordlist本身，也许我不应该提出这个build议。）
使用元组。
元组可以是字典的关键，所以你不需要嵌套字典。
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
如果你需要查找所有与word1，word2匹配的单词“word3”，然后在dictionary.keys（）中使用list comprehension
如果你有一个元组t，你可以使用切片得到前两个项目：
>>> a = (1,2,3) >>> a[:2] (1, 2)
一个用列表parsingsearch元组的小例子：
>>> 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）开头的元组中第三项出现的所有项目的列表，
在这种情况下，ZODB¹BTrees可能会有所帮助，因为它们的内存要less得多。 使用BTrees.OOBtree（Object keys to Object values）或BTrees.OIBTree（Object keys to Integer values），并使用3个字元组作为您的键。
就像是：
from BTrees.OOBTree import OOBTree as BTree
这个界面或多或less是字典式的，而且.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版本的软件包，但是我不记得在哪里。
PS他们存在于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使得大约需要31MB。 我的情况有点特别，因为我的话永远不会重复input。 你可以自己尝试一些变化，看看其中有一个可以帮助你。
你正在执行马尔可夫文本生成？
如果你的链映射2个单词到第三个概率，我会使用一个字典映射K元组到3字直方图。 实现直方图的一个微不足道的（但是内存random.choice ）方法是使用一个重复的列表，然后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空间。 你想要的这种空间访问模式对algorithm和数据结构的select至关重要。 考虑到你的数据源，你是否想把这个馈给网格？ 如果你不需要O（1）访问：
为了获得内存效率，您希望将该空间细分为具有相似条目数的子空间。 （如BTree）。 所以一个数据结构如下：
- firstWordRange
- secondWordRange
- thirdWordRange
- numberOfEntries
- sorting的条目块。
- 所有三维的下一个和前一个块
这是一个使用二等分库维护sorting的单词列表的树结构。 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语句被浪费在所有其他的单词上。
Scipy有稀疏的matrix，所以如果你能把前两个单词做成一个元组，你可以这样做：
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可以帮助存储磁盘持久性映射。
你可以使用一个numpymultidimensional array。 您需要使用数字而不是string来索引数组，但可以通过使用单个词典将单词映射到数字来解决。
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数组的效率和你可能find的任何东西一样高效。 还请注意，我没有尝试过这个代码，所以我可能会在一些细节。 从这里回忆。
你可以把所有的单词放在字典中。 键是词，值是数字（索引）。
然后你这样使用它：
Word1=indexDict[word1] Word2=indexDict[word2] Word3=indexDict[word3] topDictionary[Word1][Word2][Word3]
在indexDict中插入：
if word not in indexDict: indexDict[word]=len(indexDict)
