Efficienza dell'uso di un elenco Python come coda

Question

Un collaboratore ha recentemente scritto un programma in cui ha usato un elenco Python come coda. In altre parole, ha utilizzato .append(x) quando è necessario inserire elementi e .pop(0) quando è necessario rimuovere gli elementi.

So che Python ha collections.deque e sto cercando di capire se passare il mio (limitato) tempo per riscrivere questo codice per usarlo. Supponendo che eseguiamo milioni di accodamenti e pop ma non abbiamo mai più di qualche migliaio di voci, il suo utilizzo della lista potrebbe essere un problema?

In particolare, l'array sottostante utilizzato dall'implementazione dell'elenco Python continuerà a crescere indefinitamente con milioni di punti anche se l'elenco contiene solo un migliaio di cose oppure Python alla fine eseguirà uno realloc e libererà parte di quella memoria?

Answer 1

Non si esaurirà la memoria utilizzando l'implementazione list, ma le prestazioni saranno scarse. Da the docs:

Sebbene list oggetti supportano simili operazioni, sono ottimizzati per operazioni veloci a lunghezza fissa e comportano costi O (n) di circolazione di memoria per pop(0) e insert(0, v) operazioni che modificano sia la dimensione posizione dei dati sottostanti rappresentazione .

Quindi l'utilizzo di deque sarà molto più veloce.

Answer 2

sembra un po 'di test empirici potrebbe essere la cosa migliore da fare qui - problemi di secondo ordine potrebbero rendere un approccio migliore nella pratica, anche se non è meglio in teoria.

Answer 3

Ogni .pop(0) richiede N passaggi, poiché l'elenco deve essere riorganizzato. La memoria richiesta non crescerà all'infinito e sarà grande solo quanto richiesto per gli oggetti che sono contenuti.

Si consiglia di utilizzare deque per ottenere O (1) append e pop dalla parte anteriore.

Answer 4

Alcune risposte hanno sostenuto un vantaggio di velocità "10x" di coda doppia vs list-usato-come-FIFO quando entrambi hanno 1000 voci, ma questo è un po 'un overbid:

$ python -mtimeit -s'q=range(1000)' 'q.append(23); q.pop(0)' 
1000000 loops, best of 3: 1.24 usec per loop 
$ python -mtimeit -s'import collections; q=collections.deque(range(1000))' 'q.append(23); q.popleft()' 
1000000 loops, best of 3: 0.573 usec per loop 

python -mtimeit è tuo amico - un approccio micro-benchmarking davvero utile e semplice! Con essa è possibile, naturalmente, anche banalmente esplorare performance in tanto piccoli casi:

$ python -mtimeit -s'q=range(100)' 'q.append(23); q.pop(0)' 
1000000 loops, best of 3: 0.972 usec per loop 
$ python -mtimeit -s'import collections; q=collections.deque(range(100))' 'q.append(23); q.popleft()' 
1000000 loops, best of 3: 0.576 usec per loop 

(non molto diverso per 12 invece di 100 articoli BTW), e in quelli molto-più grande:

$ python -mtimeit -s'q=range(10000)' 'q.append(23); q.pop(0)' 
100000 loops, best of 3: 5.81 usec per loop 
$ python -mtimeit -s'import collections; q=collections.deque(range(10000))' 'q.append(23); q.popleft()' 
1000000 loops, best of 3: 0.574 usec per loop 

Si può vedere che la richiesta di prestazioni O (1) per deque è ben fondata, mentre una lista è oltre due volte più lenta di circa 1.000 articoli, un ordine di grandezza di circa 10.000. Puoi anche vedere che anche in questi casi stai solo sprecando 5 microsecondi circa per append/pop pair e decidi quanto sia significativo lo spreco (anche se è tutto ciò che stai facendo con quel container, deque non ha svantaggi, quindi tu potrebbe anche cambiare anche se 5 usec più o meno non farà una differenza importante).

Answer 5

Da Beazley's Python Essential Reference, Fourth Edition, p. 194:

Alcuni moduli della libreria fornire nuovi tipi che superano i built-in a alcuni compiti. Ad esempio, il tipo collections.deque fornisce la funzionalità simile a un elenco ma è stato ottimizzato per l'inserimento di articoli ad entrambe le estremità per l' . Un elenco , al contrario, è efficiente solo quando si aggiungono elementi alla fine. Se si inseriscono elementi nella parte anteriore, tutti gli gli altri elementi devono essere spostati per fare spazio. L'ora necessaria per farlo cresce man mano che l'elenco diventa sempre più grande. Giusto per dare un'idea della differenza, qui è una misura tempi di inserimento di un milione di voci nella parte anteriore di una lista e di una deque:

E ci segue questo codice di esempio:

>>> from timeit import timeit 
>>> timeit('s.appendleft(37)', 'import collections; s = collections.deque()', number=1000000) 
0.13162776274638258 
>>> timeit('s.insert(0,37)', 's = []', number=1000000) 
932.07849908298408 

I tempi sono dalla mia macchina.

---

2012-07-01 Aggiornamento

>>> from timeit import timeit 
>>> n = 1024 * 1024 
>>> while n > 1: 
...  print '-' * 30, n 
...  timeit('s.appendleft(37)', 'import collections; s = collections.deque()', number=n) 
...  timeit('s.insert(0,37)', 's = []', number=n) 
...  n >>= 1 
... 
------------------------------ 1048576 
0.1239769458770752 
799.2552740573883 
------------------------------ 524288 
0.06924104690551758 
148.9747350215912 
------------------------------ 262144 
0.029170989990234375 
35.077512979507446 
------------------------------ 131072 
0.013737916946411133 
9.134140014648438 
------------------------------ 65536 
0.006711006164550781 
1.8818109035491943 
------------------------------ 32768 
0.00327301025390625 
0.48307204246520996 
------------------------------ 16384 
0.0016388893127441406 
0.11021995544433594 
------------------------------ 8192 
0.0008249282836914062 
0.028419017791748047 
------------------------------ 4096 
0.00044918060302734375 
0.00740504264831543 
------------------------------ 2048 
0.00021195411682128906 
0.0021741390228271484 
------------------------------ 1024 
0.00011205673217773438 
0.0006101131439208984 
------------------------------ 512 
6.198883056640625e-05 
0.00021386146545410156 
------------------------------ 256 
2.9087066650390625e-05 
8.797645568847656e-05 
------------------------------ 128 
1.5974044799804688e-05 
3.600120544433594e-05 
------------------------------ 64 
8.821487426757812e-06 
1.9073486328125e-05 
------------------------------ 32 
5.0067901611328125e-06 
1.0013580322265625e-05 
------------------------------ 16 
3.0994415283203125e-06 
5.9604644775390625e-06 
------------------------------ 8 
3.0994415283203125e-06 
5.0067901611328125e-06 
------------------------------ 4 
3.0994415283203125e-06 
4.0531158447265625e-06 
------------------------------ 2 
2.1457672119140625e-06 
2.86102294921875e-06