Coda prioritaria con una funzione di ricerca - Implementazione più rapida

Question

Sto cercando di implementare una coda di priorità con un requisito aggiuntivo, una funzione di ricerca/ricerca che dirà se un elemento è ovunque all'interno della coda. Quindi le funzioni saranno: insert, del-min e find.

Non sono sicuro se utilizzare un heap o un albero di ricerca binaria autobilanciante. Sembra che i PQ siano solitamente implementati con un Heap, ma mi chiedo se ci sia qualche vantaggio nell'usare un albero di ricerca binario poiché anch'io ho bisogno di quella funzione di ricerca.

Inoltre, in media farò più inserti che eliminazioni. Sto anche considerando un d-ary heap. Fondamentalmente, ogni secondo conta.

Grazie!

Answer 1

IIRC cerca/trova su un heap è O(n) mentre su un albero è O(log(n)) e le altre operazioni PQ standard sono uguali.

Gli heap sono empiricamente più efficienti di qualche fattore costante, quindi se è una grande coda un albero dovrebbe essere migliore, se è piccolo è necessario testare e profilare. è tutto buono sapere in teoria che cosa è più veloce, ma se questi fattori costanti sono grandi può essere completamente irrilevante per insiemi di dati sufficientemente piccoli.

Answer 2

Perché non è possibile utilizzare solo una coda prioritaria e un set? Quando accodasti qualcosa, lo aggiungi al set. Quando lo deseleziona, lo rimuovi dal set. In questo modo il set ti dirà se qualcosa è in coda.

Answer 3

Se la tua operazione di ricerca è relativamente poco frequente (e il tuo heap è abbastanza piccolo), farei una ricerca lineare. Se è relativamente frequente o l'heap è enorme, considera l'appartenenza all'heap di tracciamento (per eseguire il test 'trova') con una struttura dati separata o un flag di oggetto. La gioia dell'indicizzazione esterna è riuscire a mettere il tuo oggetto in tutti i contenitori che vuoi.

Se per "trovare" si intende veramente "trova e modifica" (trovo che spesso devo eliminare elementi dalle code di priorità indipendentemente dal tipico inserimento/del-min), ecco tre approcci che ho utilizzato:

Dato un alto tasso di inserimento/del-min (100k/s continuo) e un basso tasso di find-delete (diciamo 1/s) su un set di lavoro abbastanza piccolo (500-1000) ho fatto una ricerca lineare per l'elemento e poi cancellato dall'albero nel modo standard.

Dato un alto tasso di inserimenti/del-min più ricerche frequenti delete ho semplicemente contrassegnato gli oggetti eliminati come "non interessanti" dopo averli trovati indirettamente. L'attuale libero è stato rinviato fino a quando l'oggetto non è stato rimosso dalla coda come di consueto.

Dato un piccolo std :: priority_queue (che non ha metodi di accesso al di fuori di insert/del-min) di pochi elementi e delezioni abbastanza rari, ho appena copiato l'intera coda in un file std :: vector e copiato la parte modificata/desiderata torna in coda. Poi ho pianto per dormire.

Answer 4

Memorizza i tuoi dati nel contenitore più veloce che hai provato e usa un filtro "bloom" per verificare se qualcosa è nel contenitore.

Ho accoppiato un filtro bloom con una tabella hash in un progetto precedente e ha accelerato di 400 volte le tabelle hash con una media di circa 10k elementi.

Il filtro Bloom è un paio di interessanti proprietà:

• Se la risposta è no da un filtro fioritura, è affidabile al 100%.
• Se la risposta è sì, è necessario controllare la struttura degli altri dati per assicurarsi che l'elemento sia effettivamente presente.
• Assicurati di scegliere una buona funzione di hash :)

Answer 5

Se avete bisogno i vantaggi di più di una struttura di dati, allora si possono usare in composizione. Ad esempio, se sono necessari i vantaggi di una coda di priorità e di un albero di ricerca binario, effettuare le azioni desiderate su entrambi.

Se è insert, inserire l'elemento in entrambi.

Se è find, è possibile trovare l'elemento utilizzando l'albero di ricerca binario e, se è stato trovato, continuare a trovarlo nella coda di priorità.

Se è min quindi rimuoverlo prima dalla coda di priorità e ora che si conosce l'elemento che è, è possibile rimuoverlo dall'albero di ricerca binario.

se è del quindi prima trovarlo nell'albero di ricerca binario e rimuoverlo, quindi continuare a trovarlo nella coda di priorità e rimuoverlo da lì.

Si presume che i nodi dell'albero binario e i nodi della coda di priorità siano puntatori ai propri elementi.

Answer 6

Radix trees con una proprietà min-heap fornirà le proprietà necessarie. Questo in realtà ti darà complessità di tempo costante per le tue operazioni. Ad esempio, se guardiamo a this Haskell implementation, tutte e tre le operazioni citate hanno una complessità temporale O (min (n, W)). Dove n è il numero di elementi e W è il numero di bit in un int (32 o 64).