È più rapido aggiungerlo a una raccolta, quindi ordinarlo o aggiungerlo a una raccolta ordinata?

Se ho una Map come questa:

 HashMap map; 

e voglio ottenere una raccolta di valori ordinati usando l’ordinamento naturale, quale metodo è il più veloce?

(UN)

Crea un’istanza di una raccolta ordinabile come ArrayList , aggiungi i valori, quindi ordinala:

 List sortedCollection = new ArrayList(map.values()); Collections.sort(sortedCollection); 

(B)

Crea un’istanza di una raccolta ordinata come TreeSet , quindi aggiungi i valori:

 Set sortedCollection = new TreeSet(map.values()); 

Si noti che la raccolta risultante non viene mai modificata, quindi l’ordinamento deve essere eseguito solo una volta.

TreeSet ha una log(n) complessità temporale garantita per i metodi add()/remove()/contains() . L’ordinamento di una ArrayList richiede operazioni n*log(n) , ma add()/get() richiede solo 1 operazione.

Quindi, se stai principalmente recuperando e non riordinare spesso, ArrayList è la scelta migliore. Se si ordina spesso, ma non recuperare quel tanto TreeSet sarebbe una scelta migliore.

In teoria, lo smistamento alla fine dovrebbe essere più veloce. Il mantenimento dello stato ordinato attraverso il processo potrebbe comportare un ulteriore tempo di CPU.

Dal punto di vista del CS, entrambe le operazioni sono NlogN, ma 1 sort dovrebbe avere una costante inferiore.

Perché non usare il meglio di entrambi i mondi? Se non lo utilizzi più, ordina usando un set di alberi e inizializza un ArrayList con i contenuti

 List sortedCollection = new ArrayList( new TreeSet(map.values())); 

MODIFICARE:

Ho creato un benchmark (puoi accedervi da pastebin.com/5pyPMJav ) per testare i tre approcci (ArrayList + Collections.sort, TreeSet e il mio meglio dell’approccio di entrambi i mondi) e il mio vince sempre. Il file di test crea una mappa con 10000 elementi, i cui valori hanno un comparatore intenzionalmente terribile, e quindi ciascuna delle tre strategie ha la possibilità di a) ordinare i dati e b) scorrere su di essa. Ecco alcuni esempi di output (puoi testarlo da soli):

EDIT: ho aggiunto un aspetto che registra le chiamate a Thingy.compareTo (Thingy) e ho anche aggiunto una nuova strategia basata su PriorityQueues che è molto più veloce di una delle soluzioni precedenti (almeno nell’ordinamento).

 compareTo() calls:123490 Transformsr ArrayListTransformsr Creation: 255885873 ns (0.255885873 seconds) Iteration: 2582591 ns (0.002582591 seconds) Item count: 10000 compareTo() calls:121665 Transformsr TreeSetTransformsr Creation: 199893004 ns (0.199893004 seconds) Iteration: 4848242 ns (0.004848242 seconds) Item count: 10000 compareTo() calls:121665 Transformsr BestOfBothWorldsTransformsr Creation: 216952504 ns (0.216952504 seconds) Iteration: 1604604 ns (0.001604604 seconds) Item count: 10000 compareTo() calls:18819 Transformsr PriorityQueueTransformsr Creation: 35119198 ns (0.035119198 seconds) Iteration: 2803639 ns (0.002803639 seconds) Item count: 10000 

Stranamente, il mio approccio funziona al meglio in iterazione (avrei pensato che non ci sarebbero state differenze nell’approccio di ArrayList in iterazione, ho un bug nel mio benchmark?)

Disclaimer: so che questo è probabilmente un punto di riferimento terribile, ma aiuta a capire il punto e io di certo non lo ho manipolato per far vincere il mio approccio.

(Il codice ha una dipendenza da apache commons / lang per i builder uguali / hashcode / compareTo, ma dovrebbe essere facile da rifattorizzare)

Assicurati di leggere il mio commento su TreeSet in fondo se scegli di implementare B)

Se la tua app funziona solo occasionalmente ma itera moltissimo, direi che stai meglio usando un elenco semplice e non ordinato. Ordinalo una volta e poi beneficia di una iterazione più veloce. L’iterazione è particolarmente veloce su un elenco di array.

Tuttavia, se vuoi che l’ordinamento sia sempre garantito o che tu stia aggiungendo / rimuovendo gli elementi frequentemente, allora usi una raccolta ordinata e prenda il colpo sull’iterazione.

Quindi nel tuo caso direi A) è l’opzione migliore. L’elenco viene ordinato una volta, non cambia e pertanto beneficia di un array. L’iterazione dovrebbe essere molto veloce, specialmente se si conosce una ArrayList e si può usare direttamente ArrayList.get () invece di un Iterator.

Vorrei anche aggiungere che TreeSet per definizione è un Set che significa che gli oggetti sono unici. Un TreeSet determina l’uguaglianza usando compareTo sul tuo Comparatore / Comparabile. Potresti facilmente ritrovarti dei dati mancanti se provi ad aggiungere due oggetti il ​​cui compareTo restituisce il valore 0. Ad esempio, aggiungendo “C”, “A”, “B”, “A” a un TreeSet restituirà “A”, “B “,” C ”

Collections.sort utilizza mergeSort che ha O (nlog n).

TreeSet ha un albero rosso-nero sottostante, le operazioni di base hanno O (logn). Quindi n elementi ha anche O (nlog n).

Quindi entrambi sono lo stesso grande algoritmo O.

L’inserimento in un SortedSet è O (log (n)) (MA l’attuale n e non l’ultimo n). L’inserimento in una lista è 1.

L’ordinamento in un SortedSet è già incluso nell’inserimento, quindi è 0. L’ordinamento in un elenco è O (n * log (n)).

La complessità totale di SortedSet è quindi O (n * k), k

Quindi, SortedSet ha matematicamente le migliori prestazioni. Ma alla fine, hai un Set invece di un Elenco (perché SortedList non esiste) e Set ti offre meno funzioni di List. Quindi, a mio parere, la soluzione migliore per le funzionalità e le prestazioni disponibili è quella proposta da Sean Patrick Floyd:

  • utilizzare un SortedSet per l’inserimento,
  • inserire SortedSet come parametro per la creazione di un elenco da restituire.