सूचियों के लिए संलग्न और concatenate की जटिलता में अंतर

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] 

संलग्न विधि चारों ओर 20 बार संयोजन की तुलना में बेहतर क्यों है। AFAIK परिशिष्ट में ओ (1) जटिलता है जबकि सहानुभूति में ओ (के) जटिलता है। जबकि के यहां है 1.

क्या कुछ स्पष्ट चीज़ मैंने अनदेखी की है?

Answer 1

आप प्रत्येक बार नया सूची ऑब्जेक्ट बना रहे हैं। इसके लिए पुरानी सूची के सभी तत्वों को एक नए में कॉपी करने की आवश्यकता है, साथ ही एक अतिरिक्त। तो हाँ, l = l + [i] का उपयोग ओ (एन) एल्गोरिदम है, ओ (1) नहीं।

कम से कम, + concatenation का उपयोग न करें; उपयोग +=संवर्धित संयोजन, जो एक ही संदर्भ के लिए एक फिर से काम के साथ 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]