爲什麼字典比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