file basato merge sort su grandi serie di dati in Java

Question

dato grandi serie di dati che non rientrano nella memoria, c'è qualche libreria o API per eseguire sorta in Java? l'applicazione potrebbe possibilmente essere simile a utilità Linux ordinamento.

Answer 1

Java fornisce una routine di ordinamento general-purpose che può essere usato come parte della soluzione più grande per il vostro problema. Un approccio comune ai dati di ordinamento che è troppo grande per tutti in forma in memoria è questo:

1) Leggi tutti i dati che si inserisce nella memoria principale, diciamo che si tratta di 1 Gb

2) Quicksort che 1 Gb (ecco dove devi usare Java incorporato ordinamento dal quadro Collections)

3) che allineati 1 Gb su disco come "chunk-1"

4) Ripetere i passaggi 1-3 fino a quando hai passato attraverso tutti i dati, salvando ogni blocco di dati in un file separato. Quindi, se i dati originali erano 9 Gb, si avranno ora 9 risolto blocchi di dati etichettati "chunk-1" a "chunk-9"

5) A questo punto è solo bisogno di un merge finale sorta di fondere il 9 ordinato pezzi in un unico insieme di dati completamente ordinato. Il merge sort funziona in modo molto efficiente contro questi pezzi pre-assortiti. Si aprirà essenzialmente 9 lettori di file (uno per ogni pezzo), più uno scrittore di file (per l'uscita). Confronta, poi, il primo elemento di dati in ogni file in lettura e seleziona il valore più piccolo, che è scritto nel file di output. Il lettore da cui tale valore selezionato è venuto avanza alla sua prossima elemento di dati, e il processo di confronto a 9 vie per trovare il valore più piccolo si ripete, a scrivere di nuovo la risposta al file di output. Questo processo si ripete fino a quando tutti i dati sono stati letti da tutti i file chunk.

6) Una volta che il punto 5 ha finito di leggere tutti i dati che si stanno fatto - il file di output contiene ora un set di dati completamente ordinato

Con questo approccio si potrebbe facilmente scrivere un generico programma di utilità "megasort" della propria che prende un nome di file e maxMemory parametro ed efficiente ordina il file utilizzando i file temporanei. Scommetto che si possa trovare almeno alcune implementazioni là fuori per questo, ma se non si può semplicemente rotolare il proprio come descritto sopra.

Answer 2

Il modo più comune per gestire grandi quantità di dati è in memoria (è possibile acquistare un server con 1 TB in questi giorni) o in un database.

Se non si ha intenzione di utilizzare un database (o comprare più memoria) è possibile scrivere da soli giusto facilmente.

Ci sono le librerie che possono aiutare, che svolgono funzioni di Map-Reduce ma possono aggiungere più complessità di quello che risparmiano.