Как использовать Python для приоритетной очереди?
[
Реализация очередей в Python
Очереди являются основой множества алгоритмов, применяемых в играх, искусственном интеллекте, спутниковой навигации и планировании задач. Они являются одними из основных «абстрактных типов данных», которые студенты учат уже на ранних этапах своего обучения в области компьютерных наук. В то же время программные инженеры часто используют более высокоуровневые «очереди сообщений», чтобы достичь лучшей масштабируемости «микросервисной архитектуры». Использование очередей в Python просто интересно!
Python предоставляет несколько встроенных типов очередей, которые вы увидите в действии в этом руководстве. Вы также получите краткое введение в теорию очередей и их типы. Наконец, вы рассмотрите некоторые внешние библиотеки для подключения к популярным брокерам сообщений, доступным на основных платформах облачных сервисов.
В этом учебнике вы узнаете, как:
- Различать различные типы очередей
- Реализовать тип данных «очередь» в Python
- Решать практические проблемы, применяя правильную очередь
- Использовать «надежные в потоках», «асинхронные» и «межпроцессные» очереди Python
- Интегрировать Python с распределенными брокерами сообщений через библиотеки
Для получения наибольшей пользы от этого урока рекомендуется иметь предварительное знание о основах языка Python.
Обзор типов очередей
Давайте начнем с изучения различных типов очередей.
Очередь: Первым пришел — первым обслужен (FIFO)
Очередь FIFO (First-In, First-Out) - это простая структура данных, в которой элементы добавляются в конец очереди и извлекаются из начала очереди. Это означает, что элементы пребывают в очереди в том порядке, в котором они были добавлены.
Стек: Последним пришел — первым обслужен (LIFO)
Стек LIFO (Last-In, First-Out) - это еще одна простая структура данных, в которой элементы добавляются и извлекаются только с одного конца. В стеке элементы хранятся в обратном порядке - последний добавленный элемент будет первым, который будет извлечен.
Дек: двунаправленная очередь
Дек (Double-Ended Queue) - структура данных, в которой элементы можно добавлять и извлекать с обоих концов. Вы можете добавлять элементы как в начало, так и в конец очереди, и извлекать элементы как с начала, так и с конца.
Приоритетная очередь: отсортировано от большего к меньшему
Приоритетная очередь (Priority Queue) - это очередь, в которой каждому элементу присваивается приоритет, а элементы хранятся в порядке сначала наиболее приоритетных. В отличие от обычной очереди, где элементы обслуживаются в порядке их добавления, приоритетная очередь позволяет добавлять элементы с разным уровнем приоритета и извлекать их в порядке убывания приоритета.
Реализация очередей в Python
Теперь, когда мы знаем основные типы очередей, давайте рассмотрим, как реализовать их в Python.
Представление FIFO и LIFO очередей с помощью дека
На практике очень удобно реализовывать FIFO и LIFO очереди с помощью двунаправленной очереди (deque) из встроенного модуля collections. Дека предоставляет эффективную реализацию буферизованного хранилища данных, упорядоченного по индексам, и позволяет быстро и эффективно добавлять элементы как в начало, так и в конец.
Создание пользовательского типа данных “очередь”
Мы также можем создать собственный тип данных «очередь», используя различные встроенные структуры данных, такие как список или связанный список. В этом случае мы будем работать непосредственно с методами добавления и извлечения элементов, чтобы обеспечить правильное поведение очереди.
Создание пользовательского типа данных “стек”
Аналогично пользовательский тип данных «стек» может быть реализован с использованием встроенных структур данных в Python. В этом случае мы будем использовать методы добавления и извлечения элементов только с одного конца.
Представление приоритетных очередей с помощью кучи
Приоритетные очереди могут быть реализованы с использованием структуры данных «куча», которая является специальным видом дерева, где каждый узел имеет больший приоритет, чем его потомки. Встроенный модуль heapq предоставляет функции для работы с кучами, которые можно использовать для реализации приоритетной очереди в Python.
Создание пользовательского типа данных “приоритетная очередь”
Кроме того, мы можем создать пользовательскую реализацию приоритетной очереди, основанную на структуре данных куча. В этом случае мы будем использовать методы добавления и извлечения элементов приоритетной очереди, чтобы автоматически обеспечить сортировку по приоритету.
Обработка крайних случаев в вашей приоритетной очереди
В процессе работы с приоритетной очередью возникнут ситуации, когда добавленные элементы будут иметь одинаковый приоритет или когда вы захотите извлечь элементы из пустой очереди. Важно предусмотреть обработку этих крайних случаев в вашей реализации приоритетной очереди.
Рефакторинг кода с использованием класса Mixin
Иногда вам может потребоваться добавить поведение, общее для нескольких классов, в свой код. В таких случаях вы можете использовать механизм наследования и создавать классы «Миксины», которые содержат общий код и могут быть добавлены к другим классам для целей повторного использования.
Использование очередей на практике
Теперь рассмотрим, как использовать очереди на практике, на примере решения реальной задачи.
Образец данных: Дорожная карта Великобритании
Давайте представим, что у нас есть образец данных - это карта дорог Великобритании. Мы хотим использовать очередь для обработки маршрутов между городами.
Объектное представление городов и дорог
Мы можем создать объектное представление городов и дорог, чтобы легко использовать эту информацию при поиске маршрутов. Каждый город будет представлен объектом, содержащим информацию о его имени и расположении на карте. Дороги будут представлены объектами, содержащими информацию о начальном и конечном городе, а также о расстоянии между ними.
Поиск в ширину с использованием очереди FIFO
Один из наиболее распространенных алгоритмов поиска маршрута между двумя пунктами на графе - это алгоритм поиска в ширину. Он основан на идее исследования всех вершин графа, находящихся на одном уровне от начальной вершины, перед переходом на следующий уровень.
Поиск кратчайшего пути с использованием обхода в ширину
При использовании алгоритма обхода в ширину можно найти кратчайший путь между двумя вершинами. Для этого необходимо сохранить информацию о родительских вершинах при обходе графа и затем восстановить путь от начальной вершины до целевой вершины.
Поиск в глубину с использованием очереди LIFO
Еще один алгоритм поиска маршрута на графе - это алгоритм поиска в глубину. В отличие от алгоритма поиска в ширину, он исследует все возможные пути из одной вершины, прежде чем переходить к следующей.
Использование алгоритма Дейкстры с использованием приоритетной очереди
Алгоритм Дейкстры - это алгоритм нахождения кратчайшего пути на взвешенном графе. Он использует очередь с приоритетом, чтобы выбрать следующую вершину для исследования, и обновляет расстояния до каждой вершины, если находит короче путь.
Использование потокобезопасных очередей
Python предоставляет несколько встроенных потокобезопасных очередей, которые позволяют обрабатывать данные в многопоточных приложениях без опасности состояния гонки и других проблем, связанных с одновременным доступом к данным из нескольких потоков.
queue.Queue
queue.Queue - это простая потокобезопасная очередь, которая использует блокировки для синхронизации доступа к данным. Эта очередь предоставляет методы для добавления элементов в очередь и извлечения элементов из очереди с использованием FIFO-порядка.
queue.LifoQueue
queue.LifoQueue - это потокобезопасная очередь, которая реализует LIFO-подход к обработке элементов. Она аналогична стеку LIFO и поддерживает те же самые методы добавления и извлечения элементов с добавлением и извлечением только с одного конца.
queue.PriorityQueue
queue.PriorityQueue - это потокобезопасная очередь, которая реализует приоритетное добавление элементов в очередь. Каждый элемент при добавлении получает приоритет, и элементы извлекаются из очереди в порядке убывания приоритета.
Использование асинхронных очередей
Для обработки данных в асинхронных приложениях Python предоставляет несколько встроенных асинхронных очередей, которые позволяют выполнять операции ввода-вывода без блокировки основного потока выполнения.
asyncio.Queue
asyncio.Queue - это асинхронная очередь, которая позволяет отправлять и получать элементы асинхронно. Она позволяет организовать очередь из сколь угодно корутин и выполнять операции добавления и извлечения элементов асинхронно.
asyncio.LifoQueue
asyncio.LifoQueue - это аналог asyncio.Queue, который реализует LIFO-подход к обработке элементов. Как и синхронный аналог, он поддерживает методы добавления и извлечения элементов только с одного конца.
asyncio.PriorityQueue
asyncio.PriorityQueue - это асинхронная очередь с приоритетом, которая реализует приоритетное добавление элементов. Извлечение элементов происходит в порядке убывания приоритета, а добавление элемента может происходить асинхронно.
Использование очередей межпроцессного взаимодействия (IPC)
Если у вас есть несколько процессов, выполняющих работу параллельно, вы можете использовать очереди для обмена данными между процессами без необходимости синхронизации или блокировки процессов.
Использование очереди multiprocessing.Queue для межпроцессного взаимодействия (IPC)
multiprocessing.Queue - это аналог queue.Queue, но с поддержкой межпроцессного взаимодействия (IPC). Он позволяет обмениваться данными между несколькими процессами, используя механизмы IPC, предоставляемые операционной системой.
Разворот хэша MD5 на однопоточном процессе
Один из способов использования межпроцессных очередей - это распределение вычислительной нагрузки между несколькими процессами. Например, вы можете разделить вычисление хэшей MD5 для большого набора данных между несколькими процессами, чтобы ускорить работу.
Равномерное распределение нагрузки в виде блоков
Еще один способ использования межпроцессных очередей - это распределение равномерной нагрузки между процессами. Например, вы можете разделить обработку большого файла на блоки и распределить эти блоки между несколькими процессами, чтобы обрабатывать несколько блоков одновременно.
Обмен данными в полнодуплексном режиме
Очереди межпроцессного взаимодействия могут использоваться для передачи данных между процессами в полнодуплексном режиме, когда процессы могут одновременно отправлять и получать данные с общей очереди.
Завершение потока работника с использованием «ядовитой пилюли»
Очереди межпроцессного взаимодействия могут использоваться для остановки работника в многопоточном приложении. Вы можете отправить “ядовитую пилюлю” в очередь, чтобы уведомить поток работника о его завершении.
Анализ производительности параллельного выполнения
Очереди межпроцессного взаимодействия позволяют произвести анализ производительности параллельного выполнения, сравнив время, затраченное на последовательное выполнение задачи с временем, затраченным на параллельное выполнение при использовании очереди.
Интеграция Python с распределенными брокерами сообщений
Иногда вам может потребоваться интегрировать Python с распределенными брокерами сообщений, такими как RabbitMQ, Redis или Apache Kafka, чтобы передавать данные между разными компонентами вашей системы.
RabbitMQ: pika
RabbitMQ - это популярный брокер сообщений, который используется для создания и управления очередями сообщений. Библиотека pika позволяет интегрировать Python с RabbitMQ, чтобы передавать данные между клиентом и сервером.
Redis: redis
Redis - это быстрый ин-memory хранилище данных, которое поддерживает различные структуры данных, включая очереди. Библиотека redis позволяет интегрировать Python с Redis, чтобы отправлять и получать данные из очередей Redis.
Apache Kafka: kafka-python3
Apache Kafka - это промышленный брокер сообщений, предназначенный для обработки потоков данных в реальном времени. Библиотека kafka-python3 позволяет интегрировать Python с Apache Kafka, чтобы отправлять и получать данные из очередей Kafka.
Заключение
Очереди - это важный инструмент в программировании, который может быть использован для решения множества задач. В Python вы можете использовать встроенные типы очередей, такие как deque, Queue, LifoQueue и PriorityQueue, или можете создать собственные типы данных очередей с использованием встроенных структур данных и классов. Кроме того, Python предоставляет потокобезопасные и асинхронные очереди для использования в многопоточных и асинхронных приложениях. Вы также можете использовать очереди межпроцессного взаимодействия для обмена данными между процессами и интегрировать Python с распределенными брокерами сообщений для создания распределенных систем.
В этом учебнике мы рассмотрели основные типы очередей, их реализацию в Python и практическое использование очередей для решения задач. Теперь вы можете применять свои знания о очередях в своих собственных проектах.
