Как реализовать Приоритетные очереди в Python? - PullRequest
Новая
       38

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

23 голосов
/ 02 апреля 2012

Извините за такой глупый вопрос, но документы по Python сбивают с толку ...

Ссылка 1: Реализация очереди http://docs.python.org/library/queue.html

Это говорит о том, что у очереди есть очередь для приоритетной очереди.Но я не смог найти, как это реализовать. 

class Queue.PriorityQueue(maxsize=0)

Ссылка 2: Реализация кучи http://docs.python.org/library/heapq.html

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

pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>'      # placeholder for a removed task
counter = itertools.count()     # unique sequence count

def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue'

Какая реализация очереди приоритетов наиболее эффективна в python?И как это реализовать?

Ответы [ 3 ]

29 голосов
/ 02 апреля 2012

В любом языке . 1003 *.

не существует такого понятия, как «наиболее эффективная реализация очереди с приоритетами». Очередь приоритетов - это все компромиссы.См. http://en.wikipedia.org/wiki/Priority_queue

Вы должны выбрать один из этих двух, в зависимости от того, как вы планируете его использовать:

  • O(log(N)) время вставки и O(1) время поиска мин + время удаления,или
  • O(1) время вставки и O(log(N)) findMin + время удаления delete

В последнем случае вы можете выбрать реализацию очереди приоритетов с кучей Фибоначчи: http://en.wikipedia.org/wiki/Heap_(data_structure)#Comparison_of_theoretic_bounds_for_variants (как вы можете видеть, heapq, который является в основном двоичным деревом, обязательно должен иметь O(log(N)) для вставки и findMin + deleteMin)

Если вы имеете дело с данными со специальными свойствами (такими каккак ограниченные данные), тогда вы можете достичь O(1) вставки и O(1) findMin + deleteMin времени.Вы можете делать это только с определенными типами данных, потому что в противном случае вы могли бы злоупотребить своей приоритетной очередью, чтобы нарушить ограничение O(N log(N)) для сортировки.

Чтобы реализовать любую очередь на любом языке, все, что вам нужно, это определить insert(value) и extractMin() -> value операций.Как правило, это просто включает в себя минимальное обертывание основной кучи;см. http://en.wikipedia.org/wiki/Fibonacci_heap, чтобы реализовать свою собственную, или использовать готовую библиотеку аналогичной кучи, например, «Куча сопряжения» (поиск Google показал http://svn.python.org/projects/sandbox/trunk/collections/pairing_heap.py)

Если вас волнует только то, какие из двух упомянутых вами ссылок более эффективны (код на основе heapq из http://docs.python.org/library/heapq.html#priority-queue-implementation-notes, который вы включили выше, по сравнению с Queue.PriorityQueue), то:

Кажется, что в интернете легко найти дискуссию о том, что на самом деле делает Queue.PriorityQueue;Вы должны были бы погрузиться в код, который связан с справочной документацией: http://hg.python.org/cpython/file/2.7/Lib/Queue.py

   224     def _put(self, item, heappush=heapq.heappush):
   225         heappush(self.queue, item)
   226 
   227     def _get(self, heappop=heapq.heappop):
   228         return heappop(self.queue)

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

(обратите внимание, что Queue.PriorityQueue, похоже, не имеетспособ удалить записи, в то время как heapq это делает. Однако это обоюдоострый меч: реализация очередей с хорошим приоритетом может позволить вам удалять элементы за O (1) или O (log (N)), но если выиспользуйте функцию remove_task, которую вы упомянули, и пусть эти задачи-зомби накапливаются в вашей очереди, потому что вы не извлекаете их из минимума, тогда вы увидите асимптотическое замедление, которое иначе вы бы не увидели. Конечно, вы не моглисделайте это с Queue.PriorityQueue во-первых, чтобы сравнение здесь не проводилось.)

28 голосов
/ 02 апреля 2012

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

Тем не менее, версия Queue медленнее, потому что она добавляет блокировки, инкапсуляцию и хороший объектно-ориентированный API.

Предложения очереди приоритетов , показанные вДокументы heapq предназначены для того, чтобы показать, как добавить дополнительные возможности в очередь с приоритетами (например, стабильность сортировки и возможность изменить приоритет ранее поставленной в очередь задачи).Если вам не нужны эти возможности, то основные функции heappush и heappop обеспечат вам максимальную производительность.

1 голос
/ 28 февраля 2018

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

# class for Node with data and priority
class Node:

  def __init__(self, info, priority):
    self.info = info
    self.priority = priority

# class for Priority queue 
class PriorityQueue:

  def __init__(self):
    self.queue = list()
    # if you want you can set a maximum size for the queue

  def insert(self, node):
    # if queue is empty
    if self.size() == 0:
      # add the new node
      self.queue.append(node)
    else:
      # traverse the queue to find the right place for new node
      for x in range(0, self.size()):
        # if the priority of new node is greater
        if node.priority >= self.queue[x].priority:
          # if we have traversed the complete queue
          if x == (self.size()-1):
            # add new node at the end
            self.queue.insert(x+1, node)
          else:
            continue
        else:
          self.queue.insert(x, node)
          return True

  def delete(self):
    # remove the first node from the queue
    return self.queue.pop(0)

  def show(self):
    for x in self.queue:
      print str(x.info)+" - "+str(x.priority)

  def size(self):
    return len(self.queue)

Найдите полный код и объяснение здесь: https://www.studytonight.com/code/python/ds/priority-queue-in-python.php

...