Java - PriorityQueue vs ordinati LinkedList

Question

Quale implementazione è meno "pesante": PriorityQueue o LinkedList ordinata (utilizzando un comparatore)?

Voglio che tutti gli elementi siano ordinati. L'inserimento sarà molto frequente e occasionalmente dovrò eseguire tutta la lista per fare alcune operazioni.

Answer 1

A LinkedList è la scelta peggiore. Utilizzare uno ArrayList (o, più in generale, un implementatore RandomAccess) o PriorityQueue. Se si utilizza un elenco, ordinarlo solo prima di iterare sul suo contenuto, non dopo ogni inserimento.

Una cosa da notare è che l'iteratore PriorityQueue fa non fornire gli elementi in ordine; dovrete effettivamente rimuovere gli elementi (svuotare la coda) per scorrere gli elementi in ordine.

Answer 2

È necessario implementare entrambi e quindi eseguire test delle prestazioni sui dati effettivi per vedere quale funziona meglio nelle circostanze specifiche.

Answer 3

Se si utilizza uno LinkedList, è necessario ricorrere agli elementi ogni volta che ne è stato aggiunto uno e poiché gli inserimenti sono frequenti, non utilizzerei uno LinkedList. Quindi, in questo caso, utilizzerei un PriorityQueue Se aggiungerai elementi univoci all'elenco, ti consiglio di utilizzare un SortedSet (una implementazione è TreeSet).

Answer 4

Avete bisogno di essere ordinato in ogni momento? Se questo è il caso, potresti voler andare con qualcosa come un set di alberi (o altri SortedSet con una ricerca veloce).

Se è necessario solo occasionalmente ordinato, andare con un elenco collegato e ordinarlo quando è necessario l'accesso. Lascia che sia non ordinato quando non hai bisogno di accedere.

Answer 5

java.util.PriorityQueue è

"Una coda di priorità illimitata sulla base di un cumulo priorità"

. La struttura dei dati heap ha molto più senso di una lista collegata

Answer 6

C'è una differenza fondamentale tra le due strutture dati e non sono così facilmente intercambiabili come si potrebbe pensare.

Secondo la documentazione CodaConPriorita:

all'iteratore prevista metodo iterator() non è garantito per attraversare gli elementi della coda di priorità in un ordine particolare.

Utilizzare un oggetto Array e chiamare Collections.sort() su di esso solo prima di iterare l'elenco.

Answer 7

Il problema con PriorityQueue è che è necessario svuotare la coda per ottenere gli elementi in ordine. Se questo è ciò che vuoi, allora è una buona scelta. Altrimenti, è possibile utilizzare uno ArrayList che si ordina solo quando è necessario il risultato ordinato o, se gli elementi sono distinti (rispetto al comparatore), uno TreeSet. Sia TreeSet e ArrayList non sono molto "pesanti" in termini di spazio; che è più veloce dipende dal caso d'uso.

Answer 8

Sono in grado di vedere due opzioni, una delle quali dipende dalla necessità di disporre di elementi duplicati.

Se non è necessario mantenere gli elementi duplicati nell'elenco, utilizzare un SortedSet (probabilmente un TreeSet).

Se è necessario mantenere gli elementi duplicati, andrei con una lista collegata e inserire nuovi elementi nella lista nell'ordine corretto.

PriorityQueue non si adatta perfettamente a meno che non si desideri rimuovere gli elementi ogni volta che si eseguono operazioni.

Proseguendo con gli altri, assicurati di utilizzare la creazione di profili per assicurarti di scegliere la soluzione corretta per il tuo problema specifico.

Answer 9

Ho fatto un piccolo punto di riferimento su questo problema. Se si desidera ordinare l'elenco dopo la fine di tutti gli inserimenti, non c'è quasi nessuna differenza tra PriorityQueue e LinkedList (LinkedList è leggermente migliore, da 5 a 10 percento più veloce sulla mia macchina), tuttavia se si utilizza ArrayList si otterrà un ordinamento quasi 2 volte più veloce rispetto a PriorityQueue.

Nel mio benchmark per le liste ho misurato il tempo dall'inizio del riempimento con valori fino alla fine dell'ordinamento. Per CodaConPriorita - a partire dall'inizio di riempire fino alla fine delle operazioni di voto tutti gli elementi (perché gli elementi vengono ordinati in CodaConPriorita durante la rimozione loro come indicato nella Erickson risposta)

Answer 10

aggiungere oggetti alla coda di priorità sarà log O (n) e lo stesso per ogni pol. Se si inseriscono spesso inserimenti su code molto grandi, ciò potrebbe influire sulle prestazioni. L'inserimento nella parte superiore di ArrayList è costante, quindi nel complesso tutti gli inserti saranno più veloci su ArrayList che sulla coda di priorità.

Se è necessario acquisire TUTTI gli elementi nell'ordine ordinato, Collections.sort funzionerà in circa O n log (n) tempo totale. Dove ogni pol dalla coda di priorità sarà O log (n) tempo, quindi se prendi tutte le n cose dalla coda che sarà di nuovo O n log (n).

Il caso d'uso in cui la coda di priorità vince è se si sta cercando di trovare quale sia il valore più grande nella coda in un dato momento. Per farlo con ArrayList devi ordinare l'intera lista ogni volta che vuoi sapere il più grande. Ma con la coda di priorità sa sempre qual è il valore più grande.

Answer 11

IMHO: non è necessario PriorityQueue se si dispone di LinkedList. Posso ordinare la coda con LinkedList più velocemente che con PriorityQueue. per esempio.

Queue list = new PriorityQueue(); 
list.add("1"); 
list.add("3"); 
list.add("2"); 
while(list.size() > 0) { 
    String s = list.poll().toString(); 
    System.out.println(s); 
} 

Credo che questo codice funzioni troppo a lungo, perché ogni volta che aggiungo elemento, esso ordinerà gli elementi. ma se userò codice successivo:

Queue list = new LinkedList(); 
list.add("1"); 
list.add("3"); 
list.add("2"); 
List lst = (List)list; 
Collections.sort(lst); 
while(list.size() > 0) { 
    String s = list.poll().toString(); 
    System.out.println(s); 
} 

Penso che questo codice sarà sorta solo una volta e sarà più veloce che l'utilizzo di CodaConPriorita. Quindi, una volta posso ordinare il mio LinkedList una volta, prima di usarlo, in ogni caso e funzionerà più velocemente. E anche se ordina allo stesso tempo non ho davvero bisogno di PriorityQueue, non abbiamo davvero bisogno di questa classe.