python: confronto tra prestazioni deque vs list

Question

In python docs posso vedere che deque è una collezione speciale altamente ottimizzata per l'inserimento/aggiunta di elementi dal lato sinistro o destro. Per esempio. documentazione dice:

deque sono una generalizzazione delle pile e code (il nome è pronunciato “ponte” ed è l'abbreviazione di “Deque”). Deques supportano threaded safe, appends e pop efficienti dal lato della deque con circa le stesse prestazioni O (1) in in entrambe le direzioni.

Sebbene Lista oggetti supportano operazioni simili, sono ottimizzati per operazioni rapido a lunghezza fissa e comportano O spedizione (n) di movimento della memoria per pop (0) e inserire (0, v) che modificano sia la dimensione e posizione della rappresentazione dei dati sottostanti.

Ho deciso di effettuare alcuni confronti utilizzando ipython. Qualcuno mi potrebbe spiegare che cosa ho fatto di sbagliato qui:

In [31]: %timeit range(1, 10000).pop(0) 
10000 loops, best of 3: 114 us per loop 

In [32]: %timeit deque(xrange(1, 10000)).pop() 
10000 loops, best of 3: 181 us per loop 

In [33]: %timeit deque(range(1, 10000)).pop() 
1000 loops, best of 3: 243 us per loop 

Answer 1

Per quello che vale:

> python -mtimeit -s 'import collections' -s 'c = collections.deque(xrange(1, 100000000))' 'c.pop()' 
10000000 loops, best of 3: 0.11 usec per loop 

> python -mtimeit -s 'c = range(1, 100000000)' 'c.pop()' 
10000000 loops, best of 3: 0.174 usec per loop 

> python -mtimeit -s 'import collections' -s 'c = collections.deque()' 'c.appendleft(1)' 
10000000 loops, best of 3: 0.116 usec per loop 

> python -mtimeit -s 'c = []' 'c.insert(0, 1)' 
100000 loops, best of 3: 36.4 usec per loop 

Come si può vedere, dove brilla davvero è in appendleft vs insert.

Answer 2

Could anyone explain me what I did wrong here

Sì, il tuo tempismo è dominato dal tempo per creare l'elenco o deque. Il tempo di fare il pop è insignificante in confronto.

Invece si dovrebbe isolare la cosa si sta cercando di prova (la velocità di comparsa) dal momento di installazione:

In [1]: from collections import deque 

In [2]: s = range(1000) 

In [3]: d = deque(s) 

In [4]: s_append, s_pop = s.append, s.pop 

In [5]: d_append, d_pop = d.append, d.pop 

In [6]: %timeit s_pop(); s_append(None) 
10000000 loops, best of 3: 115 ns per loop 

In [7]: %timeit d_pop(); d_append(None) 
10000000 loops, best of 3: 70.5 ns per loop 

Detto questo, le reali differenze tra i deque e lista in termini di performance sono:

• deque hanno O (1) velocità appendleft() e popleft() mentre liste hanno prestazioni O (n) per inserto (0, valore) 012.389.e pop (0).

• L'elenco delle prestazioni dell'app è incostante perché utilizza realloc() sotto il cofano. Di conseguenza, tende ad avere temporizzazioni eccessivamente ottimistiche in codice semplice (perché il realloc non deve spostare dati) e tempi veramente lenti nel codice reale (perché la frammentazione costringe realloc a spostare tutti i dati). Al contrario, le prestazioni di deque append sono coerenti perché non reallocano mai e non spostano mai i dati.