Come faccio a ordinare file molto grandi

Ho alcuni file che dovrebbero essere ordinati secondo l’id all’inizio di ogni riga. I file sono circa 2-3 GB.

Ho provato a leggere tutti i dati in un ArrayList e ordinarli. Ma la memoria non è sufficiente per tenerli tutti. Non funziona.

Le linee sembrano

0052304 0000004000000000000000000000000000000041 John Teddy 000023
0022024 0000004000000000000000000000000000000041 George Clan 00013

Come posso ordinare i file ??

Questo non è esattamente un problema Java. È necessario esaminare un algoritmo efficiente per ordinare i dati che non sono completamente letti in memoria. Alcuni adattamenti a Merge-Sort possono raggiungere questo objective.

Dai un’occhiata a questo: http://en.wikipedia.org/wiki/Merge_sort

e: http://en.wikipedia.org/wiki/External_sorting

Fondamentalmente l’idea qui è quella di suddividere il file in parti più piccole, ordinarle (con l’ordinamento di tipo merge o un altro metodo) e quindi utilizzare l’unione da unire-ordinamento per creare il nuovo file ordinato.

Hai bisogno di un ordinamento di fusione esterno per farlo. Ecco una sua implementazione Java che ordina file molto grandi.

Dal momento che i tuoi record sono già in formato testo di file flat, puoi inserirli in sort(1) UNIX sort(1) ad es. sort -n -t' ' -k1,1 < input > output . Dividerà automaticamente i dati ed eseguirà l’ordinamento di merge usando la memoria disponibile e /tmp . Se hai bisogno di più spazio di quanta hai memoria disponibile, aggiungi -T /tmpdir al comando.

È abbastanza divertente che tutti stiano dicendo di scaricare enormi librerie C # o Java o implementare un merge-sort quando si può usare uno strumento disponibile su ogni piattaforma ed esiste da decenni.

Invece di caricare tutti i dati nella memoria in una volta, puoi leggere solo le chiavi e un indice dove inizia la linea (e possibilmente anche la lunghezza) ad esempio

 class Line { int key, length; long start; } 

Questo userebbe circa 40 byte per riga.

Una volta ordinato questo array, è ansible utilizzare RandomAccessFile per leggere le righe nell’ordine in cui appaiono.

Nota: poiché il disco verrà colpito a caso, invece di utilizzare la memoria potrebbe essere molto lento. Un disco tipico richiede 8 ms per accedere in modo casuale ai dati e se si dispone di 10 milioni di linee questo richiederà circa un giorno. (Questo è assolutamente il caso peggiore) In memoria ci vorrebbero circa 10 secondi.

È ansible utilizzare il file SQL Lite db, caricare i dati nel db e quindi lasciarli ordinare e restituire i risultati.

Vantaggi: non è necessario preoccuparsi di scrivere il miglior algoritmo di ordinamento.

Svantaggio: avrai bisogno di spazio su disco, elaborazione più lenta.

https://sites.google.com/site/arjunwebworld/Home/programming/sorting-large-data-files

Quello che devi fare è dividere i file in uno stream ed elaborarli separatamente. Quindi puoi unire i file insieme poiché saranno già ordinati, questo è simile a come funziona l’ordinamento di unione.

La risposta di questa domanda SO avrà valore: esegui lo streaming di file di grandi dimensioni

I sistemi operativi sono dotati di una potente utility per l’ordinamento dei file. Una semplice funzione che chiama uno script di bash dovrebbe aiutare.

 public static void runScript(final Logger log, final String scriptFile) throws IOException, InterruptedException { final String command = scriptFile; if (!new File (command).exists() || !new File(command).canRead() || !new File(command).canExecute()) { log.log(Level.SEVERE, "Cannot find or read " + command); log.log(Level.WARNING, "Make sure the file is executable and you have permissions to execute it. Hint: use \"chmod +x filename\" to make it executable"); throw new IOException("Cannot find or read " + command); } final int returncode = Runtime.getRuntime().exec(new String[] {"bash", "-c", command}).waitFor(); if (returncode!=0) { log.log(Level.SEVERE, "The script returned an Error with exit code: " + returncode); throw new IOException(); } } 

È necessario eseguire un ordinamento esterno. È gentile l’idea alla base di Hadoop / MapReduce, solo che non prende in considerazione il cluster distribuito e lavora su un singolo nodo.

Per prestazioni migliori, dovresti usare Hadoop / Spark.

inserisci la descrizione dell'immagine qui Cambia questa linea in base al tuo sistema. fpath è il tuo unico grande file di input (testato con 20 GB). percorso shared è dove è memorizzato il registro di esecuzione. fdir è dove i file intermedi verranno archiviati e uniti. Cambia questi percorsi in base alla tua macchina.

 public static final String fdir = "/tmp/"; public static final String shared = "/exports/home/schatterjee/cs553-pa2a/"; public static final String fPath = "/input/data-20GB.in"; public static final String opLog = shared+"Mysort20GB.log"; 

Quindi eseguire il seguente programma. Il tuo file ordinato finale verrà creato con il nome op401 nel percorso fdir . l’ultima riga Runtime.getRuntime().exec("valsort " + fdir + "op" + (treeHeight*100)+1 + " > " + opLog); controlla che l’output sia ordinato o meno. Rimuovi questa riga se non hai installato valsort o il file di input non viene generato usando gensort ( http://www.ordinal.com/gensort.html ).

Inoltre non dimenticare di cambiare int totalLines = 200000000; alle linee totali nel tuo file. e thread count ( int threadCount = 16 ) dovrebbe essere sempre in potenza di 2 e abbastanza grande in modo che la quantità di dati (dimensione totale * 2 / no del thread) possa risiedere in memoria. Il cambio del numero di thread cambierà il nome del file di output finale. Come per 16, sarà op401, per 32 sarà op501, per 8 sarà op301 ecc.

Godere.

  import java.io.*; import java.nio.file.Files; import java.nio.file.Paths; import java.util.ArrayList; import java.util.Comparator; import java.util.stream.Stream; class SplitFile extends Thread { String fileName; int startLine, endLine; SplitFile(String fileName, int startLine, int endLine) { this.fileName = fileName; this.startLine = startLine; this.endLine = endLine; } public static void writeToFile(BufferedWriter writer, String line) { try { writer.write(line + "\r\n"); } catch (Exception e) { throw new RuntimeException(e); } } public void run() { try { BufferedWriter writer = Files.newBufferedWriter(Paths.get(fileName)); int totalLines = endLine + 1 - startLine; Stream chunks = Files.lines(Paths.get(Mysort20GB.fPath)) .skip(startLine - 1) .limit(totalLines) .sorted(Comparator.naturalOrder()); chunks.forEach(line -> { writeToFile(writer, line); }); System.out.println(" Done Writing " + Thread.currentThread().getName()); writer.close(); } catch (Exception e) { System.out.println(e); } } } class MergeFiles extends Thread { String file1, file2, file3; MergeFiles(String file1, String file2, String file3) { this.file1 = file1; this.file2 = file2; this.file3 = file3; } public void run() { try { System.out.println(file1 + " Started Merging " + file2 ); FileReader fileReader1 = new FileReader(file1); FileReader fileReader2 = new FileReader(file2); FileWriter writer = new FileWriter(file3); BufferedReader bufferedReader1 = new BufferedReader(fileReader1); BufferedReader bufferedReader2 = new BufferedReader(fileReader2); String line1 = bufferedReader1.readLine(); String line2 = bufferedReader2.readLine(); //Merge 2 files based on which string is greater. while (line1 != null || line2 != null) { if (line1 == null || (line2 != null && line1.compareTo(line2) > 0)) { writer.write(line2 + "\r\n"); line2 = bufferedReader2.readLine(); } else { writer.write(line1 + "\r\n"); line1 = bufferedReader1.readLine(); } } System.out.println(file1 + " Done Merging " + file2 ); new File(file1).delete(); new File(file2).delete(); writer.close(); } catch (Exception e) { System.out.println(e); } } } public class Mysort20GB { //public static final String fdir = "/Users/diesel/Desktop/"; public static final String fdir = "/tmp/"; public static final String shared = "/exports/home/schatterjee/cs553-pa2a/"; public static final String fPath = "/input/data-20GB.in"; public static final String opLog = shared+"Mysort20GB.log"; public static void main(String[] args) throws Exception{ long startTime = System.nanoTime(); int threadCount = 16; // Number of threads int totalLines = 200000000; int linesPerFile = totalLines / threadCount; ArrayList activeThreads = new ArrayList(); for (int i = 1; i < = threadCount; i++) { int startLine = i == 1 ? i : (i - 1) * linesPerFile + 1; int endLine = i * linesPerFile; SplitFile mapThreads = new SplitFile(fdir + "op" + i, startLine, endLine); activeThreads.add(mapThreads); mapThreads.start(); } activeThreads.stream().forEach(t -> { try { t.join(); } catch (Exception e) { } }); int treeHeight = (int) (Math.log(threadCount) / Math.log(2)); for (int i = 0; i < treeHeight; i++) { ArrayList actvThreads = new ArrayList(); for (int j = 1, itr = 1; j < = threadCount / (i + 1); j += 2, itr++) { int offset = i * 100; String tempFile1 = fdir + "op" + (j + offset); String tempFile2 = fdir + "op" + ((j + 1) + offset); String opFile = fdir + "op" + (itr + ((i + 1) * 100)); MergeFiles reduceThreads = new MergeFiles(tempFile1,tempFile2,opFile); actvThreads.add(reduceThreads); reduceThreads.start(); } actvThreads.stream().forEach(t -> { try { t.join(); } catch (Exception e) { } }); } long endTime = System.nanoTime(); double timeTaken = (endTime - startTime)/1e9; System.out.println(timeTaken); BufferedWriter logFile = new BufferedWriter(new FileWriter(opLog, true)); logFile.write("Time Taken in seconds:" + timeTaken); Runtime.getRuntime().exec("valsort " + fdir + "op" + (treeHeight*100)+1 + " > " + opLog); logFile.close(); } }