5 .6 . Очереди (с дисциплиной доступа FIFO)
195
>>> q.get()
'есть'
>>> q.get()
'спать'
>>> q.get()
'программировать'
>>> q.get_nowait()
queue.Empty
>>> q.get()
# Блокирует / ожидает бесконечно...
multiprocessing .Queue — очереди совместных заданий
Такая реализация очереди совместных заданий позволяет выполнять па-
раллельную обработку находящихся в очереди элементов многочисленны-
ми параллельными рабочими процессами
1
. Процессно-ориентированное
распараллеливание популярно в Python из-за глобальной блокировки
интерпретатора (GIL), которая препятствует некоторым формам парал-
лельного исполнения в единственном процессе интерпретатора.
В качестве специализированной реализации очереди, предназначенной
для обмена данными между процессами, очередь
multiprocessing.Queue
упрощает распределение работы по многочисленным процессам с целью
преодоления ограничений GIL. Этот тип очереди может хранить и пере-
давать любой консервируемый (модулем
pickle
) объект через границы
процессов.
>>> from multiprocessing import Queue
>>> q = Queue()
>>> q.put('есть')
>>> q.put('спать')
1
См. документацию Python «multiprocessing.Queue»:
https://docs .python .org/3 .6/library/
multiprocessing .html#multiprocessing .Queue
196 Глава 5 • Общие
структуры данных Python
>>> q.put('программировать')
>>> q
>>> q.get()
'есть'
>>> q.get()
'спать'
>>> q.get()
'программировать'
>>> q.get()
# Блокирует / ожидает бесконечно...
Ключевые выводы
Python содержит несколько реализаций очередей в качестве составной
части ядра языка и его стандартной библиотеки.
Объекты-списки
list
могут использоваться в качестве очередей, но
это обычно не рекомендуется делать из-за низкой производитель-
ности.
Если вы не ищете поддержку параллельной обработки, то реализация,
предлагаемая очередью
collections.deque
, является превосходным
вариантом по умолчанию для реализации в Python структуры данных
с дисциплиной доступа FIFO, то есть очереди. Она обеспечивает ха-
рактеристики производительности, которые можно ожидать от хоро-
шей реализации очереди, а также может применяться в качестве стека
(очереди с дисциплиной доступа LIFO).
5 .7 . Очереди с приоритетом
Очередь с приоритетом представляет собой контейнерную структуру дан-
ных, которая управляет набором записей с полностью упорядоченными
5 .7 . Очереди
с приоритетом 197
ключами
1
(например, числовым значением
веса) с целью обеспечения бы-
строго доступа к записи с наименьшим или наибольшим ключом в наборе.
Очередь с приоритетом можно представить как видоизмененную очередь:
вместо получения следующего элемента по времени вставки она получает
элемент
с самым высоким приоритетом. Приоритет отдельных элементов
определяется примененным к их ключам упорядочением.
Очереди с приоритетом широко используются для решения задач пла-
нирования, например предоставления предпочтений задачам с более
высокой актуальностью.
Представьте работу планировщика задач операционной системы:
В идеальном случае высокоприоритетные задачи в системе (например,
игра в компьютерную игру в реальном времени) должны иметь пред-
почтение перед задачами с более низким приоритетом (например, ска-
чивание обновлений в фоновом режиме) . Организовывая предстоящие
задачи в очередь с приоритетом, которая использует актуальность за-
дачи в качестве ключа, планировщик задач может быстро выбирать за-
дачи с самым высоким приоритетом и давать им выполняться в первую
очередь .
В этом разделе вы увидите несколько вариантов реализации очередей
с приоритетом в Python с помощью встроенных структур данных либо
структур данных, которые поставляются вместе со стандартной библио-
текой Python. Каждая реализация будет иметь свои собственные преиму-
щества и недостатки, но, по моему мнению, в каждом распространенном
сценарии есть свой победитель.
Давайте узнаем, что лучше.
list — поддержание сортируемой очереди вручную
Вы можете использовать сортированный список
list
, который позволяет
быстро идентифицировать и удалять наименьший или наибольший эле-
мент. Недостатком является то, что вставка новых элементов в список
является медленной
O(
n) операцией.
1
См. Википедию «Полная упорядоченность»:
https://en .wikipedia .org/wiki/Total_order
и
https://ru .wikipedia .org/wiki/Линейно_упорядоченное_множество
198 Глава 5 • Общие структуры данных Python
Несмотря на то что точка вставки может быть найдена за
O(log n) время
с помощью алгоритма
bisect.insort
1
стандартной библиотеки, это реше-
ние всегда находится во власти медленного шага вставки.
Поддержание упорядоченности путем добавления в конец списка и пере-
сортировки также занимает минимум
O(n log n) времени. Еще один недо-
статок — вам придется вручную заботиться о пересортировке списка во
время вставки новых элементов. Пропустив этот шаг, можно легко внести
ошибки, и ответственность за них всегда будет на вас как на разработчике.
Поэтому я убежден, что сортированные списки подходят как очереди
с приоритетом только в тех случаях, когда вставок немного.
q = []
q.append((2, 'программировать'))
q.append((1, 'есть'))
q.append((3, 'спать'))
Do'stlaringiz bilan baham: 
