为什么defaultdict(int)的字典占用这么多内存？（以及其他简单的Python性能问题）

Question

我明白在使用defaultdict时，如果查询一个不存在的键，会自动添加这个键值对。这就是为什么我可以把第二段代码和第一段代码在性能上进行比较。

import numpy as num
from collections import defaultdict

topKeys = range(16384)
keys = range(8192)

table = dict((k,defaultdict(int)) for k in topKeys)

dat = num.zeros((16384,8192), dtype="int32")

print "looping begins"
#how much memory should this use? I think it shouldn't use more that a few
#times the memory required to hold (16384*8192) int32's (512 mb), but
#it uses 11 GB!
for k in topKeys:
    for j in keys:
        dat[k,j] = table[k][j]

print "done"

这里到底发生了什么？而且，这段类似的脚本运行起来比第一段慢得多，还占用了非常多的内存。

topKeys = range(16384)
keys = range(8192)
table = [(j,0) for k in topKeys for j in keys]

我猜测Python中的整数可能是64位的，这可能是造成部分问题的原因。但是，这些相对简单的代码真的会产生如此巨大的开销吗？我想这些脚本确实显示了这一点。那么，我的问题是：第一段脚本的高内存使用和第二段脚本的长运行时间以及高内存使用到底是什么原因造成的？有没有办法避免这些开销呢？

编辑：在64位机器上使用Python 2.6.4。

编辑2：我可以理解，粗略估算一下，我的表应该占用3GB的内存，计算方式是16384*8192*(12+12)字节。如果使用defaultdict的负载因子，它会强制保留双倍的空间，那就变成6GB了。然后，内存分配中的低效又会再增加一个2倍的开销。

所以我还有以下问题：有没有办法让我使用32位的整数？

还有，为什么我的第二段代码运行起来比第一段慢得多？第一段大约需要一分钟，而我在第二段运行了80分钟后就结束了。

Answer 1

Mike Graham 对于字典为什么会占用更多内存做了很好的解释，但我想告诉你为什么你的默认字典表会占用这么多内存。

现在这个默认字典（DD）的设置是这样的：每当你试图获取一个不在字典里的元素时，你会得到一个默认值（在你的例子中是0），同时这个字典也会把这个之前不存在的键和默认值0一起存储起来。我个人不太喜欢这样，但就是这样。不过，这就意味着在每次内层循环时，都会分配新的内存，这就是为什么它运行得这么慢。如果你把下面的代码

for k in topKeys:
    for j in keys:
        dat[k,j] = table[k][j]

改成

for k in topKeys:
    for j in keys:
        if j in table[k]:
            dat[k,j] = table[k][j]
        else:
            dat[k,j] = 0

那么就不会给字典里的键分配默认值了，这样我的内存使用量就保持在大约540 MB，基本上就是分配给 dat 的内存。虽然默认字典对于稀疏矩阵还不错，但如果你想要稀疏矩阵的话，可能还是直接使用 Scipy 中的稀疏矩阵更好。

Answer 2

好吧，先看看你的代码到底在干什么：

topKeys = range(16384)
table = dict((k,defaultdict(int)) for k in topKeys)

这段代码创建了一个字典，里面有16384个defaultdict(int)。字典本身有一定的开销：字典对象的大小在60到120字节之间（具体取决于你的系统构建中指针和ssize_t的大小）。这只是字典本身的大小；如果字典里的项目不止几个，数据会单独占用一块内存，大小在12到24字节之间，而且通常会填满一半到三分之二。而defaultdict会多占4到8字节，因为它需要存储额外的信息。每个整数占用12字节，虽然可以重复使用，但这段代码大部分情况下不会重复使用它们。所以，实际上，在32位的系统中，这段代码会占用60 + (16384*12) * 1.8 (填充因子)字节用于table字典，16384 * 64字节用于它存储的defaultdict，以及16384 * 12字节用于整数。这样算下来，光是这些就超过了一百五十万字节，而且还没在你的defaultdict里存储任何东西。在64位系统中，这个大小会是两倍。

接下来你创建了一个numpy数组，这个数组在内存使用上其实比较节省：

dat = num.zeros((16384,8192), dtype="int32")

这个数组本身也会有一些开销，包括常规的Python对象开销，还有数组的维度和类型等等，但总的来说不会超过100字节，而且只针对这个数组。它会在你的512Mb内存中存储16384*8192个int32类型的整数。

然后你用一种比较特殊的方式来填充这个numpy数组：

for k in topKeys:
    for j in keys:
        dat[k,j] = table[k][j]

这两个循环本身并不会占用太多内存，而且每次迭代都会重复使用内存。然而，table[k][j] 会为你请求的每个值创建一个新的Python整数，并将其存储在defaultdict中。创建的整数总是0，而且这个0总是被重复使用，但在defaultdict中存储这个引用仍然会占用空间：每个条目占用12字节，乘以填充因子（在1.66到2之间）。这样一来，实际的数据量就接近3Gb，而在64位系统中则是6Gb。

此外，由于你不断添加数据，defaultdict需要不断扩展，这意味着它们需要重新分配内存。由于Python的内存分配方式（obmalloc）以及它如何将小对象分配到自己的块中，还有大多数操作系统的进程内存工作方式，这意味着你的进程会分配更多内存，但无法释放它；实际上不会用到所有的11Gb，Python会在defaultdict的大块内存之间重复使用可用的内存，但总的映射地址空间会是11Gb。

Answer 3

Python中的整数实际上是用C语言的长整型来表示的（其实比这要复杂一些），但这并不是你问题的根本原因。

你遇到的最大问题是使用了字典（dicts）。在这里，默认字典（defaultdicts）和普通字典差不多。字典是通过哈希表来实现的，这样可以快速查找一些比较通用的键（key）。不过，当你只需要查找顺序的数字键时，这种方式就没那么必要了，因为顺序数字可以很方便地排列。

一个字典可以有比实际存储的项目多得多的槽位。比如说，你有一个字典，它的槽位是项目数量的三倍。每个槽位都需要存储一个指向键的指针和一个指向链表末尾的指针。这样算下来，指针的数量是数字的六倍，加上你关心的项目的所有指针。假设你系统中的每个指针占用8个字节，而在这种情况下你有16384个默认字典。粗略估算一下，16384 次数 * (8192 项目/次数) * 7 (指针/项目) * 8 (字节/指针) = 7 GB。这还没算上你存储的实际数字（每个唯一数字本身也是一个Python字典），外层字典，那个numpy数组，或者Python为了优化而跟踪的其他东西。

你的开销听起来比我预期的要高，我想知道那11GB是整个进程的大小，还是仅仅是表格的计算结果。无论如何，我预计这个字典嵌套字典的数据结构的大小会比numpy数组的表示大得多。

至于“有没有办法避免这些开销？”答案是“使用numpy来存储大型、固定大小的连续数字数组，而不是字典！”你需要更具体地说明为什么你觉得这样的结构是必要的，这样我才能给出更好的建议，告诉你最好的解决方案是什么。