Как я могу сделать уникальную очередь приоритетов значений в Python?

Question

В Python есть Queue.PriorityQueue, но я не вижу способа сделать каждое значение в нем уникальным, поскольку нет способа проверить, существует ли уже значение (например, find (name) или подобное). Более того, PriorityQueue нужно, чтобы приоритет оставался в пределах значения, поэтому я не мог даже искать свое значение, поскольку мне также нужно было бы знать приоритет. Вы должны использовать (0.5, myvalue) в качестве значения в PriorityQueue, а затем оно будет отсортировано по первому элементу кортежа.

С другой стороны, в коллекциях collection.deque есть функция для проверки, существует ли уже значение и является ли оно более естественным в использовании (без блокировки, но все еще атомарным), но он не предлагает способ сортировки по приоритету. .

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

Создание очереди с приоритетом Python

https://stackoverflow.com/questions/3306179/priority-queue-problem-in-python

Каков наилучший способ создания очереди с атомарным приоритетом (= может использоваться из нескольких потоков) с уникальными значениями?

Пример того, что я хотел бы добавить:

• Приоритет: 0,2, Значение: значение1
• Приоритет: 0,3, Значение: значение2
• Приоритет: 0,1, Значение: значение3 (извлекается первым автоматически)
• Приоритет: 0,4, Значение: значение1 (больше не добавляется, даже если у него другой приоритет)

Answer 1

Вы можете объединить приоритетную очередь с набором:

import heapq

class PrioritySet(object):
    def __init__(self):
        self.heap = []
        self.set = set()

    def add(self, d, pri):
        if not d in self.set:
            heapq.heappush(self.heap, (pri, d))
            self.set.add(d)

    def get(self):
        pri, d = heapq.heappop(self.heap)
        self.set.remove(d)
        return d

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

Answer 2

Ну, вот один из способов сделать это.Я в основном начал с того, как они определили PriorityQueue в Queue.py и добавил в него набор для отслеживания уникальных ключей:

from Queue import PriorityQueue
import heapq

class UniquePriorityQueue(PriorityQueue):
    def _init(self, maxsize):
#        print 'init'
        PriorityQueue._init(self, maxsize)
        self.values = set()

    def _put(self, item, heappush=heapq.heappush):
#        print 'put',item
        if item[1] not in self.values:
            print 'uniq',item[1]
            self.values.add(item[1])
            PriorityQueue._put(self, item, heappush)
        else:
            print 'dupe',item[1]

    def _get(self, heappop=heapq.heappop):
#        print 'get'
        item = PriorityQueue._get(self, heappop)
#        print 'got',item
        self.values.remove(item[1])
        return item

if __name__=='__main__':
    u = UniquePriorityQueue()

    u.put((0.2, 'foo'))
    u.put((0.3, 'bar'))
    u.put((0.1, 'baz'))
    u.put((0.4, 'foo'))

    while not u.empty():
        item = u.get_nowait()
        print item

Боаз Янив избил меня до удара через несколько минут, но я решил, что яЯ также оставлю сообщение, поскольку он поддерживает полный интерфейс PriorityQueue.Я оставил некоторые операторы печати без комментариев, но закомментировал те, которые я вставил во время отладки.;)

Answer 3

В случае, если вы хотите определить приоритет задачи позже.

u = UniquePriorityQueue()

u.put((0.2, 'foo'))
u.put((0.3, 'bar'))
u.put((0.1, 'baz'))
u.put((0.4, 'foo'))
# Now `foo`'s priority is increased.
u.put((0.05, 'foo'))

Вот еще одна реализация, следующая официальному руководству:

import heapq
import Queue

class UniquePriorityQueue(Queue.Queue):
    """
    - https://github.com/python/cpython/blob/2.7/Lib/Queue.py
    - https://docs.python.org/3/library/heapq.html
    """

    def _init(self, maxsize):
        self.queue = []
        self.REMOVED = object()
        self.entry_finder = {}

    def _put(self, item, heappush=heapq.heappush):
        item = list(item)
        priority, task = item
        if task in self.entry_finder:
            previous_item = self.entry_finder[task]
            previous_priority, _ = previous_item
            if priority < previous_priority:
                # Remove previous item.
                previous_item[-1] = self.REMOVED
                self.entry_finder[task] = item
                heappush(self.queue, item)
            else:
                # Do not add new item.
                pass
        else:
            self.entry_finder[task] = item
            heappush(self.queue, item)

    def _qsize(self, len=len):
        return len(self.entry_finder)

    def _get(self, heappop=heapq.heappop):
        """
        The base makes sure this shouldn't be called if `_qsize` is 0.
        """
        while self.queue:
            item = heappop(self.queue)
            _, task = item
            if task is not self.REMOVED:
                del self.entry_finder[task]
                return item
        raise KeyError('It should never happen: pop from an empty priority queue')