deque.popleft() vs list.pop (0), analyse de la performance

Question

Selon this question, j'ai vérifié les performances sur mon ordinateur portable.

Étonnamment, je trouve que pop(0) d'un list est plus rapide que popleft() d'un deque stucture:

python -m timeit 'l = range(10000)' 'l.pop(0)' 

donne:

10000 boucles, le meilleur de 3: 66 USEC par boucle

tandis que:

python -m timeit 'import collections' 'l = collections.deque(range(10000))' 'l.popleft()' 

donne:

10000 boucles, le meilleur de 3: 123 USEC par boucle

De plus, j'ai vérifié la performance sur jupyter trouver le même résultat:

%timeit l = range(10000); l.pop(0) 

10000 boucles, le meilleur de 3: 64,7 ps par boucle

from collections import deque 
%timeit l = deque(range(10000)); l.popleft() 

10000 boucles, le meilleur de 3: 122 ms par boucle

Quelle est la raison?

Answer 1

Le problème est que votre appel timeit également fois la deque/liste création, et la création d'un deque est évidemment beaucoup plus lent en raison de l'enchaînement.

Dans la ligne de commande, vous pouvez passer la configuration à timeit en utilisant l'option -s comme ceci:

python -m timeit -s"import collections, time; l = collections.deque(range(10000000))" "l.popleft()" 

En outre, étant donné que la configuration est exécuté qu'une seule fois, vous obtenez une erreur pop (liste vide) après une whule, puisque je ne l'ai pas changé numéro par défaut d'itérations, donc je créé un grand deque pour le faire, et ai

10000000 loops, best of 3: 0.0758 usec per loop 

d'autre part avec list il est plus lent:

python -m timeit -s "l = list(range(10000000))" "l.pop(0)" 
100 loops, best of 3: 9.72 msec per loop 

J'ai aussi codé le banc dans un script (plus pratique), avec une configuration (pour éviter cadencer la configuration) et 99999 itérations sur une liste 100000 taille:

import timeit 

print(timeit.timeit(stmt='l.pop(0)',setup='l = list(range(100000))',number=99999)) 
print(timeit.timeit(setup='import collections; l = collections.deque(range(100000))', stmt='l.popleft()', number=99999)) 

sans surprise : deque victoires:

2.442976927292288 for pop in list 
0.007311641921253109 for pop in deque 

Notez que l.pop() pour la liste exécute en 0.011536903686244897 secondes, ce qui est très bien quand popping le dernier élément, comme expé cted.