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

问题描述：

Python有Queue.PriorityQueue，但我看不到一种方法让它中的每个值都是唯一的，因为没有检查值是否已经存在的方法（如find（name）或类似方法）。此外，PriorityQueue需要优先保持在价值范围内，所以我甚至无法搜索我的价值，因为我也必须知道优先级。您将使用（0.5，myvalue）作为PriorityQueue中的值，然后它将按元组的第一个元素排序。如何在Python中创建唯一的值优先级队列？

另一方面，collections.deque类提供了一个函数来检查一个值是否已经存在，并且在使用中更加自然（没有锁定，但仍然是原子的），但是它没有提供排序的方法优先。

在stackoverflow上有一些heapq的实现，但heapq也在值中使用了优先级（例如在一个元组的第一个位置），所以它对于已经存在的值的比较似乎不是很好。

Creating a python priority Queue

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

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

例想什么我补充：

优先级：0.2，值：VALUE1
优先级：0.3，值：VALUE2
优先级：0.1，值：值3（应检索首先自动）
优先级：0.4，值：数值（不得再次添加，即使它有不同的优先级）

答

你可以COM为一组优先队列进行优化：

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

这使用您的链接问题之一中指定的优先级队列。我不知道这是否是你想要的，但是用这种方式将一组设置添加到任何类型的队列中是相当容易的。

我会建议不要使用内置函数的名字，比如'self.set' – sleepsort 2013-11-28 07:21:25

也许流行是获得更好的名字：） – DikobrAz 2014-08-20 10:10:55

答

那么这里有一个方法来做到这一点。我基本上是从他们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

波阿斯的Yaniv通过几分钟打我一记重拳，但我想我会因为它支持PriorityQueue的完整接口，所以也要发布我的帖子。我留下了一些打印语句的注释，但是在调试时放置了一些打印语句。 ;）

感谢您的回答。还不知道_init，_put和_get方法，但在扩展队列时它们非常实用。而且，既然你们都使用了套牌，我现在确信这些是正确的选择;） – Aufziehvogel 2011-05-14 15:31:36

答

如果您想稍后优先考虑任务。

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

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

相关推荐