Ordenar un archivo grande en Java

Question

Tengo un archivo, el cual consiste en una una fila:

1 , 1 2 , 1 3 6 , 4 ,... 

En esta representación, espacios separar los números enteros y las comas. Esta cadena es tan grande que no puedo leerla con RandomAccessFile.readLine() (se necesitan casi 4 Gb). Así que creé un buffer, que puede contener 10 enteros. Mi tarea es ordenar todos los enteros en la cadena.

¿Podría ayudarnos?

EDITAR

@Oscar Reyes

tengo que escribir algunas secuencias de números enteros en un archivo y luego a leer de él. En realidad, no sé cómo hacerlo. Soy un novato Así que decidí usar caracteres para escribir enteros, los delimitadores entre enteros son "," y los delímetros entre secuencias son "\ n \ r". Así que he creado un monstruo que lo lee:

public BinaryRow getFilledBuffer(String filePath, long offset) throws IOException{ 
    mainFile = new RandomAccessFile(filePath, "r"); 

    if (mainFile.length() == 0){ 
     return new BinaryRow(); 
    } 

    StringBuilder str = new StringBuilder(); 

    mainFile.seek(mainFile.length()-4); //that is "\n" symbol 
    char chN = mainFile.readChar(); 

    mainFile.seek(offset); 
    int i = 0; 
    char nextChar = mainFile.readChar(); 
    while (i < 11 && nextChar != chN){ 
     str.append(nextChar); 
     if (nextChar == ','){ 
      i++; 
      if (i == 10){ 
       break; 
      } 
     } 
     nextChar = mainFile.readChar(); 
    } 

    if (nextChar == chN){ 
     position = -1; 
    }else{ 
     position = mainFile.getFilePointer(); 
    } 

    BinaryRow br = new BinaryRow(); 

    StringBuilder temp = new StringBuilder(); 

    for (int j = 0; j < str.length(); j++){ 
     if ((str.charAt(j) != ',')){ 
      temp.append(str.charAt(j)); 
      if (j == str.length() - 1){ 
       br.add(Integer.parseInt(temp.toString())); 
      } 
     }else{ 
      br.add(Integer.parseInt(temp.toString())); 
      temp.delete(0, temp.length()); 
     } 
    } 


    mainFile.close(); 
    return br; 

} 

Si pudiera aconsejar cómo hacerlo, por favor hazlo =)

Answer 1

Leer a la memoria en trozos (100 MB cada uno), un trozo? a la vez, ordénelo y guárdelo en el disco.

A continuación, abra todos los fragmentos ordenados, lea el primer elemento de cada uno y añada el más bajo a la salida. Luego lea el siguiente elemento del fragmento del que acaba de leer y repita.

Al fusionar puede mantener una matriz de la última lectura int de cada fragmento y simplemente iterar sobre ella para obtener la más baja. Luego, sustituye el valor que acaba de utilizar con el siguiente elemento del fragmento del que se tomó.

example with chunks [1, 5, 16] [2, 9, 14] [3, 8, 10] 
array [(1), 2, 3], lowest 1 --> to output 
     [5, (2), 3], lowest 2 --> to output 
     [5, 9, (3)], lowest 3 --> 
     [(5), 9, 8],  5 
     [16, 9, (8)],  8 
     [16, (9), 10],  9 
... 

Answer 2

Este es exactamente el origen QuickSort en aquel entonces no había suficiente memoria RAM para ordenar en la memoria por lo que el procedimiento es almacenar resultados parciales en el disco.

Entonces, ¿qué se puede hacer es:

1. Elige un pivote.
2. Leer secuencialmente los datos del archivo y almacenar más baja que pivote en temp_file_1 y datos más grandes o iguales al pivote en temp_file_2
3. Repetir el procedimiento en temp_file_1 y añadir el resultado a result_file
4. Repetir el procedimiento para temp_file_2 y anexar la resultado de result_file

Cuando las piezas son lo suficientemente pequeños (como 2 acaba de intercambio directo de ellos Lo suficiente como para ser clasificado en la memoria)

de esta manera podrás ordenar en trocea y almacena los resultados parciales en archivos temporales y tendrás un archivo final con el resultado ordenado.

EDIT Te dije que una clasificación rápida era posible.

Parece que necesitarías más espacio para los archivos temporales, después de todo.

Esto es lo que hice.

Creo un archivo de 40 mb con números separados por comas.

lo nombro input:

input http://img200.imageshack.us/img200/5129/capturadepantalla201003t.png

_{de entrada es de 40 MB}

Durante la clase, los archivos temporales con los cubos de "mayor que", "menor que" los valores se crean y cuando el tipo está terminado, los valores se envían a un archivo llamado (adivinen qué) output

processing http://img200.imageshack.us/img200/1672/capturadepantalla201003y.png

_{archivos temporales se crean con los resultados parciales}

Por último, se suprimen todos los archivos temporales y el resultado se guarda en el archivo "salida" con la secuencia correcta ordenados de números:

output http://img203.imageshack.us/img203/5950/capturadepantalla201003w.png

_{Finalmente se crea el archivo "de salida", observe que es de 40 MB también}

Aquí está el progr completa a.m.

import java.io.*; 
import java.util.*; 

public class FileQuickSort { 

    static final int MAX_SIZE = 1024*1024*16; // 16 megabytes in this sample, the more memory your program has, less disk writing will be used. 
    public static void main(String [] args) throws IOException { 
     fileQuickSort(new File("input"), new File("output")); 
     System.out.println(); 
    } 

    // 
    static void fileQuickSort(File inputFile, File outputFile) throws IOException { 
     Scanner scanner = new Scanner(new BufferedInputStream(new FileInputStream(inputFile), MAX_SIZE)); 
     scanner.useDelimiter(","); 

     if(inputFile.length() > MAX_SIZE && scanner.hasNextInt()) { 
      System.out.print("-"); 

      // put them in two buckets... 
      File lowerFile = File.createTempFile("quicksort-","-lower.tmp",new File(".")); 
      File greaterFile = File.createTempFile("quicksort-","-greater.tmp", new File(".")); 
      PrintStream lower = createPrintStream(lowerFile); 
      PrintStream greater = createPrintStream(greaterFile); 
      PrintStream target = null; 
      int pivot = scanner.nextInt(); 

      // Read the file and put the values greater than in a file 
      // and the values lower than in other 
      while(scanner.hasNextInt()){ 
       int current = scanner.nextInt(); 

       if(current < pivot){ 
        target = lower; 
       } else { 
        target = greater; 
       } 
       target.printf("%d,",current); 
      } 
      // avoid dropping the pivot 
      greater.printf("%d,",pivot); 
      // close the stream before reading them again 
      scanner.close(); 
      lower.close(); 
      greater.close(); 
      // sort each part 
      fileQuickSort(lowerFile , outputFile); 
      lowerFile.delete(); 
      fileQuickSort(greaterFile , outputFile); 
      greaterFile.delete(); 

      // And you're done. 
     } else { 

      // Else , if you have enough RAM to process it 
      // 
      System.out.print("."); 
      List<Integer> smallFileIntegers = new ArrayList<Integer>(); 
      // Read it 
      while(scanner.hasNextInt()){ 
       smallFileIntegers.add(scanner.nextInt()); 
      } 
      scanner.close(); 

      // Sort them in memory 
      Collections.sort(smallFileIntegers); 

      PrintStream out = createPrintStream(outputFile); 
      for(int i : smallFileIntegers) { 
       out.printf("%d,",i); 
      } 
      out.close(); 
      // And your're done 
     } 
    } 
    private static PrintStream createPrintStream(File file) throws IOException { 
     boolean append = true; 
     return new PrintStream( new BufferedOutputStream(new FileOutputStream(file, append))); 
    } 
} 

El formato de los archivos es number,number,number,number

su formato actual es: n u m b e r , n u m b , b e r

Para corregir esto sólo hay que leer todo y saltar los espacios en blanco.

Agregue otra pregunta para eso.