Эффективность использования Python перечисляет как очередь

В некоторых ответах утверждалось "10-кратное" преимущество в скорости для двухсторонней очереди по сравнению со списком-используемым как FIFO, когда оба имеют 1000 записей, но это немного завышено:

$ 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 - ваш друг - действительно полезный и простой подход к микробенчмаркингу! С его помощью вы, конечно, также можете тривиально исследовать производительность в гораздо меньших случаях:

$ 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

(не сильно отличается для 12 элементов вместо 100 кстати), и в гораздо более крупных:

$ 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

Вы можете видеть, что требование O (1) производительность для deque хорошо обоснована, в то время как список более чем вдвое медленнее, около 1000 элементов, на порядок около 10 000. Вы также можете видеть, что даже в таких случаях вы тратите только 5 микросекунд или около того на пару добавление / извлечение и решаете, насколько значительны эти потери (хотя, если это все, что вы делаете с этим контейнером, у deque нет недостатков, поэтому вы с таким же успехом можно переключиться, даже если более или менее 5 мкс не будут иметь большого значения).

Из книги Бизли «Существенный справочник по Python», четвертое издание , с. 194:

Некоторые библиотечные модули предоставляют новые типы которые превосходят встроенные в определенные задачи. Например, Тип collections.deque предоставляет функциональность аналогична списку, но был оптимизирован для вставка предметов с обоих концов. А список, напротив, эффективен только при добавлении элементов в конце. Если вы вставляете элементы спереди, все другие элементы нужно переместить чтобы освободить место. Время требуется для этого растет по мере того, как список становится все больше и больше. Просто дать Вы можете представить себе разницу, вот измерение времени для вставки одного миллиона элементов в начало списка и двухсторонней очереди:

И вот следующий пример кода:

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

Время с моей машины.

2012 -07-01 Обновление

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

Каждый .pop (0) выполняет N шагов, так как список должен быть реорганизован. Требуемая память не будет увеличиваться бесконечно, а будет только настолько большой, насколько это необходимо для хранимых элементов.

Я бы рекомендовал использовать deque , чтобы получить O (1) добавление и извлечение спереди.

, похоже, что небольшая эмпирическая проверка может быть Лучшее, что можно сделать здесь - вопросы второго порядка могут улучшить один подход на практике, даже если он не лучше в теории.