混合 int 和 str 键时对字典值的不同访问时间

Question

假设我有两个字典，并且我知道想要测量检查字典中是否有某个键所需的时间。我尝试运行这段代码：

from timeit import timeit

dct1 = {str(i): 1 for i in range(10**7)}
dct2 = {i: 1 for i in range(10**7)}

print(timeit('"7" in dct1', setup='from __main__ import dct1', number=10**8))
print(timeit('7 in dct2', setup='from __main__ import dct2', number=10**8))

以下是我得到的结果：

2.529034548999334
2.212983401999736

现在，假设我尝试在两个字典中混合整数和字符串，并再次测量访问时间：

dct1[7] = 1
dct2["7"] = 1

print(timeit('"7" in dct1', setup='from __main__ import dct1', number=10**8))
print(timeit('7 in dct1', setup='from __main__ import dct1', number=10**8))
print(timeit('7 in dct2', setup='from __main__ import dct2', number=10**8))
print(timeit('"7" in dct2', setup='from __main__ import dct2', number=10**8))

我得到一些奇怪的东西：

3.443614432000686
2.6335261530002754
2.1873921409987815
2.272667104998618

第一个值比我之前的值高得多（3.44 vs 2.52）。然而，第三个值与之前基本相同（2.18 vs 2.21）。为什么会发生这种情况？你能复制同样的东西还是这只是我一个人？另外，我无法理解第一个值和第二个值之间的巨大差异：看起来访问字符串键更困难，但同样的事情似乎仅稍微适用于第二个字典。为什么？

更新

您甚至不需要实际添加新密钥。要看到复杂性增加，您所需要做的就是检查是否存在不同类型的密钥！这比我想象的要奇怪得多。看这里的例子：

from timeit import timeit

dct1 = {str(i): 1 for i in range(10**7)}
dct2 = {i: 1 for i in range(10**7)}

print(timeit('"7" in dct1', setup='from __main__ import dct1', number=10**8))
# 2.55
print(timeit('7 in dct2', setup='from __main__ import dct2', number=10**8))
# 2.26

7 in dct1
"7" in dct2

print(timeit('"7" in dct1', setup='from __main__ import dct1', number=10**8))
# 3.34
print(timeit('7 in dct2', setup='from __main__ import dct2', number=10**8))
# 2.35

Answer 1

让我尝试回答我自己的问题。CPython 中的 dict 实现针对 str 键的查找进行了优化。事实上，有两个不同的函数用于执行查找：

• lookdict是一个通用字典查找函数，可与所有类型的键一起使用
• lookdict_unicode是一个专门的查找函数，用于仅由 str 键组成的字典

Python 将使用字符串优化版本，直到搜索非字符串数据，之后使用更通用的函数。

看起来你甚至无法逆转特定字典实例的行为：一旦它开始使用通用函数，你就无法再回去使用专用函数！