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

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

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

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

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? И как его реализовать?

Ответы

Ответ 1

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

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

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

Ответ 2

В любом языке нет такой вещи, как "наиболее эффективная реализация очереди приоритетов".

Очередь приоритетов - это все о компромиссах. См. http://en.wikipedia.org/wiki/Priority_queue

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

  • O(log(N)) время вставки и O(1) findMin + deleteMin time, или
  • O(1) время вставки и O(log(N)) findMin + deleteMin time

В последнем случае вы можете выбрать очередь приоритетов с кучей Fibonacci: 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 time. Вы можете делать это только с определенными типами данных, потому что иначе вы могли бы злоупотреблять своей очередью приоритетов, чтобы нарушить привязку O(N log(N)) при сортировке.

Чтобы реализовать любую очередь на любом языке, вам нужно всего лишь определить операции insert(value) и extractMin() -> value. Обычно это связано с минимальной упаковкой основной кучи; см. http://en.wikipedia.org/wiki/Fibonacci_heap, чтобы реализовать свою собственную или использовать встроенную библиотеку подобной кучи, такой как Pairing 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 в первую очередь, поэтому здесь не может быть никакого сравнения.)