リストの追加と連結の複雑さの差

Question

以下の1000個の数値のリストを作成する方法を検討してください。

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倍優れています。連結はO（k）の複雑さを有する一方、AFAIK付加はO（1）の複雑さを有する。 Kはここでは1です。

見落としたことはありますか？

Answer 1

新しいリストオブジェクトを連結するたびにリストオブジェクトを作成しています。これには、古いリストのすべての要素を新しいリストに加えて1つの余分なものにコピーする必要があります。したがって、l = l + [i]を使用すると、O（1）ではなくO（N）アルゴリズムになります。

少なくとも、+の連結は使用しないでください。

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]