Efficacité de l'utilisation d'une liste Python comme file d'attente

Question

Un collègue a récemment écrit un programme dans lequel il a utilisé une liste Python comme une file d'attente. En d'autres termes, il a utilisé .append(x) lorsqu'il est nécessaire d'insérer des éléments et de l' .pop(0) lorsqu'il est nécessaire de supprimer des éléments.

Je sais que Python a collections.deque et je suis à essayer de comprendre si passer mon (limitée) de temps à réécrire ce code pour l'utiliser. En supposant que nous effectuons des millions de ajoute et pop, mais jamais plus de quelques milliers d'entrées, son utilisation des listes de problème?

En particulier, le tableau sous-jacent utilisé par la liste Python de mise en œuvre de croître indéfiniment avoir des millions de spots, même si la liste n'a qu'un millier de choses, ou va Python, éventuellement, un realloc et de libérer de la mémoire?

Answer 1

Quelques réponses réclamé un "10x" avantage de vitesse pour deque vs liste-utilisé-comme-FIFO lorsque les deux ont de 1000 entrées, mais c'est un peu un a surenchéri:

$ 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 est votre ami, vraiment utile et simple micro-analyse comparative de l'approche! Avec elle, vous pouvez bien sûr aussi trivialement explorer les performances dans bien des cas moins importants:

$ 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

(pas très différents de 12 au lieu de 100 éléments btw), et en plus-les plus grands:

$ 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

Vous pouvez voir que la revendication de O(1) performance pour deque est fondé, alors qu'une liste est plus de deux fois plus lent autour de 1 000 articles, un ordre de grandeur autour de 10 000. Vous pouvez également voir que, même dans de tels cas, vous êtes seulement de perdre 5 microsecondes par ajout/pop paire et de décider quelle est l'importance que le gaspillage est (si si c'est tout ce que vous faites avec ce conteneur deque a aucun inconvénient, de sorte que vous pourriez aussi bien basculer, même si 5 usec de plus ou de moins ne fera pas une grande différence).

Answer 2

Vous ne manquerez pas de mémoire à l'aide de l' list mise en œuvre, mais les performances seront pauvres. À partir de la documentation:

Si list objets similaires de soutien les opérations, ils sont optimisés pour rapide de longueur fixe et d'engager des opérations de O(n) de la mémoire des coûts de mouvement pour pop(0) et insert(0, v)opérations qui changer à la fois la taille et la la position des données sous-jacentes la représentation.

Donc, à l'aide d'un deque sera beaucoup plus rapide.

Answer 3

De Beazley du Python de Référence Essentiel, Quatrième Édition, p. 194:

Certains modules de bibliothèque de fournir de nouveaux types qui dépassent le built-ins à certaines tâches. Par exemple, les collections.deque type d'offre une fonctionnalité similaire à une liste, mais a été hautement optimisé pour le insertion d'éléments aux deux extrémités. Un liste, en revanche, est seulement efficace lorsque vous ajoutez des éléments à la fin. Si vous insérez des éléments à l'avant, toutes les autres éléments doivent être déplacés afin de faire de la place. Le temps nécessaire pour ce faire croît à mesure que la liste devient plus grand et plus. Juste pour donner de la vous avez une idée de la différence, ici, est un temps de mesure de l'insertion d'un million d'articles à la tête d'une liste et d'un deque:

Et on suit cet exemple de code:

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

Horaires de ma machine.

---

2012-07-01 mise à Jour

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

Answer 4

Chaque .pop (0) prend N étapes, car la liste doit être réorganisée. La mémoire requise ne se développera pas sans fin et ne sera aussi grande que celle requise pour les éléments qui sont conservés.

Je recommanderais d'utiliser deque pour obtenir O (1) append et pop de l'avant.

Answer 5

cela ressemble à un peu de tests empiriques pourrait être la meilleure chose à faire ici - les problèmes de second ordre pourraient améliorer une approche dans la pratique, même si elle n'est pas meilleure en théorie.