如何在Python中创建一个唯一值优先队列？

Question

Python有Queue.PriorityQueue类，但我无法找到一种方法使其中的每个值都是唯一的，因为它没有检查值是否已存在的方法（例如find(name)或类似方法）。此外，PriorityQueue需要优先级保留在值内，所以我甚至无法搜索我的值，因为我还必须知道优先级。在PriorityQueue中，您将使用(0.5, myvalue)作为值，然后它将按元组的第一个元素进行排序。

另一方面，collections.deque类确实提供了一个用于检查值是否已存在的函数，而且使用起来更加自然（没有锁定，但仍然是原子的），但它不提供按优先级排序的方式。

stackoverflow上有一些使用heapq的其他实现，但heapq也在值内使用优先级（例如在元组的第一个位置），因此似乎不适合比较已经存在的值。

创建python优先队列

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

创建一个原子优先队列（=可以从多个线程使用）并具有唯一值的最佳方法是什么？

以下是我想要添加的示例：

• 优先级: 0.2，值：value1
• 优先级: 0.3，值：value2
• 优先级: 0.1，值：value3（应该自动首先检索）
• 优先级: 0.4，值：value1（不应再次添加，即使具有不同的优先级）

- aufziehvogel

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 pop(self):
        pri, d = heapq.heappop(self.heap)
        self.set.remove(d)
        return d

这个代码使用了你在一个链接问题中指定的优先队列。我不知道这是否是你想要的，但是通过这种方式将集合添加到任何类型的队列中相当容易。

- Boaz Yaniv

---

建议避免使用内置函数名称，如self.set。 - sleepsort

Answer 2

这里有一种方法可以实现它。我基本上从他们在Queue.py中定义PriorityQueue的方式开始，并添加了一个集合来跟踪唯一键：

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

Boaz Yaniv比我早了几分钟发表了他的意见，但我想我也会发表我的意见，因为它支持PriorityQueue的完整接口。 我留下了一些未注释的打印语句，但注释掉了我在调试时添加的语句。 ;)

- John Gaines Jr.

---

谢谢你的回答。我之前不知道_init、_put和_get这些方法，但是它们在扩展队列时非常实用。而且你们两个都使用了集合，现在我确信那是正确的做法 ;) - aufziehvogel

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')

- colinfang

Answer 4

我喜欢@Jonny Gaines Jr.的答案，但我认为它可以简化。PriorityQueue在底层使用列表，因此您只需定义：

class PrioritySetQueue(PriorityQueue):
    def _put(self, item):
        if item not in self.queue:
            super(PrioritySetQueue, self)._put(item)

- Peter w

---

我认为if条件语句应该更改为： if item not in map(lambda x:x[1], self.queue): - Evann Courdier