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

Question

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

另一方面,collections.deque类提供了一个函数,用于检查值是否已经存在并且在使用中更自然(没有锁定,但仍然是原子的),但它没有提供按优先级排序的方法.

stackq上有一些其他实现与heapq,但heapq也使用值内的优先级(例如在元组的第一个位置),所以它似乎不是很好的比较已有的值.

创建python优先级队列

/sf/ask/231432561/

使用唯一值创建原子优先级队列(=可以从多个线程使用)的最佳方法是什么？

我要添加的示例:

• 优先级:0.2,值:value1
• 优先级:0.3,价值:价值2
• 优先级:0.1,值:value3(应首先自动检索)
• 优先级:0.4,值:value1(即使优先级不同,也不得再次添加)

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

好吧，这是一种方法。我基本上从他们如何在 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 的完整界面。我留下了一些未注释的打印语句，但注释掉了我在调试时放入的语句。;)