prioridad - implementacion cola en python

¿Cómo implementar colas de prioridad en Python?

Question

Lo siento por una pregunta tan tonta, pero los documentos de Python son confusos ...

Enlace 1: Implementación de la cola http://docs.python.org/library/queue.html

Dice que la cola tiene un diseño para la cola de prioridad. Pero no pude encontrar la forma de implementarlo.

class Queue.PriorityQueue(maxsize=0)

Enlace 2: Implementación de Heap http://docs.python.org/library/heapq.html

Aquí dicen que podemos implementar colas de prioridad indirectamente usando heapq

pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = ''<removed-task>''      # placeholder for a removed task
counter = itertools.count()     # unique sequence count

def add_task(task, priority=0):
    ''Add a new task or update the priority of an existing task''
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def remove_task(task):
    ''Mark an existing task as REMOVED.  Raise KeyError if not found.''
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    ''Remove and return the lowest priority task. Raise KeyError if empty.''
    while pq:
        priority, count, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError(''pop from an empty priority queue''

¿Cuál es la implementación de cola de prioridad más eficiente en python? ¿Y cómo implementarlo?

Answer 1

Aunque esta pregunta ha sido respondida y marcada como aceptada, aún aquí hay una implementación personalizada simple de Priority Queue sin usar ningún módulo para comprender cómo funciona.

# class for Node with data and priority
class Node:

  def __init__(self, info, priority):
    self.info = info
    self.priority = priority

# class for Priority queue 
class PriorityQueue:

  def __init__(self):
    self.queue = list()
    # if you want you can set a maximum size for the queue

  def insert(self, node):
    # if queue is empty
    if self.size() == 0:
      # add the new node
      self.queue.append(node)
    else:
      # traverse the queue to find the right place for new node
      for x in range(0, self.size()):
        # if the priority of new node is greater
        if node.priority >= self.queue[x].priority:
          # if we have traversed the complete queue
          if x == (self.size()-1):
            # add new node at the end
            self.queue.insert(x+1, node)
          else:
            continue
        else:
          self.queue.insert(x, node)
          return True

  def delete(self):
    # remove the first node from the queue
    return self.queue.pop(0)

  def show(self):
    for x in self.queue:
      print str(x.info)+" - "+str(x.priority)

  def size(self):
    return len(self.queue)

Encuentre el código completo y la explicación aquí: https://www.studytonight.com/code/python/ds/priority-queue-in-python.php

Answer 2

La versión en el módulo de Cola se implemented usando el módulo heapq , de modo que tengan la misma eficiencia para las operaciones de montón subyacentes.

Dicho esto, la versión de la cola es más lenta porque agrega bloqueos, encapsulación y una API orientada a objetos agradable.

Las sugerencias de la cola de prioridad que se muestran en los documentos heapq pretenden mostrar cómo agregar capacidades adicionales a una cola de prioridad (como la estabilidad de clasificación y la capacidad de cambiar la prioridad de una tarea en cola previamente). Si no necesita esas capacidades, entonces las funciones básicas de heappush y heappop le darán el rendimiento más rápido.

Answer 3

No existe una "implementación de cola de prioridad más eficiente" en ningún idioma .

Una cola de prioridad tiene que ver con las compensaciones. Ver http://en.wikipedia.org/wiki/Priority_queue

Debería elegir uno de estos dos, según cómo planee usarlo:

• O(log(N)) tiempo de inserción y O(1) tiempo de encontrarMin + borrarMin, o
• O(1) tiempo de inserción y O(log(N)) encontrarMin + eliminarMin tiempo

En el último caso, puede elegir implementar una cola de prioridad con un montón Fibonacci: http://en.wikipedia.org/wiki/Heap_(data_structure)#Comparison_of_theoretic_bounds_for_variants heapq (como puede ver, heapq que es básicamente un árbol binario, debe tener necesariamente O(log(N)) tanto para la inserción como para findMin + deleteMin)

Si está tratando con datos con propiedades especiales (como los datos acotados), puede lograr la inserción O(1) y el tiempo FindMin + deleteMin O(1) . Solo puede hacer esto con ciertos tipos de datos porque de lo contrario podría abusar de su cola de prioridad para violar el límite O(N log(N)) en la clasificación.

Para implementar cualquier cola en cualquier idioma, todo lo que necesita es definir las operaciones insert(value) y extractMin() -> value . En general, esto solo implica un ajuste mínimo del montón subyacente; vea http://en.wikipedia.org/wiki/Fibonacci_heap para implementar la suya propia, o use una biblioteca disponible de un montón similar como un Pairing Heap (una búsqueda de Google reveló http://svn.python.org/projects/sandbox/trunk/collections/pairing_heap.py )

Si solo se preocupa por cuál de los dos a los que hizo referencia es más eficiente (el código basado en heapq de http://docs.python.org/library/heapq.html#priority-queue-implementation-notes que incluyó anteriormente, en comparación con Queue.PriorityQueue ), entonces:

No parece que haya una discusión fácil de encontrar en la web en cuanto a lo que Queue.PriorityQueue está haciendo Queue.PriorityQueue ; tendría que sumergirse en el código, que está vinculado a la documentación de ayuda: http://hg.python.org/cpython/file/2.7/Lib/Queue.py

   224     def _put(self, item, heappush=heapq.heappush):
   225         heappush(self.queue, item)
   226 
   227     def _get(self, heappop=heapq.heappop):
   228         return heappop(self.queue)

Como podemos ver, Queue.PriorityQueue también está usando heapq como un mecanismo subyacente. Por lo tanto son igualmente malos (asintóticamente hablando). Queue.PriorityQueue puede permitir consultas paralelas, por lo que apostaría a que podría tener un factor ligeramente más constante de sobrecarga. Pero como sabe que la implementación subyacente (y el comportamiento asintótico) debe ser la misma, la forma más sencilla sería simplemente ejecutarlos en el mismo conjunto de datos de gran tamaño.

(Tenga en cuenta que Queue.PriorityQueue no parece tener una forma de eliminar entradas, mientras que heapq sí heapq hace. Sin embargo, esto es un arma de doble filo: las implementaciones de colas de buena prioridad posiblemente le permitirán eliminar elementos en O (1) u O ( log (N)) tiempo, pero si usa la función remove_task que menciona, y deja que esas tareas zombie se acumulen en su cola porque no las está extrayendo del mínimo, entonces verá una desaceleración asintótica que de otra manera no vería Por supuesto, no se puede hacer esto con Queue.PriorityQueue en primer lugar, por lo que no se puede hacer ninguna comparación aquí.)