为什么字典查找总是比丢失的查找更好？

Question

我使用字典作为查找 table 但我开始怀疑列表是否更适合我的应用程序——我查找中的条目数量 table 不是这样大。我知道列表在幕后使用 C 数组，这让我得出结论，在只有几个项目的列表中查找比在字典中查找更好（访问数组中的几个元素比计算散列更快）。

我决定分析备选方案，但结果让我大吃一惊。列表查找只对单个元素更好！见下图（对数-对数图）：

那么问题来了：为什么列表查找执行得这么差？我错过了什么？

关于附带问题，引起我注意的其他事情是在大约 1000 个条目后的字典查找时间中 "discontinuity"。我单独绘制了字典查找时间来显示它。

p.s.1 我知道数组和散列 tables 的 O(n) 与 O(1) 摊销时间，但通常情况是迭代数组的少量元素比使用散列更好 table.

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 中出人意料地是重量级的。看到第二张图中的尖峰了吗？这就是为那里的两个整数计算 == 的成本。

您的列表查找需要计算 == 比您的字典查找多得多。

同时，计算散列对于很多对象来说可能是一个相当重量级的操作，但对于这里涉及的所有整数，它们只是对自己进行散列。（-1 将散列为 -2，大整数（技术上 longs）将散列为较小的整数，但这不适用于此处。）

Dict 查找在 Python 中并没有那么糟糕，尤其是当您的键只是一个连续的整数范围时。这里的所有整数都对自己进行散列，并且 Python 使用自定义的开放寻址方案而不是链接，所以你所有的键最终在内存中几乎是连续的，就好像你使用了一个列表（也就是说，指针到键最终在 PyDictEntrys 的连续范围内）。查找过程很快，并且在您的测试用例中，它总是在第一个探测中按正确的键。

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

Answer 2

简短的回答是列表使用线性搜索而字典使用分摊的 O(1) 搜索。

此外，当 1) 哈希值不匹配或 2) 存在身份匹配时，字典搜索可以跳过相等性测试。列表仅受益于恒等式优化。

早在 2008 年，我就这个主题发表过演讲，您可以在其中找到所有详细信息：https://www.youtube.com/watch?v=hYUsssClE94

搜索列表的大致逻辑是：

for element in s:
    if element is target:
        # fast check for identity implies equality
        return True
    if element == target:
        # slower check for actual equality
        return True
return False

对于dicts，逻辑大致是：

h = hash(target)
for i in probe_sequence(h, len(table)):
    element = key_table[i]
    if element is UNUSED:
        raise KeyError(target)
    if element is target:
        # fast path for identity implies equality
        return value_table[i]
    if h != h_table[i]:
        # unequal hashes implies unequal keys
        continue
    if element == target:
        # slower check for actual equality
        return value_table[i]

字典哈希表通常有三分之一到三分之二满，因此无论大小如何，它们往往很少发生冲突（上面显示的循环很少发生）。此外，哈希值检查可防止不必要的缓慢相等检查（浪费相等检查的机会约为 2**64 中的 1）。

如果您的时间重点放在整数上，那么还有一些其他的影响在起作用。 int 的散列就是 int 本身，所以散列非常快。此外，这意味着如果您存储连续的整数，则根本不会发生冲突。

Answer 3

你说"accessing a few elements in an array is faster than computing a hash".

一个简单的字符串散列规则可能只是一个总和（最后有一个模）。这是一个无分支操作，可以与字符比较相媲美，尤其是当前缀上有长匹配时。

为什么字典查找总是比丢失的查找更好？

Why are dict lookups always better than list lookups?

python

performance

optimization

big-o

python-internals