Listeleme için ekleme ve birleştirme karmaşıklığı

Question

Bin sayıların bir listesini oluşturmak için aşağıdaki yöntemleri göz önünde bulundurun.

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) 

Çıktı:

[0.30474191033602543, 0.3783786557587963] 
[0.015134341605235302, 0.023081246200096328] 

Neden birleştirme daha yaklaşık 20 kat daha iyi ekleme yöntemidir. AFAIK eki, O (1) karmaşıklığına sahipken, birleştirme, O (k) karmaşıklığına sahiptir. Burada K 1 iken, gözden kaçan belli bir şey var mı?

Answer 1

Her defasında bir birleştirerek yeni liste nesnesini oluşturuyorsunuz. Bu, eski listeden tüm öğelerin bir kopyaya eklenmesini gerektirir. Evet, l = l + [i] kullanmak O (N) algoritmasıdır, O (1) değil. En az + birleştirme; yine de `alıyor

>>> 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]