Python字典的内存有效替代方案

一些测量。我花了10MB的免费电子书文字并计算了Trigram的频率，产生了24MB的文件。将其存储在不同的简单Python数据结构中占用了很大的空间（kB），以运行ps的RSS来衡量，其中d是字典，键和频率是列表，而a，b，c，freq是三字母记录的字段：

295760     S. Lott's answer237984     S. Lott's with keys interned before passing in203172 [*] 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）。仅因为其他人建议了它们（或它们的变体）而列出了它们。（我很讨厌这样做，因为如表所示，投票最多的答案没有帮助。）

“配对数组”是我原始答案中的以下方案（“我将从数组开始，键是前两个单词…”），其中每对的值表均表示为单个字符串。“压缩对阵列”是相同的，省略了等于1的频率值（最常见的情况）。“压缩的单个数组”类似于压缩的对数组，但是将键和值作为一个字符串（带有分隔符）组合在一起。压缩的单数组代码：

import collectionsdef 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|%sn' % (key, ' '.join(pairs[key])))def load():    return open('squeezedsinglearrayfile').readlines()if __name__ == '__main__':    build(open('freqs'))

我尚未编写代码来从该结构中查找值（使用bisect，如下所述），也未实现下面也描述的更高级的压缩结构。

原始答案：
使用bisect模块搜索的简单的字符串排序数组（每个字符串是用空格分隔的单词串联）应该值得尝试。这样可以节省指针等的空间。由于单词的重复，仍然浪费空间。有一个标准的技巧可以去除常见的前缀，并通过另一级索引将其取回，但这是相当复杂和缓慢的。（这个想法是将阵列中的连续块以压缩形式存储，该压缩形式必须按顺序进行扫描，并对每个块进行随机访问索引。块足以压缩，但对于合理的访问时间来说足够小。特定的压缩此处适用的方案：如果连续的条目是“
hello george”和“ hello world”，则将第二个条目改为“
6world”。zlib？无论如何，通过查找全文搜索中使用的字典结构，您可以在这方面找到更多的信息。）因此，具体地说，我将从键为前两个单词的数组开始，并从一个并行数组中查找可能的条目第三词及其频率。不过，它可能仍然很糟糕-
我认为您可能不满意包含电池的内存效率选项。

此外，此处 不
建议使用二叉树结构来提高内存效率。例如，本文针对相似的问题测试了各种数据结构（尽管用字母组合代替了字母组合），并找到了一个哈希表以这种方式击败了所有的树形结构。

我应该提到，就像其他人一样，排序后的数组只能用于单词列表，不能用于双字母组或三字组。然后对于“真实的”数据结构，无论它是什么，都使用整数键而不是字符串-
进入单词表的索引。（但是，这使您无法利用单词表本身之外的常用前缀。也许我不应该建议这样做。）