是否可以给 python dict 一个初始容量（并且有用）

Question

我正在用大约 10,000,000 个项目填充 python 字典。我对字典（或哈希表）的理解是，当太多元素进入其中时，需要调整大小，这个操作会花费相当长的时间。

有没有办法对 python 字典说你将在其中存储至少 n 个项目，以便它可以从一开始就分配内存？或者说这个优化对我的运行速度没有任何好处？

（不，我还没有检查我的小脚本的缓慢是否是因为这个，我实际上现在不知道如何做到这一点。然而，这是我在Java中要做的事情，正确设置HashSet的初始容量）

Answer 1

首先，我听说有传言说你可以在初始化时设置字典的大小，但我从未见过任何文档或 PEP 描述如何做到这一点。

考虑到这一点，我对你们的物品数量进行了分析，如下所述。虽然每次调整字典大小可能需要一些时间，但我建议您不要担心，至少在您可以测试其性能之前继续进行。

确定调整大小时涉及的两个规则是元素数量和调整大小因子。当添加元素使其超过 2/3 标记时，字典将在 2/3 满时自行调整大小。低于 50,000 个元素，它将增加 4 倍，高于该数量则增加 2 倍。使用您对 10,000,000 个元素的估计（在 2^23 和 2^24 之间），您的字典将调整自身大小 15 倍（低于 50k 的 7 倍，以上 8 倍）。另一次调整大小将发生在刚刚超过 11,100,000 时。

调整哈希表中当前元素的大小和替换确实需要一些时间，但我想知道您是否会注意到它以及附近代码中进行的其他操作。我只是整理了一个计时套件，比较字典大小为 2^3 到 2^24 的每个边界上五个位置的插入，“边界”添加平均比“非边界”添加长 0.4 纳秒。这长了 0.17%...可能可以接受。所有操作的最小值为 0.2085 微秒，最大值为 0.2412 微秒。

希望这是有洞察力的，如果您确实检查了代码的性能，请进行后续编辑！我关于字典内部结构的主要资源是 Brandon Rhodes 在 PyCon 2010 上的精彩演讲：The强大的词典

Answer 2

是的，你可以，这是我在另一个人的问题中找到的一个解决方案，也与你的问题相关：

d = {}
for i in xrange(4000000):
d[i] = None
# 722ms

d = dict(itertools.izip(xrange(4000000), itertools.repeat(None)))
# 634ms

dict.fromkeys(xrange(4000000))
# 558ms

s = set(xrange(4000000))
dict.fromkeys(s)
# Not including set construction 353ms

这些是初始化具有一定大小的字典的不同方法。