python - 为什么字典查找总是比列表查找好？

Question

我使用字典作为查找表，但我开始怀疑列表是否更适合我的应用程序——我的查找表中的条目数量并没有那么大。我知道列表在底层使用 C 数组，这让我得出结论，在只有几个项目的列表中查找会比在字典中更好(访问数组中的几个元素比计算哈希更快)。

我决定分析替代方案，但结果让我感到惊讶。列表查找仅使用单个元素更好!见下图(log-log plot):

那么问题来了:为什么列表查找的表现如此糟糕？我错过了什么？

在一个附带问题上，引起我注意的另一件事是在大约 1000 个条目之后的 dict 查找时间中出现了一点“不连续性”。我单独绘制了dict查找时间来显示它。

p.s.1 我知道数组和哈希表的 O(n) 与 O(1) 摊销时间，但通常情况下，迭代数组的少量元素比使用一个哈希表。

p.s.2 这是我用来比较字典和列表查找时间的代码:

import timeit

lengths = [2 ** i for i in xrange(15)]

list_time = []
dict_time = []
for l in lengths:
    list_time.append(timeit.timeit('%i in d' % (l/2), 'd=range(%i)' % l))
    dict_time.append(timeit.timeit('%i in d' % (l/2),
                                   'd=dict.fromkeys(range(%i))' % l))
    print l, list_time[-1], dict_time[-1]

p.s.3 使用 Python 2.7.13

Answer 1

I know lists use C arrays under the hood which made me conclude that lookup in a list with just a few items would be better than in a dictionary (accessing a few elements in an array is faster than computing a hash).

当然，访问一些数组元素很便宜，但计算 == 在 Python 中却出人意料地重量级。看到第二张图中的尖峰了吗？这就是为两个整数计算 == 的成本。

您的列表查找需要计算 == 比您的 dict 查找更多。

同时，计算哈希值对于很多对象来说可能是一个相当重量级的操作，但对于这里涉及的所有 int，它们只是对自己进行哈希处理。 (-1 会散列到 -2，大整数(技术上是 longs)会散列到更小的整数，但这不适用于这里。)

字典查找在 Python 中并没有那么糟糕，尤其是当您的键只是一个连续的整数范围时。这里所有的 int 都自己散列，Python 使用自定义的开放寻址方案而不是链接，所以你所有的键最终在内存中几乎和你使用列表一样连续(也就是说，指向键的指针结束在连续的 PyDictEntry 范围内)。查找过程很快，而且在您的测试用例中，它总是在第一次探测时点击右键。

---

好的，回到图 2 中的峰值。第二个图中 1024 个条目的查找时间峰值是因为对于所有较小的大小，您要查找的整数都是 <= 256，所以它们都在CPython 的小整数缓存的范围。 Python 的引用实现为从 -5 到 256 的所有整数保留规范整数对象，包括在内。对于这些整数，Python 能够使用快速指针比较来避免经历计算 == 的(令人惊讶的重量级)过程。对于较大的整数，in 的参数不再是与 dict 中匹配的整数相同的对象，Python 必须经历整个 == 过程。