为什么无序的 python 字典查找比有序查找慢 10 倍？

Question

我尝试通过迭代整数列表在 python 中进行快速字典查找。我注意到无序查找比有序查找慢大约 10 倍。

有什么方法可以加快无序字典查找的速度吗？你知道造成时差的原因吗？在我的原始数据中，条目没有排序或连续，因为并非范围内的所有整数都在我的列表中。

我做了什么：

dummy_dict = {i:i for i in range(10000000)}

#Ordered list
a = [i for i in range(10000000)] 

#Unordered list
b = [i for i in range(10000000)] 
random.shuffle(b)

#Sorted unordered list
c = b[:]
c.sort() 

跑步次数：

[dummy_dict[i] for i in a] #Time to run: 0.7s
[dummy_dict[i] for i in b] #Time to run: 6.7s
[dummy_dict[i] for i in c] #Time to run: 0.7s

不仅查找字典速度较慢，而且只是迭代列表的时间也不同：

["" for i in a] #Time to run: 0.3s
["" for i in b] #Time to run: 0.9s
["" for i in c] #Time to run: 0.3s

为了进一步增加我的困惑，如果我创建一个这样的随机列表：

#Random list
e = [random.randint(0,9999999) for i in range(10000000)]

然后迭代列表的时间不增加：

["" for i in e] #Time to run: 0.3s

但是字典查找又慢了：

[dummy_dict[i] for i in e] #Time to run: 6.3s