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

Ответ 1

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

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

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

Ответ 2

В некоторых ответах было указано преимущество "10x" скорости для deque vs list-used-as-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 микросекунд или примерно на партию append/pop и решаете, насколько значительна эта потеря (хотя, если это все, что вы делаете с этим контейнером, deque не имеет недостатков, так что вы может также переключиться, даже если 5 мкс больше или меньше не будет иметь большого значения).

Ответ 3

От Beazley Python Essential Reference, четвертое издание, стр. 194:

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

И далее следует этот пример кода:

>>> from timeit import timeit
>>> timeit('s.appendleft(37)', 'import collections; s = collections.deque()', number=1000000)
0.13162776274638258
>>> timeit('s.insert(0,37)',  = []', 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)',  = []', 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

Ответ 4

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

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

Ответ 5

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