Perché l'implementazione di ordinamento di Java converte una lista in una matrice prima dell'ordinamento?

Question

In JDK 1.8, la prima istruzione del metodo java.util.List#sort(Comparator) è il seguente:

Object[] a = this.toArray(); 

E 'costoso per copiare l'elenco in un array, ordinare, e ripristinare ogni nodo della lista per il valore di ordinata dalla array.

Sembra che sia possibile non copiare i valori su un array temporaneo quando si ordina un ArrayList. Ho ragione? Se no, cosa ha guidato i creatori del metodo?

Answer 1

sort nell'interfaccia java.util.List è l'implementazione predefinita dell'ordinamento elenco.

ArrayList sostituisce questo valore predefinito con un metodo di ordinamento che ordina direttamente l'array interno.

Answer 2

Per ArrayList, o altri elenchi di accesso casuale, potresti essere corretto.

Tuttavia, Collections.sort supporta qualsiasi implementazione Elenco. Per una LinkedList, ad esempio, sarebbe stato molto espansivo scambiare elementi durante l'ordinamento (dal momento che trovare l'elemento ith richiede tempo lineare).

Conversione di un elenco in un array e impostazione degli elementi dell'elenco originale dopo l'ordinamento dell'array aggiunge un componente di tempo lineare all'algoritmo, che non modifica il tempo di funzionamento asintotico di (O(nlog(n))).

Answer 3

In OpenJDK 1.8, java.util.ArrayList#sort(Comparator) non copia la sua matrice interna; si ordina sul posto, come suggerisci dovrebbe.

L'attuazione di java.util.List#sort() che stai criticando ha la seguente documentazione di accompagnamento:

L'implementazione predefinita ottiene un array contenente tutti gli elementi in questo elenco, ordina l'array e itera su questa lista reset ogni elemento da la posizione corrispondente nella matrice. (Questo evita la n² log (n) prestazioni che deriverebbe dal tentativo di ordinare una lista collegata al suo posto.)

Cioè, copiando la matrice e muoversi con accesso casuale è più efficiente rispetto alla testa di avanzare linearmente in una lista collegata. L'implementazione comune tenta di scambiare l'overhead di copia per l'overhead di accesso agli elementi. Per casi come ArrayList in cui la copia non è necessaria per ottenere lo stesso accesso casuale agli elementi, la libreria omette la copia sovrascrivendo il metodo.

un interessante confronto: Guarda std::sort() e std::list::sort() funzioni del ++ libreria standard C:

• std::sort() Richiede parametri che delimitano un intervallo con accesso casuale.
• std::list::sort() Si presuppone solo accesso lineare attraversando i nodi dell'elenco collegati.

Il generico std::sort() algoritmo è più efficiente, ma la biblioteca osta definendolo su un std::list (che è una lista collegata, simile a Java di java.util.LinkedList). La libreria offre un mezzo meno efficiente per ordinare uno std::list per comodità. A differenza della libreria Java, la libreria C++ non copia uno std::list() in una matrice per utilizzare l'algoritmo di accesso casuale std::sort().