Python字典的高效内存替代方案
在我目前的一个辅助项目中，我正在浏览一些文本，查看单词三元组的频率。在我的第一次尝试中，我使用了三层深度的默认字典。换句话说，topDict[word1][word2][word3]返回这些单词在文本中出现的次数，topDict[word1][word2]返回包含单词1和2之后出现的所有单词的字典，依此类推。
这可以正常运行，但它占用的内存非常多。在我最初的测试中，它使用的内存大约是在文本文件中存储三元组的内存的20倍，这似乎是一个过大的内存开销。
我怀疑许多这样的字典在创建时使用的插槽比实际使用的多得多，所以我想用其他方式使用时内存效率更高的东西来替换这些字典。我强烈倾向于一种解决方案，它允许沿着字典的行进行键查找。
根据我对数据结构的了解，使用红黑或AVL之类的平衡二进制搜索树可能是理想的，但我真的不愿意自己实现它们。如果可能的话，我更喜欢坚持使用标准的python库，但是如果其他的库工作得最好的话，我绝对愿意选择其他的库。
那么，有没有人对我有什么建议？
编辑后添加：
感谢你到目前为止的回复。到目前为止，有几个答案建议使用元组，当我将前两个单词压缩成一个元组时，元组对我来说并没有多大帮助。我不太愿意将这三个单词都用作关键字，因为我希望在给定前两个单词的情况下，能够轻松地查找所有第三个单词。(例如，我想要类似于topDict[word1, word2].keys()的结果)。
我正在使用的当前数据集是Wikipedia For Schools的最新版本。例如，对于一个文本文件，解析前1000页的结果类似于11MB，其中每行都是三个单词，count all制表符是分开的。在我现在使用的字典格式中存储文本大约需要185MB。我知道指针和诸如此类的东西会有一些额外的开销，但差异似乎太大了。
回答 12
Stack Overflow用户
发布于 2008-11-29 15:06:58
一些测量结果。我获取了10MB的免费电子书文本，并计算了三元组的频率，生成了一个24MB的文件。在不同的简单Python数据结构中存储它在kB中占用了这么多空间，通过运行ps测量RSS，其中d是一个字典，key和freqs是列表，a，b，c，freq是trigram记录的字段：
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)；列出它们只是因为其他人建议使用它们(或它们的变体)。(我做这个有点恼火，因为投票最多的答案没有帮助，如表格所示。)
“pair array”是我最初答案中的方案(“我会从键是前两个单词的数组开始...”)，其中每对的值表都表示为一个单独的字符串。“挤压对数组”是相同的，去掉了等于1的频率值(最常见的情况)。“挤压单个数组”类似于挤压对数组，但将键和值合并为一个字符串(带有分隔符)。压缩后的单数组代码：
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'))我还没有编写代码来从这个结构中查找值(使用二等分，如下所述)，也没有实现下面描述的更精致的压缩结构。
原始答案：一个简单的字符串数组，每个字符串都是空格分隔的单词连接，使用二分模块进行搜索，应该值得一试。这节省了指针上的空间，等等。由于单词的重复，它仍然浪费空间；有一个标准的技巧来剥离公共前缀，用另一层索引来取回它们，但这要复杂得多，速度也慢。(其思想是以压缩形式存储数组的连续块，必须按顺序扫描这些块，以及对每个块的随机访问索引。区块足够大，可以压缩，但对于合理的访问时间，又足够小。这里适用的特殊压缩方案是:如果连续的条目是'hello george‘和'hello world'，则将第二个条目改为'6world’。(6为前缀的共同长度。)。或者你可以使用zlib逃脱惩罚？无论如何，您可以通过查找全文搜索中使用的字典结构来了解更多信息。)所以具体地说，我将从键是前两个单词的数组开始，使用一个并行数组，它的条目列出了可能的第三个单词及其频率。不过，它可能仍然很糟糕--我认为你可能就没有那么幸运了，因为电池包括了内存效率高的选项。
此外，为了提高内存效率，这里不推荐使用二叉树结构。例如，this paper在类似的问题上测试了各种数据结构(一元组而不是三元组)，并找到了一个哈希表来击败所有的树结构。
我应该像其他人一样提到，排序的数组只能用于单词列表，而不是二元语法或三元语法；然后对于您的“真实”数据结构，无论它是什么，您都可以使用整数键而不是字符串-索引到单词列表中。(但这可以防止您使用常见的前缀，除了在单词列表本身之外。也许我最终不应该建议这样做。)
Stack Overflow用户
发布于 2008-11-29 07:36:31
使用元组。
元组可以是字典的键，所以您不需要嵌套字典。
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()中搜索它
如果您有一个元组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)开头的元组中作为第三项出现的所有项的列表。
Stack Overflow用户
发布于 2008-11-29 11:50:19
在这种情况下，ZODB？BTrees可能会有所帮助，因为它们对内存的需求要小得多。使用BTrees.OOBtree (对象值的对象键)或BTrees.OIBTree (整数值的对象键)，并使用3字元组作为键。
类似于：
from BTrees.OOBTree import OOBTree as BTree该接口或多或少类似于字典，另外(对您来说) .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☺中
https://stackoverflow.com/questions/327223
复制相似问题
腾讯云开发者
