如何在Python中創建唯一的值優先級隊列？

Question

Python有Queue.PriorityQueue，但我看不到一種方法讓它中的每個值都是唯一的，因爲沒有檢查值是否已經存在的方法（如find（name）或類似方法）。此外，PriorityQueue需要優先保持在價值範圍內，所以我甚至無法搜索我的價值，因爲我也必須知道優先級。您將使用（0.5，myvalue）作爲PriorityQueue中的值，然後它將按元組的第一個元素排序。

另一方面，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，值：數值（不得再次添加，即使它有不同的優先級）

Answer 1

你可以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 

這使用您的鏈接問題之一中指定的優先級隊列。我不知道這是否是你想要的，但是用這種方式將一組設置添加到任何類型的隊列中是相當容易的。

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 

波阿斯的Yaniv通過幾分鐘打我一記重拳，但我想我會因爲它支持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')