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

Question

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

有没有办法对 python dict 说你将在其中存储至少 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 Mighty Dictionary

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

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