用於列表的追加和連接複雜度的差異

Question

考慮以下用於形成一千個數字列表的方法。

def test1(): 
    l = [] 
    for i in range(1000): 
     l = l + [i] 
    return l 


def test2(): 
    l = [] 
    for i in range(1000): 
     l.append(i)  

print timeit.repeat(stmt=test1, number=100,repeat=2) 
print timeit.repeat(stmt=test2, number=100,repeat=2) 

輸出：

[0.30474191033602543, 0.3783786557587963] 
[0.015134341605235302, 0.023081246200096328] 

爲什麼append方法比拼接好20倍左右。 AFAIK追加具有O（1）複雜性，而級聯具有O（k）複雜性。雖然這裏的K是1.

有沒有我忽略的一些明顯的東西？

Answer 1

您正在創建一個新的列表對象，每次通過連接。這需要將舊列表中的所有元素複製到新列表中，再加上一個。所以是的，使用l = l + [i]是O（N）算法，而不是O（1）。

至少，不要使用+級聯;使用+=增強串聯，這是同樣的事情list.extend()與重新分配到同一個參考：

def test3(): 
    l = [] 
    for i in range(1000): 
     l += [i] # or use l.extend([i]) 
    return l 

這將產生：

>>> print timeit.repeat(stmt=test1, number=100, repeat=2) 
[0.1333179473876953, 0.12804388999938965] 
>>> print timeit.repeat(stmt=test2, number=100, repeat=2) 
[0.01052403450012207, 0.007989168167114258] 
>>> print timeit.repeat(stmt=test3, number=100, repeat=2) 
[0.013209104537963867, 0.011193037033081055]