加载大字典时内存使用过大

Question

我在硬盘上有一个文件，大小只有168MB。里面是用逗号分隔的单词和ID的列表。每个单词的长度在1到5个字符之间，总共有650万行。

我在Python中创建了一个字典，把这个文件加载到内存中，这样我就可以用它来搜索输入的文本。可是当Python把它加载到内存时，显示使用了1.3GB的内存空间。你知道这是为什么吗？

假设我的单词文件看起来是这样的……

1,word1
2,word2
3,word3

然后再加上650万行。

接着我循环遍历这个文件，创建一个字典（使用的是Python 2.6.1）：

def load_term_cache():
    """will load the term cache from our cached file instead of hitting mysql. If it didn't
    preload into memory it would be 20+ million queries per process"""
    global cached_terms
    dumpfile = os.path.join(os.getenv("MY_PATH"), 'datafiles', 'baseterms.txt')
    f = open(dumpfile)
    cache = csv.reader(f)
    for term_id, term in cache:
        cached_terms[term] = term_id
    f.close()

光是这样就让内存使用量飙升。我查看了活动监视器，发现内存使用量达到了大约1.5GB，几乎用尽了我的笔记本电脑的所有内存，结果它开始进行交换。你有什么建议，如何在Python中更有效地存储键值对？

更新：我尝试使用anydb模块，但在处理440万条记录后，它就崩溃了。浮点数表示的是我尝试加载数据以来经过的秒数。

56.95
3400018
60.12
3600019
63.27
3800020
66.43
4000021
69.59
4200022
72.75
4400023
83.42
4600024
168.61
4800025
338.57

你可以看到它运行得很好。每几秒插入20万行，直到我遇到瓶颈，时间翻倍了。

import anydbm

i=0
mark=0
starttime = time.time()
dbfile = os.path.join(os.getenv("MY_PATH"), 'datafiles', 'baseterms')
db = anydbm.open(dbfile, 'c')
#load from existing baseterm file
termfile = os.path.join(os.getenv("MY_PATH"), 'datafiles', 'baseterms.txt.LARGE')
for line in open(termfile):
    i += 1
    pieces = line.split(',')
    db[str(pieces[1])] = str(pieces[0])
    if i > mark:
        print i
        print round(time.time() - starttime, 2)
        mark = i + 200000
db.close()

Answer 1

把你的数据转换成一个dbm格式（可以通过导入anydbm，或者使用berkeley db通过导入bsddb来实现），然后用dbm的接口来访问这些数据。

之所以会出现问题，是因为Python对任何对象都有额外的元信息，而字典需要构建一个哈希表（这会占用更多内存）。你创建了太多对象（6.5百万个），所以元数据变得非常庞大。

import bsddb
a = bsddb.btopen('a.bdb') # you can also try bsddb.hashopen
for x in xrange(10500) :
  a['word%d' %x] = '%d' %x
a.close()

这段代码运行只需要1秒钟，所以我觉得速度还不错（毕竟你说每秒处理10500行）。btopen创建了一个大小为499,712字节的数据库文件，而hashopen创建了一个319,488字节的文件。

当输入为6.5百万时，使用btopen，我得到的输出文件大小是417,080KB，插入大约花了1到2分钟。所以我觉得这完全适合你。

Answer 2

来看一下这个（Python 2.6，32位版本）……：

>>> sys.getsizeof('word,1')
30
>>> sys.getsizeof(('word', '1'))
36
>>> sys.getsizeof(dict(word='1'))
140

字符串在磁盘上占用6个字节，但它的内存开销是24个字节（无论字符串多长，记得在它的长度上加24，才能知道它实际占用的内存）。如果把字符串拆分成一个元组，内存占用会稍微多一点。但是，dict（字典）才是真正占内存的“大户”：即使是一个空字典，它也会占用140个字节——这都是为了保持快速查找的开销。为了快速，哈希表必须保持低密度，而Python确保字典总是低密度（这就意味着它会占用很多额外的内存）。

存储键值对最节省内存的方法是用元组的列表，但查找速度会非常慢（即使你对列表进行排序并使用bisect来查找，速度也还是比字典慢得多）。

可以考虑使用shelve，这样会占用更少的内存（因为数据存储在磁盘上），并且查找性能也相当不错（当然没有内存中的字典快，但对于大量数据来说，它的查找速度会比列表的元组查找快得多，即使是排序过的列表也不行！）。

Answer 3

有很多想法。不过，如果你想要实际的帮助，请修改你的问题，展示你所有的代码。同时告诉我们“它”指的是什么，显示内存使用情况的内容是什么，当你加载一个没有条目的文件时，它显示的是什么，以及你使用的平台和Python的版本。

你说“这个词可以是1到5个单词长”。那么在字节中，关键字段的平均长度是多少？这些ID都是整数吗？如果是的话，最小和最大整数分别是多少？如果不是，ID的平均长度是多少字节？为了能够交叉检查以上所有内容，你的6.5M行文件有多少字节？

看你的代码，一个1行的文件word1,1会创建一个字典d['1'] = 'word1'……这不是反过来了吗？

更新3：更多问题：这个“词”是如何编码的？你确定在这两个字段中没有多余的空格吗？

更新4……你问过“如何在Python中最有效地存储键值对”，但到现在为止没有人准确回答这个问题。

你有一个168MB的文件，里面有650万行。这是168 * 1.024 ** 2 / 6.5 = 每行27.1字节。去掉1个字节的逗号和1个字节的换行符（假设是在*x平台上），我们剩下每行25个字节。假设“id”是唯一的，并且看起来是整数，我们假设“id”是7个字节长；那么“词”的平均大小就是18个字节。这符合你的预期吗？

所以，我们想在内存中的查找表中存储一个18字节的键和一个7字节的值。

假设我们使用的是32位的CPython 2.6平台。

>>> K = sys.getsizeof('123456789012345678')
>>> V = sys.getsizeof('1234567')
>>> K, V
(42, 31)

注意sys.getsizeof(str_object) => 24 + len(str_object)

有一个回答提到元组。请仔细注意以下内容：

>>> sys.getsizeof(())
28
>>> sys.getsizeof((1,))
32
>>> sys.getsizeof((1,2))
36
>>> sys.getsizeof((1,2,3))
40
>>> sys.getsizeof(("foo", "bar"))
36
>>> sys.getsizeof(("fooooooooooooooooooooooo", "bar"))
36
>>>

结论：sys.getsizeof(tuple_object) => 28 + 4 * len(tuple_object)……它只允许指向每个项目的指针，并不考虑项目的大小。

对列表的类似分析显示sys.getsizeof(list_object) => 36 + 4 * len(list_object)……同样需要加上项目的大小。还有一个进一步的考虑：CPython会过度分配列表，以便在每次调用list.append()时不必调用系统的realloc()。对于足够大的大小（比如650万！），过度分配是12.5%——见源代码（Objects/listobject.c）。这个过度分配在元组中是没有的（它们的大小不会改变）。

以下是用于内存查找表的各种替代方案的成本：

元组列表：

每个元组将占用36个字节用于2元组本身，加上K和V的内容。因此N个元组将占用N * (36 + K + V)；然后你需要一个列表来保存它们，所以我们需要36 + 1.125 * 4 * N。

元组列表的总计：36 + N * (40.5 + K + V)

这大约是26 + 113.5 * N（当N是650万时大约709MB）

两个并行列表：

(36 + 1.125 * 4 * N + K * N) + (36 + 1.125 * 4 * N + V * N) 也就是72 + N * (9 + K + V)

注意40.5 * N和9 * N之间的差异，当N是650万时大约是200MB。

值存储为整数而不是字符串：

但这还不是全部。如果ID实际上是整数，我们可以将它们作为整数存储。

>>> sys.getsizeof(1234567)
12

这意味着每个值对象占用12个字节，而不是31个字节。当N是650万时，这个19 * N的差异进一步节省了大约118MB。

使用array.array('l')而不是列表来存储（整数）值：

我们可以将这些7位整数存储在array.array('l')中。没有整数对象，也没有指向它们的指针——只有一个4字节的有符号整数值。额外好处：数组的过度分配仅为6.25%（对于大N）。所以这是1.0625 * 4 * N，而不是之前的(1.125 * 4 + 12) * N，进一步节省了12.25 * N，即76MB。

所以我们最后的结果是709 - 200 - 118 - 76 = 大约315MB。

注意：错误和遗漏除外——在我的时区是0127 :-(