为什么dict查找总是比列表查找更好？

Question

我使用字典作为查找表,但我开始怀疑列表是否会更适合我的应用程序 - 查找表中的条目数量不是那么大.我知道列表在引擎盖下使用C数组,这使我得出结论,在列表中只查找几个项目比在字典中更好(访问数组中的一些元素比计算哈希更快).

我决定介绍其他选择,但结果让我感到惊讶.列表查找只有单个元素才能更好!请参见下图(log-log plot):

所以问题就出现了:为什么列表查找执行得如此糟糕？我错过了什么？

在一个侧面问题上,在大约1000个条目之后,在dict查找时间中引起我注意的其他东西是一个小"不连续".我单独绘制了dict查找时间来显示它.

ps1我知道数组和散列表的O(n)vs O(1)摊销时间,但通常情况下,迭代数组的少量元素比使用散列表更好.

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

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]

ps3使用Python 2.7.13

Answer 1

我知道列表在引擎盖下使用C数组,这使我得出结论,在列表中只查找几个项目比在字典中更好(访问数组中的一些元素比计算哈希更快).

访问一些数组元素很便宜,当然,但计算==在Python中是非常重要的.在第二张图中看到那个尖峰？那是==两个整数的计算成本.

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

同时,对于很多对象来说,计算哈希可能是一个非常重要的操作,但是对于这里涉及的所有内容,它们只是哈希自己.(-1将散列为-2,大整数(技术上为longs)将散列为较小的整数,但这不适用于此.)

Dict查找在Python中并不是那么糟糕,特别是当你的密钥只是一个连续的整数范围时.这里的所有int都是哈希,而Python使用自定义的开放寻址方案而不是链接,所以你的所有键在内存中几乎就像你使用列表一样连续(也就是说,指向键的指针结束)在连续的PyDictEntrys)范围内.查找过程很快,在您的测试用例中,它总是在第一个探针上点击正确的键.

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

Answer 2

简短的回答是列表使用线性搜索,而dicts使用摊销的O(1)搜索.

此外,当1)哈希值不匹配时,或者当存在身份匹配时,dict搜索可以跳过相等性测试.列表仅受益于身份意味着平等优化.

早在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).

如果您的时间关注整数,那么还有一些其他效果.int的散列是int本身,因此散列非常快.此外,这意味着如果您存储连续的整数,则根本不会发生冲突.