Python'da nasıl benzersiz bir değer önceliği kuyruğu yapabilirim?

Question

Python, Queue.PriorityQueue uygulamasına sahiptir, ancak bir değerin var olup olmadığını (bulma (isim) veya benzerleri gibi) kontrol etmek için bir yöntem olmadığından, her değeri benzersiz bir şekilde yapmanın bir yolunu göremiyorum. Dahası, PriorityQueue'un, değer içinde kalması için önceliğe ihtiyacı vardır, bu yüzden de önceliğimi bilmek zorunda olduğum için değerinizi bile aramadım. PriorityQueue'da (0,5, myvalue) değerini değer olarak kullanırsınız ve daha sonra, tuple'ın ilk öğesiyle sıralanır.

Diğer taraftan collections.deque sınıfı, bir değerin var olup olmadığını kontrol etmek için bir işlev sunar ve kullanımda daha doğaldır (kilitleme olmadan, ancak atomiktir), ancak sıralaması için bir yol sunmaz. önceliği.

Heapq ile stackoverflow üzerinde başka uygulamalar da vardır, ancak heapq da değer içinde öncelik kullanır (örneğin, bir tuple'ın ilk konumunda), bu yüzden zaten var olan değerlerin karşılaştırılması için harika görünmez.

bir atom öncelik sırası yaratmanın en iyi yolu, benzersiz değerlerle (= birden çok iş parçacığı kullanılabilir) nedir

Creating a python priority Queue

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

? deger2

Öncelik: deger1

Öncelik: 0.3, Değer

• Öncelik: 0.2, Değer İsterdim Ne

  Örnek eklemek için 0.1, Değer: değer3 (Alýnacak) otomatik olarak ilk

• Öncelik: 0.4, Değer: deger1 (farklı önceliğini) olsa bile, yine ilave edilmemelidir

Answer 1

Yapabilirsin com kümesiyle bir öncelik sırası bine:

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 

Bu Bağlantılı sorulardan birinde belirtilen öncelik sırası kullanır. İstediğiniz şey bu mu, bilmiyorum, ancak bu şekilde herhangi bir sıraya bir küme eklemek oldukça kolay.

Answer 2

İşte bunu yapmanın bir yolu. Ben temelde onlar Queue.py içinde PriorityQueue tanımlanan nasıl başladı ve benzersiz anahtarların takip etmek için içine bir takım ekledi:

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 birkaç dakika ile beni dövdükleri, ama ben düşündüm PriorityQueue'nin tam arayüzünü desteklediği için benim de gönderiyorum. Bazı yazılı ifadeleri rahatsız edilmedim, ancak hata ayıklama sırasında koyduğumları açıkladım. ;)

Answer 3

Daha sonra bir göreve öncelik vermek istiyorsanız. İşte

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

başka uygulama resmi rehber izler geçerli:

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

ben `self.set`