¿Cómo puedo hacer una cola de prioridad de valor única en Python?

Question

Python tiene Queue.PriorityQueue, pero no veo una manera de hacer que cada valor sea único ya que no hay un método para verificar si ya existe un valor (como find (name) o similar). Además, PriorityQueue necesita la prioridad para permanecer dentro del valor, por lo que ni siquiera podría buscar mi valor, ya que también tendría que conocer la prioridad. Utilizaría (0.5, myvalue) como valor en PriorityQueue y luego se ordenaría por el primer elemento de la tupla.

La clase collections.deque ofrece una función para comprobar si ya existe un valor y es aún más natural en el uso (sin bloqueo, pero aún atómico), pero no ofrece una forma de ordenar por prioridad.

Hay otras implementaciones en stackoverflow con heapq, pero heapq también usa prioridad dentro del valor (por ejemplo, en la primera posición de una tupla), por lo que parece no ser excelente para la comparación de valores existentes.

Creating a python priority Queue

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

Cuál es la mejor manera de crear una cola de prioridad atómica (= se puede utilizar a partir de múltiples hilos) con valores únicos?

Ejemplo lo que desea añadir:

• Prioridad: 0.2, Valor: valor1
• Prioridad: 0.3, Valor: valor2
• Prioridad: 0.1, Valor: value3 (deberá ser recuperada primero de forma automática)
• prioridad: 0.4, Valor: valor1 (no se añade de nuevo, a pesar de que tiene una prioridad diferente)

Answer 1

Usted podría com bine una cola de prioridad con un conjunto:

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 

Esto utiliza la cola de prioridad especificada en una de sus preguntas vinculadas. No sé si esto es lo que quieres, pero es bastante fácil agregar un conjunto a cualquier tipo de cola de esta manera.

Answer 2

Bueno, aquí hay una manera de hacerlo. Yo, básicamente, empecé a como lo definen PriorityQueue en Queue.py y añadió un conjunto en él para llevar un registro de claves únicas:

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 me ganó de mano por unos minutos, pero pensé que había publicar también porque es compatible con la interfaz completa de PriorityQueue. Dejé algunas declaraciones de impresión sin comentar, pero comenté las que puse mientras lo depuraba. ;)

Answer 3

En caso de que quiera priorizar una tarea más adelante.

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

Aquí es otra aplicación sigue la guía oficial:

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