为什么字典比Python中的列表更快？

Question

>>> timeit.timeit('test.append("test")', setup='test = []') 
0.09363977164165221 
>>> timeit.timeit('test[0] = ("test")', setup='test = {}') 
0.04957961010914147 

我甚至有一个循环又试了一次，而同样的事情：

>>> timeit.timeit('for i in range(10): test.append(i)', setup='test = []') 
1.3737744340367612 
>>> timeit.timeit('for i in range(10): test[i] = i', setup='test = {}') 
0.8633718070233272 

为什么名单慢？

Answer 1

首先，list.append和dict.__setitem__都是O（1）的平均情况。当然他们会有不同的系数，但实际上没有任何理由说一个或另一个会更快。系数也可能根据实施细节而改变。

其次，一个更公平的比较，将删除该属性的分辨率开销：

>>> timeit.timeit('test[0] = ("test")', setup='test = {}') 
0.0813908576965332 
>>> timeit.timeit('test_append("test")', setup='test = []; test_append = test.append') 
0.06907820701599121 

方法名的实例上的查找是比较昂贵的，当你正在寻找一个非常便宜的操作如append。

我也看到列表一直有点快，一旦有一些数据里面。这个例子是Python 3.5.2：

>>> dict_setup = 'import random; test = {random.random(): None for _ in range(1000)}' 
>>> list_setup = 'import random; test = [random.random() for _ in range(1000)]; test_append=test.append' 
>>> timeit.timeit('test[0] = "test"', setup=dict_setup) 
0.06155529400166415 
>>> timeit.timeit('test_append("test")', setup=list_setup) 
0.057089386998995906