相关疑难解决方法(0)

我使用字典作为查找表,但我开始怀疑列表是否会更适合我的应用程序 - 查找表中的条目数量不是那么大.我知道列表在引擎盖下使用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