Iterazione vs concatenazione elenco

Question

Quindi ci sono due modi per prendere una lista e aggiungere i membri di una seconda lista alla prima. È possibile utilizzare la concatenazione di elenchi o l'iterazione su di essa. È possibile:

for obj in list2: 
    list1.append(obj) 

o è possibile:

list1 = list1 + list2 

o

list1 += list2 

La mia domanda è: che è più veloce, e perché? Ho provato questo usando due liste estremamente grandi (più di 10000 oggetti) e sembrava che il metodo iterativo fosse molto più veloce della concatenazione di lista (come in l1 = l1 + l2). Perchè è questo? Qualcuno può spiegare?

Answer 1

append aggiunge ogni articolo uno alla volta, che è la causa della sua lentezza, nonché la funzione ripetute chiamate a append.

Tuttavia in questo caso l'operatore è +=non zucchero sintattico per la +. L'operatore += non crea effettivamente un nuovo elenco, quindi lo assegna indietro, modifica l'operando sinistro in posizione. È piuttosto evidente quando si utilizza timeit per utilizzare entrambe le 10.000 volte.

>>> timeit.timeit(stmt="l = l + j", setup="l=[1,2,3,4]; j = [5,6,7,8]", number=10000) 
0.5794978141784668 
>>> timeit.timeit(stmt="l += j", setup="l=[1,2,3,4]; j = [5,6,7,8]", number=10000) 
0.0013298988342285156 

+= è molto più veloce (circa 500x)

Hai anche il metodo extend per gli elenchi che può aggiungere qualsiasi iterabile (non solo un altro elenco) con qualcosa di simile l.extend(l2)

>>> timeit.timeit(stmt="l.extend(j)", setup="l=[1,2,3,4]; j = [5,6,7,8]", number=10000) 
0.0016009807586669922 
>>> timeit.timeit(stmt="for e in j: l.append(e)", setup="l=[1,2,3,4]; j = [5,6,7,8]", number=10000) 
0.00805807113647461 

Logicamente equivalente ad accodare, ma molto più velocemente come puoi vedere.

Quindi, per spiegare questo: iterazione è più veloce di + perché + deve costruire un intero nuovo elenco

extend è più veloce di iterazione perché è un metodo di lista integrato ed è stato ottimizzato. Logicamente equivalente ad appendere ripetutamente, ma implementato in modo diverso.

+= è più veloce di extend perché può modificare l'elenco sul posto, sapendo quanto più grande deve essere l'elenco e senza chiamate di funzione ripetute.Si presuppone che si acceda alla lista con un'altra lista/tupla

Answer 2

Ho eseguito il seguente codice

l1 = list(range(0, 100000)) 
l2 = list(range(0, 100000)) 

def t1(): 
    starttime = time.monotonic() 
    for item in l1: 
     l2.append(item) 
    print(time.monotonic() - starttime) 

l1 = list(range(0, 100000)) 
l2 = list(range(0, 100000)) 

def t2(): 
    starttime = time.monotonic() 
    global l1 
    l1 += l2 
    print(time.monotonic() - starttime) 

e ottenuto questo, che dice che l'aggiunta di liste (+ =) è più veloce.

0,016047026962041855

0,0019438499584794044

Answer 3

Si sta misurando male; iterare e chiamare più volte append è molto più lento di una sola chiamata dato che il sovraccarico della chiamata a molte funzioni (almeno in cpython) nani tutto ciò che ha a che fare con l'operazione dell'elenco reale, come mostrato qui con cPython 2.7.5 su Linux x64:

$ python -m timeit -s 'x = range(10000);y = range(10000)' 'for e in y:x.append(e)' 
100 loops, best of 3: 2.56 msec per loop 
$ python -m timeit -s 'x = range(10000);y = range(10000)' 'x = x + y' 
100 loops, best of 3: 8.98 msec per loop 
$ python -m timeit -s 'x = range(10000);y = range(10000)' 'x += y' 
10000 loops, best of 3: 105 usec per loop 
$ python -m timeit -s 'x = range(10000);y = range(10000)' 'x.extend(y)' 
10000 loops, best of 3: 107 usec per loop 

Nota che x = x + y crea una seconda copia della lista (almeno in CPython). x.extend(y) e suo cugino x += y fanno la stessa cosa di chiamare lo append più volte, senza il sovraccarico di chiamare effettivamente un metodo Python.