¿Cómo ordeno archivos muy grandes?

Tengo algunos archivos que deben ordenarse de acuerdo con la identificación al comienzo de cada línea. Los archivos son de aproximadamente 2-3 gb.

Traté de leer todos los datos en una ArrayList y ordenarlos. Pero la memoria no es suficiente para mantenerlos a todos. No funciona.

Las líneas se ven como

0052304 0000004000000000000000000000000000000041 John Teddy 000023
0022024 0000004000000000000000000000000000000041 George Clan 00013

¿Cómo puedo ordenar los archivos?

Eso no es exactamente un problema de Java. Debe buscar un algoritmo eficiente para clasificar datos que no se leen por completo en la memoria. Algunas adaptaciones a Merge-Sort pueden lograr esto.

Eche un vistazo a esto: http://en.wikipedia.org/wiki/Merge_sort

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

Básicamente, la idea aquí es dividir el archivo en partes más pequeñas, ordenarlas (ya sea con tipo de fusión u otro método), y luego usar la fusión de merge-sort para crear el nuevo archivo ordenado.

Necesitas un tipo de combinación externa para hacer eso. Aquí hay una implementación de Java que ordena archivos muy grandes.

Como sus registros ya están en formato de archivo de texto sin formato, puede canalizarlos a UNIX sort(1) por ejemplo sort -n -t' ' -k1,1 < input > output . Automáticamente dividirá los datos y realizará una clasificación de fusión utilizando la memoria disponible y /tmp . Si necesita más espacio del que tiene memoria disponible, agregue -T /tmpdir al comando.

Es bastante divertido que todo el mundo te diga que descargues grandes bibliotecas de C o Java o que implementes una clasificación de fusión cuando puedas usar una herramienta que está disponible en todas las plataformas y que ha existido durante décadas.

En lugar de cargar todos los datos en la memoria de una vez, puede leer solo las teclas y un índice donde comienza la línea (y posiblemente la longitud también), por ejemplo

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

Esto usaría unos 40 bytes por línea.

Una vez que haya ordenado esta matriz, puede usar RandomAccessFile para leer las líneas en el orden en que aparecen.

Nota: dado que tocará aleatoriamente el disco, en lugar de usar la memoria, esto podría ser muy lento. Un disco típico tarda 8 ms para acceder aleatoriamente a los datos y si tiene 10 millones de líneas, esto tomará alrededor de un día. (Este es el peor caso absoluto) En memoria tomaría unos 10 segundos.

Puede usar el archivo db de SQL Lite, cargar los datos en el db y luego dejar que se ordene y devolver los resultados por usted.

Ventajas: no necesita preocuparse por escribir el mejor algoritmo de clasificación.

Desventaja: Necesitará espacio en disco, procesamiento más lento.

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

Lo que debe hacer es dividir los archivos en una transmisión y procesarlos por separado. Luego puede combinar los archivos ya que ya estarán ordenados, esto es similar a cómo funciona la fusión.

La respuesta de esta pregunta SO será de valor: transmitir archivos de gran tamaño

Los sistemas operativos vienen con una potente utilidad de clasificación de archivos. Una función simple que llama a un script bash debería ayudar.

 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(); } } 

Debe realizar una clasificación externa. Es amable la idea detrás de Hadoop / MapReduce, solo que no tiene en cuenta el clúster distribuido y funciona en un solo nodo.

Para un mejor rendimiento, debe usar Hadoop / Spark.

enter image description here Cambia estas líneas de acuerdo a tu sistema. fpath es su gran archivo de entrada (probado con 20 GB). shared ruta shared es donde se almacena el registro de ejecución. fdir es donde se almacenarán y fusionarán los archivos intermedios. Cambie estos caminos de acuerdo a su máquina.

 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"; 

Luego ejecuta el siguiente progtwig. Su archivo final ordenado se creará con el nombre op401 en fdir path. la última línea Runtime.getRuntime().exec("valsort " + fdir + "op" + (treeHeight*100)+1 + " > " + opLog); comprueba que la salida esté ordenada o no. Elimine esta línea si no tiene valsort instalado o si el archivo de entrada no se genera utilizando gensort ( http://www.ordinal.com/gensort.html ).

Tampoco te olvides de cambiar int totalLines = 200000000; a las líneas totales en su archivo. y el recuento de subprocesos ( int threadCount = 16 ) debe estar siempre en potencia de 2 y lo suficientemente grande para que la cantidad de datos (tamaño total * 2 / no de subproceso) pueda residir en la memoria. Cambiar el conteo de subprocesos cambiará el nombre del archivo de salida final. Como para 16, será op401, para 32 será op501, para 8 será op301, etc.

Disfrutar.

  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(); } }