Qual è la differenza tra heapq e PriorityQueue in python?

Question

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?

Answer 1

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 classe Queue in questo modulo implementa tutte le semantiche di blocco richieste. Dipende dalla disponibilità del supporto per i thread in Python; vedere il modulo threading.

Il modulo heapq offre nessun impuntamento, e funziona secondo list oggetti standard, che non sono destinate ad essere thread-safe.

Infatti, il PriorityQueueattuazione 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.

Answer 2

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