На этом шаге мы рассмотрим особенности реализации такой очереди.

Задача

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

Решение

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

>>> import heapq
>>> class PriorityQueue:
	def __init__(self):
		self._queue = []
		self._index = 0
	def push(self, item, priority):
		heapq.heappush(self._queue, (-priority, self._index, item))
		self._index += 1
	def pop(self):
		return heapq.heappop(self._queue)[-1]

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

>>> class Item:
	def __init__(self, name):
		self.name = name
	def __repr__(self):
		return 'Item({!r})'.format(self.name)

>>> q = PriorityQueue()
>>> q.push(Item('foo'), 1)
>>> q.push(Item('bar'), 5)
>>> q.push(Item('spam'), 4)
>>> q.push(Item('grok'), 1)
>>> q.pop()
Item('bar')
>>> q.pop()
Item('spam')
>>> q.pop()
Item('foo')
>>> q.pop()
Item('grok')
>>>

    Первая операция pop() возвращает элемент с наивысшим приоритетом. Также заметьте, что два элемента с одинаковым приоритетом (foo и grok) были возвращены в том же порядке, в каком они были помещены в очередь.

Обсуждение

    Суть этого рецепта - использование модуля heapq. Функции heapq.heappush() и heapq.heappop() вставляют и удаляют элементы из list_queue таким образом, что первый элемент в списке имеет наименьший приоритет. Метод heappop() всегда возвращает "наименьший" элемент, что является ключом к тому, чтобы заставить очередь удалять правильные элементы. Кроме того, так как операции вставки и удаления имеют сложность O(log N), где N - число элементов в куче, то они вполне эффективны даже для весьма больших значений N.

    В этом рецепте очередь состоит из кортежей формата (-priority, index, item). Значение priority сделано отрицательным, чтобы заставить очередь сортировать элементы от наибольшего к наименьшему приоритету. Это противоположно обычному порядку сортировки кучи (от наименьшего к наибольшему значению).

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

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

>>> a = Item('foo')
>>> b = Item('bar')
>>> a < b
Traceback (most recent call last):
  File "<pyshell#30>", line 1, in <module>
    a < b
TypeError: '<' not supported between instances of 'Item' and 'Item'
>>> 

    Если вы создаете кортежи (priority, item), то их можно сравнивать до тех пор, пока приоритеты различны. Однако же если сравниваются два кортежа с равными приоритетами, то сравнение не может быть проведено (как и ранее). Например:

>>> a = (1, Item('foo'))
>>> b = (5, Item('bar'))
>>> a < b
True
>>> c = (1, Item('grok'))
>>> a < c
Traceback (most recent call last):
  File "<pyshell#35>", line 1, in <module>
    a < c
TypeError: '<' not supported between instances of 'Item' and 'Item'
>>> 

    Вводя дополнительный индекс и создавая кортежи (priority, index, item), вы полностью обходите эту проблему, поскольку два кортежа никогда не будут иметь одинаковые значения переменной index (и Python никогда не будет сравнивать остальные значения в кортежах, если результат сравнения уже определен):

>>> a = (1, 0, Item('foo'))
>>> b = (5, 1, Item('bar'))
>>> c = (1, 2, Item('grok'))
>>> a < b 
True
>>> a < c 
True 
>>>

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

    Документация модуля heapq содержит дополнительные примеры и обсуждения теории и реализации куч (https://docs.python.org/3.4/library/heapq.html).

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

Предыдущий шаг Содержание Следующий шаг