Unterschied in der Komplexität von append und verketten für Listen

Question

Betrachten Sie unten Methoden zur Bildung einer Liste von tausend Zahlen.

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) 

Ausgang:

[0.30474191033602543, 0.3783786557587963] 
[0.015134341605235302, 0.023081246200096328] 

Warum ist die Methode append etwa 20 mal besser als die Verkettung. AFAIK append hat O (1) -Komplexität, während Verkettung O (k) -Komplexität hat. Während K hier ist 1.

Gibt es einige offensichtliche Dinge, die ich übersehen habe?

Answer 1

Sie erstellen ein neues Listenobjekt jedes Mal durch Verketten. Dazu müssen alle Elemente aus der alten Liste in eine neue und eine zusätzliche kopiert werden. Also ja, mit l = l + [i] ist ein O (N) Algorithmus, nicht O (1).

Zumindest nicht + Verkettung verwenden; verwenden += Verkettung ergänzt, die die gleiche Sache wie list.extend() mit einer Neuzuordnung auf die gleiche Referenz:

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

Dies erzeugt:

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