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

У вас не закончится память, используя реализацию list, но производительность будет низкой. Из документов:

Хотя объекты list поддерживают аналогичные операции, они оптимизированы для быстрых операций с фиксированной длиной и требуют O(n) затрат на перемещение памяти для операций pop(0) и insert(0, v), которые изменяют как размер, так и положение базового представления данных.

Таким образом, использование deque будет намного быстрее.

В некоторых ответах утверждалось «10-кратное» преимущество в скорости для deque по сравнению со списком, используемым как 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 Essential Reference, четвертое издание Бизли. , с. 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) и вытолкнуть спереди.

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