Come implementare le code di priorità in Python?

Question

Ci scusiamo per una domanda così sciocca ma i documenti Python sono confusi ....

Link 1: Attuazione della coda http://docs.python.org/library/queue.html

Si dice questo è in coda ha un contruct per coda di priorità. Ma non sono riuscito a trovare come implementarlo.

class Queue.PriorityQueue(maxsize=0) 

Link 2: Mucchio Attuazione http://docs.python.org/library/heapq.html

Qui si dice che siamo in grado di implementare code di priorità indirettamente tramite 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' 

Qual è l'implementazione coda di priorità più efficiente in Python? E come implementarlo?

Answer 1

la versione nella coda modulo è implemented usando il modulo heapq, in modo che abbiano uguale efficienza per le operazioni di heap sottostanti.

Detto questo, la versione è più lenta poiché aggiunge blocchi, incapsulamento e una buona API orientata agli oggetti.

Lo priority queue suggestions shown in the heapq docs è inteso a mostrare come aggiungere funzionalità aggiuntive a una coda di priorità (come la stabilità dell'ordinamento e la possibilità di modificare la priorità di un'attività precedentemente accodata). Se non hai bisogno di tali funzionalità, le funzioni di base heappush e heappop ti daranno le prestazioni più veloci.

Answer 2

Non esiste una "implementazione di coda di priorità più efficiente" in qualsiasi lingua.

Una coda di priorità è tutta una questione di compromessi. Vedere http://en.wikipedia.org/wiki/Priority_queue

Si dovrebbe scegliere uno di questi due, in base a come si prevede di utilizzarlo:

• O(log(N)) tempo di inserimento e O(1) tempo findMin + deleteMin, o
• O(1) tempo di inserimento e O(log(N)) findMin + deleteMin time

In quest'ultimo caso, è possibile scegliere di implementare una coda di priorità con un heap di Fibonacci: http://en.wikipedia.org/wiki/Heap_(data_structure)#Comparison_of_theoretic_bounds_for_variants (come ou può vedere, heapq che è fondamentalmente un albero binario, deve necessariamente avere O(log(N)) sia per l'inserimento e findMin + deleteMin)

Se avete a che fare con i dati con proprietà speciali (come i dati delimitate), allora si può ottenere O(1) inserimento e O(1) findMin + deleteMin time. Puoi farlo solo con determinati tipi di dati, perché altrimenti potresti abusare della tua coda di priorità per violare il numero O(N log(N)) legato all'ordinamento.

Per implementare qualsiasi coda in qualsiasi lingua, è sufficiente definire le operazioni insert(value) e extractMin() -> value.Questo generalmente richiede solo un involucro minimale dell'heap sottostante; vedi http://en.wikipedia.org/wiki/Fibonacci_heap per implementare il proprio, o utilizzare una libreria off-the-shelf di un mucchio simile come un accoppiamento Heap (una ricerca su Google ha rivelato http://svn.python.org/projects/sandbox/trunk/collections/pairing_heap.py)

---

Se vi interessa soltanto quale delle due si fa riferimento sono più efficiente (il codice di heapq based da http://docs.python.org/library/heapq.html#priority-queue-implementation-notes cui è incluso sopra, contro Queue.PriorityQueue), quindi:

ci non sembra essere qualsiasi discussione facilmente trovabili sul web come a ciò che sta effettivamente facendo Queue.PriorityQueue; si avrebbe a fonte tuffo nel codice, che è legata alla dalla documentazione di aiuto: 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) 

Come possiamo vedere, Queue.PriorityQueue è anche utilizzando heapq come un meccanismo sottostante. Pertanto sono ugualmente cattivi (asintoticamente parlando). Queue.PriorityQueue potrebbe consentire query parallele, quindi vorrei scommettere che potrebbe avere un fattore leggermente più costante di overhead. Ma poiché sai che l'implementazione di base (e il comportamento asintotico) devono essere uguali, il modo più semplice sarebbe semplicemente di eseguirli sullo stesso set di dati di grandi dimensioni.

(Si noti che Queue.PriorityQueue non sembra avere un modo per rimuovere le voci, mentre lo fa heapq. Tuttavia questa è un'arma a doppio taglio: implementazioni di coda con priorità buona potrebbero eventualmente consentire di eliminare elementi in O (1) o O (log (N)), ma se usi la funzione remove_task che hai menzionato e lasci che quelle attività zombi si accumulino nella tua coda perché non le estrai dal minimo, allora vedrai un rallentamento asintotico che non dovresti altrimenti vedere. Naturalmente, non si poteva fare questo con Queue.PriorityQueue, in primo luogo, in modo che nessun confronto può essere fatto qui.)

Answer 3

Anche se questa domanda è stata accettata e contrassegnata come accettata, ancora qui è una semplice implementazione personalizzata di Coda prioritaria senza utilizzare alcun modulo per capire come funziona.

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

Trova il codice completo e la spiegazione qui: https://www.studytonight.com/code/python/algo/priority-queue-in-python.php