python - 意料之外的 Python 字典行为

Question

我有这段代码:

import time

d = dict()
for i in range(200000):
    d[i] = "DUMMY"

start_time = time.time()

for i in range(200000):
    for key in d:
        if len(d) > 1 or -1 not in d:
            break
    del d[i]

print("--- {} seconds ---".format(time.time() - start_time))

为什么这需要大约 15 秒才能运行？

但是，如果我注释掉 del d[i] 或内部循环，它会在 ~0.1 秒内运行。

Answer 1

您遇到的问题是由于迭代曾经很大但已大幅缩小的字典的一个元素(例如 next(iter(d)))引起的。如果您对哈希值不走运，这可能会因为迭代所有字典项而变得几乎很慢。而且这段代码非常“不走运”(可以预见的是，由于 Python 哈希设计)。

问题的原因是当您删除项目时 Python 不会重建字典的哈希表。因此，曾经有 200000 个项目但现在只剩下 1 个项目的字典的哈希表仍然有超过 200000 个空格(可能更多，因为它可能在峰值时没有完全填满)。

当您在字典中包含所有值时迭代字典时，找到第一个非常简单。第一个将在前几个表条目之一中。但是当你清空表格时，表格开头的空格会越来越多，搜索仍然存在的第一个值会花费越来越长的时间。

这可能会更糟，因为您使用的是整数键，它(主要)散列到自己(只有 -1 散列到其他东西)。这意味着“完整”字典中的第一个键通常是 0，下一个是 1，依此类推。当您以递增的顺序删除值时，您将非常精确地首先删除表中最早的键，从而最大限度地降低搜索质量。