为什么无序 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

Answer 1

执行速度变慢是由于两种综合效应造成的。问题主要来自于内部数据结构的内存访问模式。

只是迭代列表的时间是不同的

这是因为 Python 列表实际上并不包含整数，而是包含对整数对象的引用。因此，当您创建 list 时b，CPython 会分配 10_000_000 个项目，并在列表中添加一个引用，该引用基本上是内存中对象的低级地址。由于内部分配器的工作方式，分配的对象往往彼此靠近（它们通常一个接一个地放置）。问题是random.shuffle不复制对象或创建新对象，它只是对列表和引用进行洗牌，而不是内存中的对象。

问题是使用随机访问模式从内存访问数据比连续数据慢得多。这个问题称为记忆扩散。这就是为什么某些应用程序随着时间的推移变得越来越慢的原因。某些运行时可以移动内存中的对象，以便快速访问（据我所知，Java 中的某些 JVM 可以这样做，但 CPython 不能——PyPy可能会这样做，但大对象除外）。

您可以通过创建一个新列表来检查此效果：d = [(i+1)-1 for i in b]从打乱的b列表中进行基准测试d（破坏：它在我的机器上速度更快，实际上与 一样快c）。

请注意，实际上，在实际应用程序中，字典可能不会一次性填满。

我注意到无序查找比有序查找慢大约 10 倍。

这是因为字典被设计为内部排序，因此以有序方式访问它们会导致更可预测的内存访问模式。当访问可预测时，现代处理器可以有效地从内存中预取数据。此外，当并非所有对象都能放入高速缓存并且存储器访问是随机的时，许多高速缓存行的重用率较低（如果有的话），因为由于为新对象加载新的高速缓存行，高速缓存行被从高速缓存中逐出。实际上，这甚至是最糟糕的，因为缓存不是完全关联的。由此产生的效果称为缓存垃圾。当许多对象共享同一缓存行时，这种效果并不是真正的问题。

有什么方法可以加快无序字典查找速度吗？

通常的解决方案是重新排序数据结构或简单地创建一个新副本，同时考虑遍历顺序（如d之前的列表）。一般来说，字典查找效率不是很高，因为散列往往会打乱内存访问。这也是它们渐近快速的原因（O(1)查找）。

在较低级别的本机语言（如 C）中，您可以使用手动软件预取来显着减少字典查找的延迟（尽管这不灵活/不便携，而且在实践中有点棘手）。这在Python这样的高级语言中是不可能的。