Come si esegue un ordinamento di array efficiente in memoria in java?

Sto cercando di ordinare una vasta gamma di stringhe (in particolare File.list(), che non riesco a esternare o ridurre ulteriormente) senza utilizzare [molta] memoria extra.Come si esegue un ordinamento di array efficiente in memoria in java?

Arrays.sort() dice che fa un ordinamento di unione e wikipedia dice che alcune implementazioni allocano la dimensione dell'array originale per la memorizzazione dell'output ordinato. (Questo sembra essere supportato dal riferimento System.arraycopy nel metodo).

Esiste un algoritmo di ordinamento sul posto che è invece possibile utilizzare per la memoria?

fonte

2011-05-13 Stephen

Quanto complesso un algoritmo di ordinamento sei felice di scrivere a mano e vuoi che sia stabile (nel senso che gli elementi di uguale valore appaiono nell'array finale nello stesso ordine in cui sembra abbiano inizio)? Non che tu possa davvero capire la differenza con String a meno che non inizi a guardare "System.identityHashcode" o qualsiasi altra cosa. –

quicksort è sul posto e molto veloce. Vedi here.

fonte

2011-05-13 02:41:36 dlev

Ok: è fantastico; Apache o Google hanno una libreria con un quicksort? (Sono sicuro di averne visto uno prima ...) – Stephen

quicksort è molto veloce, ma è anche uno dei tipi più costosi, dal punto di vista della memoria –

@Sam Quicksort può essere implementato sul posto, che credo lo renda bene per quanto riguarda la memoria. –

È possibile scrivere un algoritmo di ordinamento heap per l'ordinamento sul posto.

fonte

2011-05-13 02:47:28

String è immutabile in Java. Pertanto, quando l'array di String s nella tua domanda viene duplicato, non richiede tutto lo spazio che ti aspetti. In realtà, l'overhead può essere abbastanza minimale.

In altre parole, Java Arrays#sort() può essere perfetto per la soluzione. Puoi testare la performance da solo.

Per il titolo della domanda, la risposta di Ankit e la risposta di dlev vanno bene.

fonte

2011-05-13 03:26:51

Per essere chiari, ciò che verrà duplicato è solo l'array di oggetti * riferimenti * (in genere 4 o 8 byte per stringa) non gli oggetti String stessi, e quindi non le matrici di caratteri all'interno di ogni stringa. –

Come si esegue un ordinamento di array efficiente in memoria in java?

risposta

Problemi correlati