Как сделать очередь в python

Добавил пользователь Alex
Обновлено: 10.09.2024

Структуры данных, которые мы рассмотрим на этом уроке, объединены тем, что создаются на основе последовательностей для эффективного решения определенного круга задач. В компилируемых языках эти структуры можно создать на основе встроенных массивов, но в python выбор невелик. List можно использовать для моделирования стека и создания кучи. Для работы с очередью и кучей в python разработаны специальные модули.
Начнем знакомство с дека. Дек, двусвязная очередь (от англ. deque — double ended queue) — структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов массива. Это позволяет многие задачи решать непосредственно с помощью дека, абстрагируясь до нужной структуры данных. Дело в том, что такие структуры данных как очередь и стек создаются на основе дека. В python дек реализован в классе collections.deque (док. collections — Container datatypes).
Реализация дека такова, что элементы добавляются или удаляются с обоих концов массива очень эффективно. Также эффективно происходит увеличение объема массива в обоих направлениях. Поскольку дек – это динамический массив, такое увеличение не ограничено (если не указана максимальная длина). Если указывается максимальная длина дека, то добавление элементов сверх этого значения приведет к отбрасыванию соответствующего количества элементов с противоположного конца массива.
Поскольку тип deque не является встроенным типом, а реализован в модуле, то перед использованием дека модуль нужно импортировать. Конструктор объекта дек выглядит следующим образом:

Ниже перечислены методы класса deque модуля collections .

Методы класса deque

Метод	Описание
append(x)	Добавляет элемент справа
appendleft(x)	Добавляет элемент слева
clear()	Удаляет все элементы и обнуляет длину
copy()	Создаёт неполную копию дека
count(x)	Подсчитывает количество элементов равных х
extend(iterable)	Добавление коллекции справа
extendleft(iterable)	Добавление коллекции слева
index(x[, start[, stop]])	Возвращает позицию первого вхождения элемента равного x. Возбуждает исключение ValueError, если он не найден.
insert(i, x)	Вставка x в позицию i. Если вставка невозможна по причине MAXLEN, возбуждается исключение IndexError.
pop()	Удаляет и возвращает элемент с правой стороны двусторонней очереди. Если нет ни одного элемента, то возбуждается исключение IndexError
popleft()	Тоже, слева
remove(value)	Удаляет первое вхождение элемента со значением value. Если не найден, то возбуждается ValueError
reverse()	Реверс элементов дека на месте, а затем возвращается None
rotate(n=1)	Поворот Deque на n шагов вправо. Если n является отрицательным, то поворот влево. Если Deque не пустой, то вращение на один шаг вправо эквивалентно d.appendleft(d.pop()) , а вращение на один шаг влево эквивалентно d.append(d.popleft())
maxlen	Максимальный размер дека или None, если неограничен.

Нужно сказать, что дек – это последовательность, которая предоставляет последовательный доступ к элементам. Решим с помощью дека следующую задачу.
Задача 1. Дан массив Ar и срез этого массива Ar[m:n] , где m . Определить на этом отрезке (срезе) минимальный элемент. Задачу эту решить с помощью дека.

Структура данных stack (стек)

Структура данных queue (очередь)

Структура данных heap (куча). Очередь с приоритетом (priority queue)

Куча (другие названия: двоичная куча, пирамида, сортирующее дерево) — это структура данных представленная в виде дерева. Свойство кучи: если B является узлом-потомком узла A , то ключ A ключ B . Из этого следует, что элемент с наименьшим ключом всегда является корневым узлом кучи. Такая разновидность кучи называется min -куча. Если A >= B , то мы имее дело с другой разновидностью кучи - max -куча. В python реализована min -куча.

Для двоичного дерева min -кучи должны выполняться три условия:

Для реализации кучи можно использовать последовательность list . Корневой элемент кучи -> A[0] , а потомки элемента A[i] -> A[2*i+1] и A[2*i+2] .

Тогда индексы в виде дерева можно изобразить следующим образом:

Высота кучи определяется как высота двоичного дерева. То есть, она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев.
Куча является максимально эффективной реализацией абстрактного типа данных, который называется очередью с приоритетом ( priority queue ). Очередь с приоритетом применяется в программах, которые включают в себя поиск максимального (или минимального) элемента в некотором массиве данных. С помощью очереди с приоритетом можно организовать планировщик задач, поиск оптимальных путей и прогнозирование событий.
В python очередь с приоритетом реализована в модуле heapq . Ниже в таблице перечислены функции этого модуля.

Функции heapq

Функция	Описание
heappush(heap, item)	Помещает значение item в кучу, сохраняя её порядок
heappop(heap)	Извлекает и возвращает элемент из кучи, сохраняя её порядок. Чтобы получить первый элемент без извлечения используйте heap[0]
heappushpop(heap, item)	Вставляет элемент в кучу и при этом извлекает и возвращает первый элемент
heapify(x)	Преобразует список x в кучу на месте за линейное время
heapreplace(heap, item)	Удаляет и возвращает первый элемент из кучи, а также вставляет новый элемент item. Размер кучи не меняется.
merge(*iterables, key=None, reverse=False)	Объединяет несколько отсортированных последовательностей в одну. Возвращает итератор по отсортированным значениям
nlargest(n, iterable, key=None)	Возвращает список из n наибольших элементов последовательности iterable.
nsmallest(n, iterable, key=None)	Возвращает список из n наименьших элементов последовательности iterable.

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

Решим следующую задачу.
Задача 4. В игре участвуют N игроков ( N >= 3 ). В каждом раунде пользователи по очереди бросают кость. Результаты суммируются по каждому раунду, количество которых не ограничено. По итогам игры выявляются три участника с максимальным результатом. Абсолютным победителем является игрок, первым набравший более 20 очков.

Современное программное обеспечение проектируется так, что его функции и задачи могут выполняться параллельно. Python предоставляет программисту мощный набор инструментов для работы с потоками в библиотеке threading.

Как работает многопоточность

Многопоточность — это выполнение программы сразу в нескольких потоках, которые выполняют её функции одновременно.

Многопоточное программирование можно спутать с мультипроцессорным. На самом деле их концепции очень похожи, но если в первом случае программа работает с потоками, то в другом — с процессами. Разница между потоками и процессами проста: потоки имеют общую память, поэтому изменения в одном потоке видны в других, а процессы используют разные области памяти.

На самом деле, если рассмотреть одноядерный процессор, операции из разных потоков не выполняются параллельно. Одно ядро может выполнить только одну операцию в единицу времени, но так как операции выполняются очень быстро, создается ощущение параллельного выполнения, псевдопараллельность. По-настоящему параллельно программы могут работать только на многоядерных процессорах, где каждое ядро может выполнять операции независимо от других.

Отличным примером использования многопоточности является программа, где отрисовка графического интерфейса и обработка ввода пользователя управляются разными потоками. Если бы обе задачи были помещены в один поток, отрисовка интерфейса прерывалась бы каждый раз, когда программа получает ввод от пользователя. Использование двух потоков позволяет сделать выполнение этих функций независимым друг от друга.

Однако при выполнении многопоточной программы на одноядерном процессоре, её производительность будет ниже, чем если бы она была написана в один поток. Это происходит потому, что на реализацию и управление потоками тратится дополнительная память.

Можно ли считать threading многопоточным?

В Python используется GIL (Global Interpreter Lock), который однопоточный. Все потоки, которые создаются с помощью threading будут работать внутри потока GIL. В связи с этим они будут обрабатываться только одним ядром. Ни о какой работе одновременно на нескольких физических ядрах процессора не может быть и речи.

А так как threading будет выполняться только на одном ядре процессора, то нету преимущества по скорости, только наоборот — threading замедлит работу.

Но без него никуда не деться, если вам нужно выполнять несколько задач одновременно:

Обрабатывать нажатие кнопки в графическом интерфейсе, например с помощью Tkinter. Если по нажатию кнопки надо производить много действий, которые требуют времени, то эти действия надо выполнять в другом потоке, чтобы графический интерфейс не подвис на это время. Соответственно кнопки надо блокировать, а как поток завершит вычисления — обратно разблокировать.
Если наша программа работает одновременно с несколькими подключенными устройствами. Они могут быть подключены к разным COM-портам.
Если мы загружаем файлы из сети и одновременно обрабатываем уже загруженные.
И так далее…

Если нам нужно, чтобы наша программа работала на нескольких физических ядрах процессора одновременно, то следует обратить внимание на другой модуль — Multiprocessing.

В чём преимущества тогда модуля Threading по сравнению с Multiprocessing? Рассмотрим их:

Таким образом, если наша программа будет запускаться на одноядерном компьютере или нагрузка на процессор будет не большой, то Threading — оптимальный выбор.

Подключение библиотеки threading

Threading – это стандартный модуль, который поставляется вместе с интерпретатором. Программисту не нужно устанавливать его, достаточно просто подключить модуль с помощью команды:

Работать с потоками можно, создавая экземпляры класса Thread. Чтобы создать отдельный, поток нужно создать экземпляр класса и применить к нему метод start() . Вот пример:

Здесь мы функцию mydef запустили в отдельном потоке. В качестве аргументов функции передали числа 1 и 2.

threading.Thread()

Эта конструкция позволяет создать новый поток, создав экземпляр класса Thread. Вот как выглядят её аргументы:

Она принимает аргументы:

Рассмотрим их подробнее:

Демоны

Демонами называют процессы, которые работают в фоновом режиме. В Python для демона есть более конкретное значение: демонический поток или поток демона. В отличие от обычных потоков поток демона автоматически завершает свою работу при закрытии программы. Иными словами, программа не будет ожидать завершения демонического потока, при её закрытии эти потоки уничтожаются, в каком бы состоянии они не находились.

Демонические потоки используют для выполнения операций, выполняемых в бесконечном цикле. В других случаях обычно используют простые потоки, которые задерживают закрытие программы, пока не завершат выполнение всех операций. Использование демонических потоков позволяет операции в фоновом режиме, которые обычно не связаны с изменением и сохранением долгосрочных данных.

Например, если программа полностью перезаписывает содержимое файла, и механизм перезаписи реализован в демоническом потоке, то при неожиданном выходе из программы данные потеряются.

В демонические потоки часто помещают функции по рисованию графического интерфейса. Рисование интерфейса — бесконечный процесс, который завершается сразу после выхода из программы, если просто поместить его в обычный поток, это будет препятствовать закрытию программы.

Методы для работы с потоками

Для создания и управления потоками используются различные методы класса Thread. С их помощью можно легко манипулировать сразу несколькими потоками и определять их поведение.

start()

Он используется для запуска созданного потока. После использования threading.Thread() создаётся новый поток, однако он неактивен. Для того чтобы он начал работу, используется метод start().

Здесь пока мы не вызвали метод start , функция myfunc не будет запущена.

Этот метод блокирует выполнение потока, который его вызвал, до тех пор пока не завершится поток, метод которого был вызван. То есть если в потоке thread1 был вызван метод потока thread2: thread2.join(), то поток thread1 будет приостановлен до тех пор, пока выполнение thread2 не завершится.

С помощью этого метода можно заставить программу дождаться завершения демонического потока. Например, если вызвать метод в основном потоке, то программа не завершится, пока не выполнится демонический поток.

У метода join() есть аргумент timeout . По умолчанию он имеет значение None, но программист может передать в него число с плавающей точкой.

Если аргумент имеет значение по умолчанию, то выполнение потока приостанавливается, пока выполняется поток метода.

Если передать в качестве аргумента число, то для метода join() установится время ожидания, когда оно истечёт, поток продолжит свою работу.

Например, thr1.join(100) означает, что будет ожидаться завершение выполнения потока thr1 не более 100 секунд.

Так как метод join() всегда возвращает None, чтобы проверить, успел ли полностью выполниться поток за указанный timeout, нужно проверить, выполняется ли поток с помощью метода is_alive().

Здесь мы делаем поток демоническим, чтобы программа не дожидалась окончания выполнения функции. Подключаем модуль time, для того, чтобы сделать задержку в функции на 2.5 секунд. После старта потока, мы приостанавливаем основной поток на 0.125 секунд. Потом выполняем проверку is_alive(). Если выведет True, значит поток не закончил выполнение за 0.125 секунды.

В этом методе описываются операции, выполняемые потоком. Он используется, когда явно создается экземпляр класса. Пример:

Остановка потока

Бывают ситуации, когда требуется остановить поток, который работает в фоне. Допустим у нас поток у которого в функции run бесконечный цикл. В основной программе нам нужно его остановить. Тут самое простое — это создать некую переменную stop:

В бесконечном цикле делать постоянно её проверку и если она True, то завершать его.
Не использовать функции, которые могут блокировать выполнение на длительное время. Всегда использовать timeout.

Вот пример такой программы:

Здесь используем глобальную переменную stop. Когда нам нужно остановить поток, мы ей присваиваем значение True, а дальше просто ждём его завершения.

Состояние гонки

Состояние гонки или race condition – это ошибка, возникающая при неправильном проектировании многопоточной программы. Она возникает тогда, когда несколько потоков обращаются к одним и тем же данным. Например, переменная хранит число, которое пытаются одновременно изменить потоки thread1 и thread2, что приводит к непредсказуемым результатам или ошибке.

Распространена ситуация, когда один поток проверяет значение переменной на выполнение условия, чтобы совершить какое-то действие, но между проверкой условия и выполнением действия вмешивается второй поток, который изменяет значение переменной, что приводит к получению неправильных результатов, например:

deadlock

При использовании Lock возникает серьезная проблема, которая приводит к полной остановки работы программы. Если вызвать метод acquire(), а объект Lock уже заблокирован, то вызвавший acquire() поток будет ждать, пока заблокировавший объект поток не вызовет release().

Если один поток вызывает метод блокировки несколько раз подряд, то выполнение потока приостанавливается, пока он сам не вызовет release(). Однако он не может вызвать release, потому что его выполнение приостановлено, что означает бесконечную блокировку программы.

Самоблокировку можно предотвратить, если удалить лишний вызов acquire(), но это не всегда возможно. Самоблокировка может происходить из-за следующий вещей:

Возникновение ошибок, когда Lock остаётся заблокированным.
Неправильное проектирование программы, когда одна функция вызывается другой функцией, у которой отсутствует блокировка.

В случае возникновения ошибок достаточно воспользоваться конструкцией try-finally или оператором with.

Вот пример с with:

Конструкция try-finally позволяет удалять блокировку даже в случае возникновения ошибок, что позволяет избежать deadblock. Пример:

Конструкция try-finally гарантирует, что код в finally будет исполнен всегда, независимо от ошибок и результатов блока try.

Однако это не работает в случае самоблокировки из-за неправильного проектирования программы. Для этого был создан объект RLock.

RLock

Если Lock заблокирован, он блокирует любой поток, попытавшийся сделать то же самое, даже если этот поток и является владельцем блокировки в данный момент. Например, программист написал код:

Данный код будет работать, но его проблема заключается в том, что при вызове функции both_parts , в ней вызываются функции part1 и part2 . Между вызовами этих функций может получить доступ к данным какой-нибудь другой поток и их поменять. А что делать, если нужно избежать изменения другим потоком?

Чтобы решить проблему, нужно заблокировать lock1 и в both_parts , перепишем её:

Идея проста: внешняя both_parts блокирует поток на время выполнения функций part1 и part1 . Каждая из функций также блокирует поток для суммирования своей части объекта. Однако объект Lock не позволит этого сделать, этот код приведет к полному зависанию программы, потому что для Lock нет разницы, где в потоке был вызван acquire().

RLock блокирует поток только в том случае, если объект заблокирован другим потоком. Используя RLock, поток никогда не сможет заблокировать сам себя.

Также следует помнить, что, хотя и можно вызывать acquire() несколько раз, метод release() нужно вызвать столько же раз. При каждом вызове acquire() уровень рекурсии увеличивается на единицу, соответственно при каждом вызове release() он уменьшается на единицу.

Передача данных с помощью очередей (Queue)

Библиотеке queue содержит все необходимые инструменты для передачи данных между потоками и реализует нужные механизмы блокировки.

Класс Queue реализует очередь FIFO, который работает так: первый элемент, который пошел в очередь, первым и выйдет из неё. Эту очередь можно сравнить с вертикальной полой трубой, в которую сверху бросают элементы.

Queue имеет параметр maxsize, принимающий только целочисленные значения. Он указывает максимальное количество элементов, которое можно поместить в очередь. Когда максимум достигается, добавление в очередь элементов блокируется, пока в ней не освободится место. Если maxsize принимает значение myfunc выполнится через 4 секунды после вызова метода start().

Barrier

Этот класс позволяет реализовать простой механизм синхронизации потоков. Его можно использовать для фиксированного числа потоков, когда необходимо, чтобы каждый поток ждал выполнения какого-либо действия всеми.

Для того чтобы продолжить выполнения, все потоки должны вызвать метод wait(), если хоть один поток не сделал этого, остальные блокируются до тех пор, пока метод не будет вызван.

Так выглядят его аргументы:

Рассмотрим пример использования:

Здесь выставляю barrier на 2 вызова wait. То есть, для того, чтобы выполнился код после wait, wait должен быть вызван в 2 потоках. В данном случае функция myfunc сразу запускается в потоке, но она сразу не выведет 'отработал barrier' в консоль, а дождётся когда в основном потоке будет вызван wait тоже.

Event

Event представляет собой простой механизм реализации связи между потоками: один поток даёт сигнал о событии, другие ожидают этого сигнала.

Объект события управляет внутренним флагом, который может быть установлен в True или False с помощью методов set() и clear(). Также есть методы is_set(), которым можно проверить состояние внутреннего флага. С помощью метода wait(timeout=None) можно ждать пока не выставлен флаг в True. Так же при необходимости можно задать время ожидания.

Вот пример:

Возможность управления потоками в Python – это мощный инструмент в разработке больших программ. Для работы с ними используется модуль Threading и библиотека queue в связке с ним.

Каждый программист Python должен уметь работать с потоками, очередями и понимать, как устроена блокировка, доступ к данным и их передача между потоками.

Для реализации АТД очереди подходящим решением вновь станет создание нового класса. Как и раньше, для построения внутреннего представления очереди мы будем использовать мощь и простоту коллекции “список”.

Нам надо определиться, какой конец списках считать головой, а какой - хвостом. Реализация, показанная в листинге 1 предполагает, что последний элемент очереди находится на его нулевой позиции. Это позволяет использовать функцию `insert` для добавления новых элементов в конец очереди. Операция `pop` будет использоваться для удаления переднего элемента (последнего элемента в списке). Напомним, что также это означает постановку в очередь за O(n), а извлечение - за O(1) времени.

Листинг 1

CodeLens 1 демонстрирует класс Queue в действии для последовательности операций из таблицы 1

Пример операций очереди (ququeuetest)

Q-42: Предположим, что у вас есть следующая последовательность операций с кодом.

Вот реальная аналогия для очереди первого входа, первого выхода:

Еще один способ запомнить характеристики структуры данных очереди-это думать о ней как о канале:

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

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

С помощью очереди вы удаляете элемент, добавленный последним (первый вход, первый выход или FIFO ? ); а с помощью стека вы удаляете элемент, добавленный последним ( последний вход, первый выход или LIFO ? ).

С точки зрения производительности, правильная реализация очереди, как ожидается, займет O(1) времени для операций вставки и удаления. Это две основные операции, выполняемые в очереди, и они должны быть быстрыми в правильной реализации.

Очереди имеют широкий спектр применения в алгоритмах и для решения задач планирования, а также параллельного программирования. Короткий и красивый алгоритм, использующий очередь, — это широтно-первый поиск (BFS) в структуре данных дерева или графика.
Алгоритмы планирования часто используют внутренние очереди приоритетов. Это специализированные очереди: вместо получения следующего элемента по времени вставки приоритетная очередь получает элемент с наивысшим приоритетом. Приоритет отдельных элементов определяется очередью на основе порядка, применяемого к их ключам.

Обычная очередь, однако, не будет повторно заказывать элементы, которые она несет. Вы получаете то, что вы вкладываете, и именно в таком порядке (помните пример с трубой?)

Python поставляется с несколькими реализациями очереди, каждый из которых имеет немного разные характеристики. Давайте взглянем на них:

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

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

Поэтому я бы не рекомендовал вам использовать a listв качестве временной очереди в Python (если вы не имеете дело только с небольшим количеством элементов).

Класс collections.deque

Класс deque реализует двустороннюю очередь, которая поддерживает добавление и удаление элементов с любого конца за O (1) раз.

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

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

collections.deque это отличный выбор по умолчанию, если вы ищете структуру данных очереди в стандартной библиотеке Python.

Класс queue.Queue

Эта реализация очереди в стандартной библиотеке Python синхронизирована и предоставляет семантику блокировки для поддержки нескольких одновременных производителей и потребителей.

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

В зависимости от вашего варианта использования семантика блокировки может быть полезной или просто нести ненужные накладные расходы. В этом случае вам было бы лучше использовать collections.dequeв качестве очереди общего назначения.

Класс multiprocessing.Queue

Это реализация общей очереди заданий, которая позволяет помещенным в очередь элементам обрабатываться параллельно несколькими параллельными работниками. Распараллеливание на основе процессов популярно в Python из-за глобальной блокировки интерпретатора (GIL) .

multiprocessing.Queue предназначена для совместного использования данных между процессами и может хранить любой маринованный объект.

Хороший выбор по умолчанию: collections.deque
Если вы не ищете поддержку параллельной обработки, предложенная реализация collections.deque является отличным выбором по умолчанию для реализации структуры данных очереди FIFO в Python.

I’D предоставляет характеристики производительности, которые вы ожидаете от хорошей реализации очереди, а также может использоваться в качестве стека (очередь LIFO).

В этой статье чего-то не хватает или вы нашли ошибку? Помогите коллеге и оставьте комментарий ниже.

Читайте также: