python - 为什么 defaultdict(int) 的 dicts 使用这么多内存？ (以及其他简单的 python 性能问题)

Question

我明白，以我的方式查询 defaultdict 中不存在的键会将项目添加到 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"

这里发生了什么？此外，与第一个脚本相比，这个类似的脚本需要 eon 来运行，并且还使用了荒谬的内存量。

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:我知道为什么，大致上，我的表应该占用 3 GB16384*8192*(12+12) 字节 和 6GB 的 defaultdict 负载因子强制它保留双倍的空间。然后内存分配效率低下又消耗了 2 个因素。

所以这是我剩下的问题:有没有办法告诉它以某种方式使用 32 位整数？

与第一个相比，为什么我的第二个代码片段需要 FOREVER 才能运行？第一个大约需要一分钟，我在 80 分钟后杀死了第二个。

Answer 1

Python int 在内部表示为 C longs(实际上比这更复杂一些)，但这并不是问题的根源。

最大的开销是你对字典的使用。 (在这个描述中，defaultdicts 和 dicts 大致相同)。 dicts 是使用哈希表实现的，这很好，因为它可以快速查找非常通用的键。 (当您只需要查找连续的数字键时，就没有那么必要了，因为它们可以以一种简单的方式进行布局。)

一个字典可以有比它拥有的项目更多的插槽。假设您有一个 dict，其插槽数是项目数的 3 倍。这些插槽中的每一个都需要空间来容纳指向键的指针和用作链表末尾的指针。这是数字的 6 倍，加上指向您感兴趣的项目的所有指针。考虑到这些指针中的每一个在您的系统上都是 8 个字节，并且在这种情况下您有 16384 个默认字典。粗略地看一下，16384 次出现 *(8192 项/出现)*7(指针/项)*8(字节/指针)= 7 GB。这是在我得到你正在存储的 实际数字(每个唯一数字本身就是一个 Python 字典)、外部字典、那个 numpy 数组或 Python 跟踪的东西之前尝试优化一些。

您的开销听起来比我怀疑的要高一些，我很想知道 11GB 是用于整个进程还是仅用于表计算。无论如何，我确实希望这个 dict-of-defaultdicts 数据结构的大小比 numpy 数组表示大几个数量级。

至于“有什么办法可以避免这些费用？”答案是“使用 numpy 存储大型、固定大小的连续数字数组，而不是字典!”您必须更具体、更具体地说明为什么您发现这样的结构对于更好地建议最佳解决方案是必要的。