Очереди в Python

автор

Как запустить FIFO структуру данных в Python, пользуясь только встроенными типами данных и классами из стандартной библиотеки. Очередь – это набор объектов, который поддерживает быструю семантику first-in, first-out (FIFO) для вставки и удаления. Операции вставки и удаления иногда называют enqueue и dequeuer. В отличие от списков и массивов, очереди, как правило, не пропускают случайный доступ к содержащимся объектам.

Аналогия очереди first-in, first-out на пальцах

Представьте ряд питонистов, в ожидании получения бейджиков на конференции в день регистрации на PyCon. Новые дополнения в ряде находятся в конце очереди, так как новые люди становятся в очередь на конференцию в ожидании бейджиков. Сокращение очереди (подача) происходит в её начале, так как разработчики получают свои бейджи с новыми кепками с надписью SWAG и покидают очередь.

Другой способ описать такую структуру данных, как очередь, это представить её как трубку:

Новые объекты (молекулы воды, шарики для тенниса, и т.д.) помещаются в один конец трубки, и двигаются к другому, когда вы, или что-то другое пропихиваете их вдоль трубки. Пока объекты находятся в очереди (в нашем случае это трубка), вы не можете достать их. Единственный способ взаимодействия с объектами в очереди, это добавить новые объекты в конце очереди (enqueuer) или убрать существующие из начала (dequeuer) трубки.

Очереди похожи на стеки, но отличаются способом удаления элементов:

В случае с очередью вы удаляете объект, который был недавно добавлен (по принципу первый вошел – первым вышел first-in, first-out или FIFO), в случае сто стеком вы удаляете последний добавленный элемент (последним зашел – первым вышел, last-in, first-out or LIFO).

С точки зрения производительности, верная реализация очереди заключается в выделении О(1) времени для вставки и удаления операций. Существует две основные операции, используемые в очереди и они должны выполнять работу быстро и корректно. Очереди Python имеют широкий ряд приложений в алгоритмах, а также все необходимое для составления графиков, а также решения параллельных проблем в программировании. Короткий и удобный алгоритм под названием BFS (breadth-first search) годится для работы с такими структурами данных как tree и graph.

Алгоритмы планирования часто используют приоритетные очереди изнутри. Существуют определенные виды очередей: вместо получения следующего элемента в соответствии с указанным временем вставки, приоритетная очередь извлекает элемент с самым высоким приоритетом. Приоритет отдельных элементов определяется очередью на основании порядка применяемых к ним ключам. Однако, обычная очередь, не будет переопределять порядок объектов, которые в ней находятся. Вы получаете только то, и в том порядке, в каком вы помещали объекты в очередь (пример с трубкой). Python позволяет выполнить несколько реализаций очереди, каждая из которых имеет небольшие отличия. Давайте рассмотрим их:

Встроенный список

Мы можем использовать обычный список в качестве очереди, но это не очень эффективно с точки зрения производительности. Списки слишком медленные для этой задачи, так как вставка и удаление элемента с начала требует сдвига всех прочих элементов по одному, на это уходит О(n) времени. В связи с этим, я не спешу рекомендовать список в качестве временной очереди в Python (разве что вы имеете дело с небольшим количеством элементов).

Класс collections.deque

Класс deque реализует двухконечную очередь, которая поддерживает добавление и удаление элементов с обоих концов в течение О(1) времени. Объекты deque представлены в виде двусвязных списков, что дает им превосходную производительность для входящих и выходящих элементов, но при этом у него плохая производительность O(n) при работе со случайно принимаемыми элементами в середине очереди. В связи с тем, что deque поддерживает вставку и удаление элементов одинаково хорошо, они могут поддерживать и очереди и стеки. collections.deque это отличное решение, если вы ищите структуру данных очереди в Python в стандартной библиотеке.

Класс queue.Queue

Такая реализация очереди в стандартной библиотеке является синхронизированной и предоставляет блокировку семантики для поддержки нескольких конкурирующих производителей и потребителей. Модуль queue содержит несколько других классов, реализующих мульти-продюсера, очереди мульти-потребители , которые полезны в параллельных вычислениях. В зависимости от причины использования, закрытие семантики может быть полезным, или просто привести к ненужному перерасходу. В данном случае, вам лучше будет использовать collections.deque как очередь общего назначения.

Класс multiprocessing.Queue

Это реализация очереди с разделенными функциями, которые позволяет находящимся в очереди объектам быть обработанными параллельно несколькими одновременно работающими процессами. Основанная на процессах паралеллизация очень популярна в Python, из-за глобального блокиратора интерпретатора GIL. multiprocessing.Queue используется при разделении данных между процессами и может хранить любой пригодный объект.

Как использовать multiprocessing.Queue в качестве очереди FIFO:

 

Вердикт

Неплохой выбор – это collections.deque. Если вас не интересует поддержка параллельной обработки, реализация очереди, выполняемая collections.deque – отличный дефолтный выбор для создания структуры данных очереди FIFO в Python. У него хорошие характеристики, которые нужны при реализации очереди, также он может быть использован в качестве стека.

Вам может быть интересно