Эффективность использования списка Python в качестве очереди
Автор вопроса: Eli CourtwrightОтветов: 5
Коллега недавно написал программу, в которой он использовал список Python в качестве очереди. Другими словами, он использовал .append(x), когда нужно было вставить элементы, и .pop(0), когда нужно было удалить элементы.
Я знаю, что в Python есть collections.deque, и я пытаюсь выяснить, потратить свое (ограниченное) время, чтобы переписать этот код, чтобы использовать его. Предполагая, что мы выполняем миллионы добавлений и извлечений, но никогда не имеем более нескольких тысяч записей, будет ли проблемой использование его списка?
В частности, будет ли базовый массив, используемый реализацией списка Python, продолжать бесконечно расти, иметь миллионы точек, даже если список содержит только тысячу элементов, или Python в конечном итоге выполнит realloc и освободит часть этой памяти?
Базовый актив НЕ продолжает расти бесконечно (остается лишь немного больше, чем его максимальная отметка). Но проблемы O (N) и O (1), выделенные в некоторых ответах, могут быть важными. Alex Martelli 19.08.2009
У вас не закончится память, используя реализацию list, но производительность будет низкой. Из документов:
Хотя объекты list поддерживают аналогичные операции, они оптимизированы для быстрых операций с фиксированной длиной и требуют O(n) затрат на перемещение памяти для операций pop(0) и insert(0, v), которые изменяют как размер, так и положение базового представления данных.
Таким образом, использование deque будет намного быстрее.
Ответ 2 · рейтинг 76 · Alex Martelli
В некоторых ответах утверждалось "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 мкс больше или меньше не будут иметь существенного значения).
Некоторые библиотечные модули предоставляют новые типы, которые превосходят встроенные в определенных задачах. Например, тип collections.deque обеспечивает функциональность, аналогичную списку, но оптимизирован для вставки элементов с обоих концов. Список, напротив, эффективен только при добавлении элементов в конец. Если вы вставляете элементы спереди, все остальные элементы необходимо сместить, чтобы освободить место. Время, необходимое для этого, растет по мере того, как список становится все больше и больше. Просто чтобы дать вам представление о разнице, вот измерение времени вставки миллиона элементов в начале списка и очереди:
Каждый .pop(0) занимает N шагов, так как список должен быть реорганизован. Требуемая память не будет расти бесконечно, а будет ровно столько, сколько требуется для удерживаемых элементов.
Я бы рекомендовал использовать deque, чтобы добавить O(1) и вытолкнуть спереди.
Ответ 5 · рейтинг 2 · Peter
Звучит так, будто здесь лучше всего провести небольшое эмпирическое тестирование - проблемы второго порядка могут сделать один подход лучше на практике, даже если он не лучше в теории.
