为什么我的dict查找不比我在Python中的列表查找更快？

Question

我正在将文件的每一行读入列表和字典,

with open("../data/title/pruned2_titleonly.txt", 'rb') as f_titles:
    titles_lst = f_titles.read().split('\n')
assert titles_lst[-1] == ''
titles_lst.pop() # remove the last element, an empty string

titles_dict = {}
with open("../data/title/pruned2_titleonly.txt", 'rb') as f_titles:
    for i,line in enumerate(f_titles):
        titles_dict[i] = line

我正在通过以随机顺序访问list/dict中的每个项目来测试性能:

n = len(titles_lst)
a = np.random.permutation(n)

%%time
for i in xrange(10):
    t = []
    for b in a:
        t.append(titles_lst[b])
    del t

>>> CPU times: user 18.2 s, sys: 60 ms, total: 18.2 s
>>> Wall time: 18.1 s

%%time
for i in xrange(10):
    t = []
    for b in a:
        t.append(titles_dict[b])
    del t

>>> CPU times: user 41 s, sys: 208 ms, total: 41.2 s
>>> Wall time: 40.9 s

上面的结果似乎暗示字典不如查找表的列表有效,即使列表查找是O(n)而dict查找是O(1).我已经测试了以下内容,看看O(n)/ O(1)性能是否真实......原来它不是......

%timeit titles_lst[n/2]
>>> 10000000 loops, best of 3: 81 ns per loop

%timeit titles_dict[n/2]
>>> 10000000 loops, best of 3: 120 ns per loop

这笔交易是什么？如果需要注意的话,我在Ubuntu 12.04下使用Python 2.7.6 Anaconda发行版,我在英特尔MKL下构建了NumPy.

Answer 1

上面的结果似乎暗示字典不如查找表的列表有效,即使列表查找是O(n)而dict查找是O(1).我已经测试了以下内容,看看O(n)/ O(1)性能是否真实......原来它不是......

dict查找是O(N)并不是真的,在"获取项目"的意义上,这是你的代码似乎要测试的意义.确定元素存在的位置(如果存在的话)可以是O(N),例如,somelist.index(someval_not_in_the_list)或者someval_not_in_the_list in somelist两者都必须扫描每个元素.试着比较x in somelist与x in somedict看到的主要区别.

但只是访问somelist[index]是O(1)(参见时间复杂性页面).并且系数可能会小于字典的情况,也就是O(1),因为您不必对密钥进行散列.

Answer 2

怎么了

出现这种现象的原因是，对于字典访问，索引（键）被散列，然后使用散列来访问散列表中的值。在列表中，索引是到列表中相应插槽的直接映射，本质上是计算得出的内存偏移量。

分别参见字典和列表的实现。

以上结果似乎暗示字典不如查找表列表有效，

不，我们不能得出结论。您的实验显示的是一个特定的实例，将列表中的数字索引访问与哈希表中的哈希键访问进行了比较。显然，要访问字典需要做更多的工作（即对索引进行哈希处理）。

我测试了以下内容，以查看O（n）/ O（1）的性能是否正确……事实并非如此……

我还进行了一些测试，请参见下文。在进行详细介绍之前，请注意所有O（1）状态都是访问时间与相应收集对象的大小无关。声明维基百科：

如果T（n）的值由不依赖于输入大小的值限制，则该算法被称为恒定时间（也称为O（1）时间）。

换句话说，给定一些集合对象x，对该对象的所有访问将独立于对象的大小。需要注意的是O（1）也做不平均，但是，所有的访问将有完全相同的运行时间。再次引用维基百科：

尽管名称为“恒定时间”，但运行时间不必与问题大小无关，但是运行时间的上限必须与问题大小无关。

这里的关键词是有界的。我们可以通过稍微修改程序来验证访问时间是否在合理范围内。请注意，我正在生成随机输入，而不是从文件构建列表和字典对象。另外，我还简化了代码以仅测试访问权限（您的代码为每个回合构建了一个新列表，这可能会改变结果的范围）。

import sha
from timeit import timeit
import random
import numpy as np

N = 1000
# generate random input of size N
titles_lst = [sha.sha(str(x)).digest() for x in range(1, N)]
titles_dict = {}
for i in range(0, len(titles_lst)):
    titles_dict[i] = titles_lst[i]
# permutate access pattern
n = len(titles_lst)
a = np.random.permutation(n)

def access_list():
    x = titles_lst[b]

def access_dict():
    x = titles_dict[b]

# run measurements for dictionary
X = []
C = 1000
for i in range(C):
    for b in a:
       X.append(timeit(access_dict, number=C))
print "dict std=%f avg=%f" % (np.std(X), np.mean(X))
# run measurements for list       
X = []
for i in range(C):
    for b in a:
       X.append(timeit(access_list, number=C))
print "list std=%f avg=%f" % (np.std(X), np.mean(X))

在我的2.7GHz macmini上，这产生以下结果。

N=100 C=1000 dict std=0.000001 avg=0.000002
N=100 C=1000 list std=0.000001 avg=0.000001

N=1000 C=1000 dict std=0.000001 avg=0.000002
N=1000 C=1000 list std=0.000001 avg=0.000001

N=10000 C=1000 dict std=0.000001 avg=0.000002
N=10000 C=1000 list std=0.000001 avg=0.000001

显然，这些测试确认字典和列表确实具有O（1）中的访问时间。他们还确认，使用数字索引/键，在这种特殊情况下，字典查找平均比列表访问慢。