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

Question

Python有一个叫Queue.PriorityQueue的东西，但我找不到让里面的每个值都唯一的方法，因为它没有检查某个值是否已经存在的功能（比如找(name)之类的）。而且，PriorityQueue需要把优先级放在值里面，所以我连查找我的值都做不到，因为我还得知道优先级。你会用(0.5, myvalue)这样的格式放入PriorityQueue，然后它会根据元组的第一个元素进行排序。

另一方面，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（即使优先级不同，也不应该再次添加）

Answer 1

如果你想稍后优先处理某个任务。

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

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的完整接口。我留了一些打印语句没有注释掉，但把我在调试时加的那些注释掉了。；）

Answer 3

你可以把优先队列和集合结合起来：

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

这里使用了你在一个链接问题中提到的优先队列。我不确定这是否是你想要的，但这样把集合加到任何类型的队列中其实很简单。