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

Реализация очереди на Python¶

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

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

Листинг 1

class Queue: def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def enqueue(self, item): self.items.insert(0,item) def dequeue(self): return self.items.pop() def size(self): return len(self.items) 

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

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

>>> q.size() 3 >>> q.isEmpty() False >>> q.enqueue(8.4) >>> q.dequeue() 4 >>> q.dequeue() 'dog' >>> q.size() 2 

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

q = Queue() q.enqueue('hello') q.enqueue('dog') q.enqueue(3) q.dequeue() 

Какие элементы находятся в очереди слева?

readers online now | | Back to top

© Copyright 2014 Brad Miller, David Ranum. Created using Sphinx 1.2.3.

Как организовать очередь на Python?

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

Наверняка уже есть что-то готовое. Или как минимум какие-то рекомендации как организуется очередь.

• Вопрос задан более трёх лет назад
• 8377 просмотров

Модуль queue, очереди в Python

Потоко-безопасные очереди FIFO, LIFO и очереди с приотитетом

Модуль queue реализует очереди с несколькими производителями и несколькими потребителями. Это особенно полезно в потоковом программировании, когда информация должна безопасно обмениваться между несколькими потоками. Класс queue.Queue() в этом модуле реализует всю необходимую семантику блокировки.

Модуль реализует три типа очереди, которые отличаются только порядком, в котором извлекаются записи:

• В очереди FIFO первые добавленные задачи являются первыми извлеченными.
• В очереди LIFO самая последняя добавленная запись является первой извлеченной (работающей как стек).
• В очереди с приоритетами записи сохраняются отсортированными с использованием модуля heapq и сначала извлекается запись с наименьшим значением.

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

Кроме того, модуль реализует простой тип очереди FIFO — queue.SimpleQueue() , специфическая реализация которого обеспечивает дополнительные гарантии в обмен на меньшую функциональность.

Примеры использования модуля queue .

Очередь FIFO:

Класс queue.Queue() реализует базовый контейнер типа FIFO — «первым пришел — первым вышел». Элементы добавляются к одному концу очереди с помощью метода put() , а удаляются с другого конца с помощью метода get() .

import queue q = queue.Queue() for i in range(5): q.put(i) while not q.empty(): print(q.get(), end=' ') # 0 1 2 3 4 

Очередь LIFO:

В отличие от стандартной реализации очереди FIFO, в queue.LifoQueue() используется порядок «последним пришел — первым вышел», который обычно связан со структурой данных стека.

import queue q = queue.LifoQueue() for i in range(5): q.put(i) while not q.empty(): print(q.get(), end=' ') # 4 3 2 1 0 

Очередь с приоритетом:

Иногда порядок обработки элементов в очереди должен основываться на характеристиках этих элементов, а не только на порядке их создания или добавления в очередь. Например, задания на печать из финансового отдела могут иметь приоритет над списком заданий из отдела технической поддержки. Класс модуля queue.PriorityQueue() использует порядок сортировки содержимого очереди, чтобы решить, какой элемент получить.

import functools import queue import threading @functools.total_ordering class Job: def __init__(self, priority, description): self.priority = priority self.description = description return def __eq__(self, other): try: return self.priority == other.priority except AttributeError: return NotImplemented def __lt__(self, other): try: return self.priority  other.priority except AttributeError: return NotImplemented def process_job(q): while True: next_job = q.get() print('Processing job:', next_job.description) q.task_done() q = queue.PriorityQueue() q.put(Job(3, 'Mid-level')) q.put(Job(10, 'Low-level')) q.put(Job(1, 'Important')) workers = [ threading.Thread(target=process_job, args=(q,)), threading.Thread(target=process_job, args=(q,)), ] for w in workers: w.setDaemon(True) w.start() q.join() 

Этот пример имеет несколько потоков, потребляющих задания, которые обрабатываются на основе приоритета элементов в очереди на момент вызова get() . Порядок обработки элементов, добавляемых в очередь во время работы потоков-потребителей, зависит от переключения контекста потока.

Processing job: Important job Processing job: Mid-level job Processing job: Low-level job

• КРАТКИЙ ОБЗОР МАТЕРИАЛА.
• Класс Queue() модуля queue
• Класс LifoQueue() модуля queue
• Класс PriorityQueue() модуля queue
• Объект очереди модуля queue
• Пример обработки очереди в несколько потоков
• Класс SimpleQueue() модуля queue
• Исключения модуля queue

18. Очереди¶

Эта глава рассказывает о двух абстрактных типах данных: очередь и очередь с приоритетом. Все мы видели очередь клиентов, ожидающих обслуживания. Чаще всего, первый клиент в очереди будет обслужен следующим. Хотя бывают и исключения. В аэропортах, пассажиры рейсов, которые вскоре отправляются, иногда обслуживаются вне очереди. В супермаркете вежливый покупатель может пропустить другого, с одной-двумя покупками, перед собой.

Правило, определяющее, кто будет обслужен следующим, называется политикой очереди. Простейшая политика очереди называется FIFO, от английского first in — first out, что означает: первым пришел — первым вышел. А наиболее обобщенной политикой является приоритетное обслуживание, при которой каждому клиенту назначается приоритет, и клиент с наивысшим приоритетом обслуживается первым, независимо от времени его прихода. Мы назвали такую политику обобщенной потому, что приоритет может назначаться, исходя из чего угодно: времени отправления рейсов, количества покупок у покупателя, важности конкретного клиента.

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

18.2. Абстрактная очередь¶

Абстрактный тип данных очередь имеет следующие операции:

__init__ Создать новую пустую очередь. insert Добавить в очередь новый элемент. remove Удалить и вернуть элемент из очереди. Возвращаемый элемент — тот, который был добавлен первым. is_empty Проверить, пуста ли очередь.

18.3. Связная очередь¶

Первая из реализаций очереди, которую мы рассмотрим, будет связная очередь, построенная из связанных объектов Node . Вот определение класса Queue (англ.: очередь):

class Queue: def __init__(self): self.length = 0 self.head = None def is_empty(self): return (self.length == 0) def insert(self, cargo): node = Node(cargo) node.next = None if self.head == None: # if list is empty the new node goes first self.head = node else: # find the last node in the list last = self.head while last.next: last = last.next # append the new node last.next = node self.length += 1 def remove(self): if self.length == 0: return cargo = self.head.cargo self.head = self.head.next self.length -= 1 return cargo 

Методы is_empty и remove достаточно просты и похожи на подобные методы класса LinkedList . Метод insert существенно новый и чуть более сложный.

Нам нужно добавить новый элемент в конец списка. Если очередь пуста, мы просто присваиваем атрибуту head ссылку на новый узел.

В противном случае, мы проходим по всему списку до последнего узла, и присоединяем новый узел в конец списка. Мы определяем, что достигли последнего узла, когда значением атрибута next является None .

Для правильно построенного объекта Queue существуют два инварианта. Переменная length должна содержать количество узлов в очереди, и последний узел должен иметь атрибут next со значением None . Убедитесь, что метод insert сохраняет оба инварианта.

18.4. Показатели производительности¶

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

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

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

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

18.5. Улучшенная связная очередь¶

Хочется иметь реализацию очереди, которая выполняла бы все операции за постоянное время. Один из способов добиться этого — изменить класс Queue так, чтобы он поддерживал ссылку как на первый, так и на последний узел в списке!

Класс ImprovedQueue выглядит так:

class ImprovedQueue: def __init__(self): self.length = 0 self.head = None self.last = None def is_empty(self): return (self.length == 0) 

Все, что мы пока изменили в коде, — добавили атрибут last . Он используется в методах insert и remove :

class ImprovedQueue: . def insert(self, cargo): node = Node(cargo) node.next = None if self.length == 0: # if list is empty, the new node is head and last self.head = self.last = node else: # find the last node last = self.last # append the new node last.next = node self.last = node self.length += 1 

Поскольку атрибут last указывает на последний узел, нам не нужно искать его. В результате, данный метод является методом с постоянным временем выполнения.

За скорость, однако, нужно платить. Придется добавить условное предложение в remove для того, чтобы присваивать last значение None в случае, когда удален последний узел:

class ImprovedQueue: . def remove(self): if self.length == 0: return cargo = self.head.cargo self.head = self.head.next self.length -= 1 if self.length == 0: self.last = None return cargo 

Эта реализация очереди несколько сложнее, чем реализация Queue . Также стало сложнее убедиться в ее корректности. Но преимущество состоит в том, что теперь и insert и remove являются операциями с постоянным временем выполнения.

18.6. Очередь с приоритетом¶

Абстрактный тип данных очередь с приоритетом имеет тот же интерфейс, что и очередь, но семантика отличается. Приведем интерфейс:

__init__ Создать новую пустую очередь. insert Добавить в очередь новый элемент. remove Удалить и вернуть элемент из очереди. Возвращаемый элемент — тот, у которого наивысший приоритет. is_empty Проверить, пуста ли очередь.

Семантическое отличие состоит в том, что извлекаемый из очереди элемент не обязательно тот, который был добавлен в очередь первым. Это элемент, имеющий наивысший приоритет. Что такое приоритет, и как выполняется сравнение приоритетов, не определяется в интерфейсе. Мы также не станем определять этого в нашей реализации очереди с приоритетом! О приоритете будут “знать” только сами элементы, помещаемые в очередь.

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

Следующая реализация очереди с приоритетом хранит элементы очереди в списке Python.

class PriorityQueue: def __init__(self): self.items = [] def is_empty(self): return self.items == [] def insert(self, item): self.items.append(item) 

Методы __init__ , is_empty и insert используют операции над списком. Единственный интересный метод remove :

class PriorityQueue: . def remove(self): maxi = 0 for i in range(1, len(self.items)): if self.items[i] > self.items[maxi]: maxi = i item = self.items[maxi] self.items[maxi:maxi+1] = [] return item 

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

Когда цикл for завершается, maxi содержит индекс элемента с наивысшим приоритетом. Этот элемент удаляется из списка и возвращается.

Протестируем нашу реализацию очереди с приоритетом:

>>> q = PriorityQueue() >>> q.insert(11) >>> q.insert(12) >>> q.insert(14) >>> q.insert(13) >>> while not q.is_empty(): print q.remove() 14 13 12 11 

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

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

18.7. Класс Golfer ¶

В качестве примера объекта с необычным приоритетом, реализуем класс Golfer (англ.: игрок в гольф), который хранит имя игрока и набранные им очки. Как всегда, начнем с определения методов __init__ и __str__ :

class Golfer: def __init__(self, name, score): self.name = name self.score= score def __str__(self): return "%-16s: %d" % (self.name, self.score) 

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

Далее, определим метод __cmp__ , в котором наименьшее число очков означает наивысший приоритет. Как всегда, __cmp__ возвращает 1, если self больше other , -1, если self меньше other , и 0 в случае их равенства.

class Golfer: . def __cmp__(self, other): if self.score  other.score: return 1 # less is more if self.score > other.score: return -1 return 0 

Теперь мы готовы протестировать работу очереди с приоритетом с классом Golfer :

>>> tiger = Golfer("Tiger Woods", 61) >>> phil = Golfer("Phil Mickelson", 72) >>> hal = Golfer("Hal Sutton", 69) >>> >>> pq = PriorityQueue() >>> pq.insert(tiger) >>> pq.insert(phil) >>> pq.insert(hal) >>> while not pq.is_empty(): print pq.remove() Tiger Woods : 61 Hal Sutton : 69 Phil Mickelson : 72 

18.8. Глоссарий¶

FIFO First In, First Out, или первым вошел — первым вышел, политика очереди, при которой элемент, первым добавленный в очередь, будет излечен первым. очередь Упорядоченный набор объектов, ожидающих обслуживания. очередь с приоритетом Очередь, в которой которой каждый элемент имеет приоритет, зависящий от внешних факторов (то есть, независимый от самой очереди). Первым извлекается из очереди элемент с наивысшим приоритетом. политика очереди Правило, определяющее, какой элемент очереди будет извлечен (обслужен) следующим. программа с линейным временем выполнения Программа, время выполнения которой есть линейная функция от размера структуры данных. программа с постоянным временем выполнения Программа, время выполнения которой не зависит от размера структуры данных. связная очередь Реализация очереди с использованием связного списка.

18.9. Упражнения¶

1. Напишите реализацию очереди, используя список Python. Сравните производительность вашей реализации с реализацией ImprovedQueue для очередей различной длины.
2. Напишите реализацию очереди с приоритетом, используя связный список. Поддерживайте список отсортированным, так, чтобы извлечение из списка было операцией с постоянным временем выполнения. Сравните производительность этой реализации с реализацией при помощи списка Python.

Просмотр

© Copyright 2009, 2012, Джеффри Элкнер, Аллен Б. Дауни, Крис Мейерс, Андрей Трофимов. При создании использован Sphinx 1.1.3.