In Python esiste un algoritmo integrato heapq
che fornisce push
, pop
, nlargest
, nsmallest
ecc. Che è possibile applicare agli elenchi. Tuttavia, c'è anche la classe queue.PriorityQueue
che sembra supportare più o meno la stessa funzionalità. Qual è la differenza e quando utilizzeresti l'una rispetto all'altra?Qual è la differenza tra heapq e PriorityQueue in python?
risposta
Queue.PriorityQueue
è una classe thread-safe, mentre il modulo heapq
non garantisce la sicurezza del thread. Dal Queue
module documentation:
Il modulo implementa
Queue
multi-produttori, code multi-consumo. È particolarmente utile nella programmazione con thread quando le informazioni devono essere scambiate in modo sicuro tra più thread. La classeQueue
in questo modulo implementa tutte le semantiche di blocco richieste. Dipende dalla disponibilità del supporto per i thread in Python; vedere il modulothreading
.
Il modulo heapq
offre nessun impuntamento, e funziona secondo list
oggetti standard, che non sono destinate ad essere thread-safe.
Infatti, il PriorityQueue
attuazione utilizza heapq
sotto il cofano per fare tutto il lavoro prioritizzazione, con la classe di base Queue
fornire il bloccaggio per rendere questo thread-safe. Vedi lo source code per i dettagli.
Questo rende il modulo heapq
più veloce; non c'è nessun sovraccarico di blocco. Inoltre, sei libero di utilizzare le varie funzioni heapq
in modi diversi e nuovi, lo PriorityQueue
offre solo la funzionalità di accodamento in linea.
queue.PriorityQueue è un wrapper parziale attorno alla classe heapq.
In altre parole, un queue.PriorityQueue è in realtà un heapq, inserito nel modulo della coda con un paio di metodi rinominati per rendere l'heapq più facile da usare, proprio come una normale coda.
In heapq, si utilizza il metodo heappush() per aggiungere un nuovo elemento e il metodo heappop() per rimuoverne uno. Non è molto simile alla coda, quindi queue.PriorityQueue consente di utilizzare i soliti metodi di coda come push e pop per fare la stessa cosa.
Ci sono alcune funzionalità di heapq che non vengono trasferite in queue.PriorityQueue, come heappushpop() e heapreplace(), ma si preferisce non utilizzarle. Se ne hai bisogno (e lo faccio nel mio attuale progetto), usa heapq piuttosto che queue.PriorityQueue.
Inoltre, poiché heapq è specializzato per lo scopo, non è thread-safe (come indicato in un'altra risposta qui.)