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

Question

在我的一个项目中，我正在扫描一些文本，查看单词三元组的频率。在第一次尝试时，我使用了默认的三层字典。换句话说，topDict[word1][word2][word3] 返回这些单词在文本中出现的次数，topDict[word1][word2] 返回一个包含所有接踵而至的单词的字典。

这样做是正确的，但它需要占用很多内存。在我的初始测试中，它使用了大约20倍于仅将三元组存储在文本文件中所需的内存量，这似乎是一种过度的内存开销。

我的怀疑是许多这些字典被创建了比实际使用的要多的插槽，因此我想用更加内存高效的东西来替换这些字典。我非常希望找到一种解决方案，可以使用类似于字典的键查找。

据我所知，使用像红黑树或AVL之类的平衡二叉搜索树可能是理想的，但我真的不想自己实现它们。如果可能的话，我更愿意坚持使用标准的Python库，但如果它们能最好地工作，我绝对会考虑其他替代方案。

那么，有没有人对我有什么建议呢？

编辑后添加：

感谢迄今为止的回复。到目前为止，一些答案建议使用元组，但当我将前两个单词缩成一个元组时并没有起到很大作用。我不愿意将所有三个单词都用作键，因为我希望很容易地查找给定前两个单词的所有第三个单词。（例如，我需要类似于topDict[word1, word2].keys()结果的东西）。

我目前正在处理的数据集是最新版本的Wikipedia For Schools。例如，解析前一千个页面的结果是一个文本文件，大约有11MB大小，每行都是三个单词和计数用制表符分隔。使用我现在使用的字典格式存储这些文本需要大约185MB的空间。我知道会有一些额外的指针开销等问题，但这种差异似乎过大。

- ricree

---

你能提供一个样本词汇表的链接吗？Wikipedia For Schools已禁用下载。你的11MB文件以及你计划从中获得的内容（也许是你当前的实现）将非常适合测试。 - Dustin

Answer 1

一些度量。我取了10MB的免费电子书文本并计算了三元组频率，生成一个24MB的文件。将其存储在不同的简单Python数据结构中所占用的空间大小以kB为单位进行测量，通过运行ps来测量RSS，其中d是一个字典，keys和freqs是列表，a、b、c、freq是三元组记录的字段：

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”是我的原始答案中下面的方案（“我会从键为前两个单词的数组开始……”），其中每个对的值表现为一个单独的字符串。“Squeezed pair array”与此相同，省略了等于1的频率值（最常见的情况）。 “Squeezed single array”类似于“squeezed pair array”，但将键和值作为一个字符串粘合在一起（使用分隔符字符）。压缩后的单个数组代码：

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

我还没有编写从这个结构中查找值的代码（使用如下所述的 bisect），也没有实现其他描述下面的更高级压缩结构。

原始答案：首先尝试使用一个简单的字符串排序数组，每个字符串都是由空格分隔的单词串联起来搜索，使用 bisect 模块。这可以节省指针等空间。但它仍然浪费了空间，因为单词会重复；有一种标准技巧可以剥离公共前缀并使用另一级索引将它们还原，但这更加复杂和缓慢。（思路是将数组的连续块以压缩形式存储，必须按顺序扫描，以及每个块的随机访问索引。块足够大以进行压缩，但访问时间合理。适用于此处的特定压缩方案：如果连续条目是“hello george”和“hello world”，则使第二个条目成为“6world”。 （6 是相同前缀的长度）。或者也许您可以使用 zlib？无论如何，您可以通过查找全文搜索中使用的字典结构了解更多信息。）因此，具体而言，我会从数组开始，键是前两个单词，并有一个并行的数组，其条目列出了可能的第三个单词及其频率。但它可能仍然不太好 - 我认为您在内存高效选项上可能运气不佳。

此外，二叉树结构在这里不推荐使用。例如，这篇论文 在类似问题上测试了各种数据结构（虽然是 unigrams 而不是 trigrams），并发现哈希表在该度量标准下都优于所有树结构。

我应该提到，正如其他人所做的那样，排序数组可以仅用于单词列表，而不是 bigrams 或 trigrams；然后对于您的“真实”数据结构，无论它是什么，都使用整数键而不是字符串 - 这是单词列表中的索引。（但这使您无法在单词列表之外利用公共前缀。也许我不应该建议这样做。）

- Darius Bacon

---

你有原始字典的访问权限吗？如果有，测试d[(intern(a), intern(b))] = sorted([(int(freq), intern(c))])将很有启发性...重点是单词对返回第三个单词的（排序）列表... - F1Rumors

@F1Rumors，恐怕不行。而且从今天的角度来看，这都是在一个古老的Python版本上完成的。 - Darius Bacon

Answer 2

使用元组。
元组可以作为字典的键，因此您不需要嵌套字典。

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)开头的元组中第三个项目的所有项目。

- hasen j

---

使用列表推导式进行搜索对于如此大的输入来说将会非常慢（虽然它是线性搜索，但“n”将非常大）。在这里使用字典的目的是为了快速查找。 - Claudiu

Answer 3

在这种情况下，ZODB¹ B树可能会很有帮助，因为它们需要的内存更少。使用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 ☺

- ΤΖΩΤΖΙΟΥ

Answer 4

一些尝试：

我猜你正在做类似于这样的事情：

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的空间。我的情况有些特殊，因为输入中我的单词从不重复。您可以尝试一些变化，看看是否有助于解决问题。

- Dustin

Answer 5

你正在实现马尔可夫文本生成吗？

如果你的链将2个单词映射到第三个单词的概率，我建议使用字典将K元组映射到第三个单词的直方图。一种简单（但占用内存）的实现直方图的方法是使用带有重复项的列表，然后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,)

- orip

Answer 6

好的，所以您基本上正在尝试存储稀疏的三维空间。您希望对这个空间进行的访问模式对于算法和数据结构的选择至关重要。考虑到您的数据源，您想将其馈送到网格中吗？如果您不需要O(1)的访问：

为了实现内存效率，您需要将该空间细分成具有相似条目数量的子空间（例如BTree）。因此，需要使用以下数据结构：

• firstWordRange
• secondWordRange
• thirdWordRange
• numberOfEntries
• 一个条目的排序块。
• 在所有3个维度中的下一个和前一个块。

- Stephan Eggermont

Answer 7

你可以尝试只使用同一个字典，且仅限于一层深度。

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

分隔符可以是普通的空格（或使用（单词1，单词2，单词3））

这将是最容易实现的。 我相信您会看到一些改善，如果还不够... ...我会想出办法的...

- user39307

---

我尝试了两层深度，其中键是单词1和2的元组，但实际上增加了内存使用量。我强烈希望在给定1和2的情况下轻松访问所有第三个单词，因此将它们全部用作键可能不太可行。 - ricree

此外，我的理解是dict是使用某种哈希表实现的，尽管我从未能找到明确的来源。 - ricree

1. 使用哈希函数计算密钥的哈希值。
2. 哈希值指向 d.data 中的一个位置，该位置应该是一个包含（键，值）对的“桶”或“冲突列表”的数组。
3. 顺序搜索冲突列表。 __ 我认为在第二步中使用了 RB。

- user39307

我想我可能会就dict()的实现提出自己的问题。顺便说一句，谢谢你们的回答。 - ricree

Answer 8

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

- Rick Copeland

Answer 9

如果内存不够大，pybsddb 可以帮助存储一个磁盘持久化映射。

- orip

Answer 10

你可以使用numpy的多维数组。你需要使用数字而不是字符串来索引数组，但可以通过使用一个字典将单词映射到数字来解决这个问题。

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数组是你可能找到的最有效的东西。还要注意的是，我没有尝试过这段代码，所以某些细节可能有偏差。只是凭记忆写的。

- nase

---

这个一般的想法可能有所帮助，但单靠它本身行不通。在我的测试输入中，有100000个不同的单词；一个3D数组需要10^15个条目。 - Darius Bacon