0

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

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

我正在通过以随机顺序访问列表/字典中的每个项目来测试性能：

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) 而字典查找是 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 发行版，并且在 Intel MKL 下构建了 NumPy。

4

3 回答 3

8

上述结果似乎暗示字典不如查找表的列表高效，即使列表查找是 O(n) 而字典查找是 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)，因为您不必散列密钥。

于 2014-01-18T03:43:47.597 回答
5

什么是交易？

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

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

上述结果似乎暗示字典不如查找表的列表高效，

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

我已经测试了以下内容，看看 O(n)/O(1) 的性能是否属实......结果不是......

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

如果 T(n) 的值受一个不依赖于输入大小的值限制，则称该算法为常数时间（也写为 O(1) 时间）。

换句话说，给定一些集合对象x，对这个对象的所有访问都将独立于对象的大小。但是请注意，O(1)也不意味着所有访问都将具有完全相同的运行时间。再次引用维基百科：

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

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

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)。他们还确认，在这种特殊情况下，使用数字索引/键，字典查找平均比列表访问慢。

于 2014-01-18T05:42:36.047 回答
4

list[]正在从列表中的特定已知位置获取某些东西- O(1)

dict[]正在使用键搜索字典 -平均O(1)

如果你想比较搜索尝试搜索一个列表 - O(n)

[x for x in list if x==val]

看到真正的区别

于 2014-01-18T03:55:22.367 回答