ordinamento di un file enorme in Java

Question

Ho un file, che consiste in un una riga:

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

In questa rappresentazione, gli spazi separare gli interi e le virgole. Questa stringa è così grande che non riesco a leggerla con RandomAccessFile.readLine() (quasi 4 Gb necessari). In modo che ho creato un buffer, che può contenere 10 numeri interi. Il mio compito è quello di ordinare tutti gli interi nella stringa.

Potresti, per favore, aiutare?

EDIT

@Oscar Reyes

ho bisogno di scrivere alcune sequenze di numeri interi in un file e poi leggere da esso. In realtà non lo so, come farlo. Sono un principiante. Così ho deciso di usare i caratteri per scrivere numeri interi, i delimitatori tra interi sono "," e i delimitatori tra le sequenze sono "\ n \ r" che. In modo che ho creato un mostro che lo legge:

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; 

} 

Se potessi consigliare come farlo, si prega di farlo =)

Answer 1

Leggila alla memoria in blocchi (100 MB ciascuna), un pezzo? alla volta, ordinarlo e salvarlo sul disco.

Quindi aprire tutti i blocchi ordinati, leggere il primo elemento di ciascuno e aggiungere il più basso all'output. Poi leggi il prossimo elemento del pezzo che hai appena letto e ripeti.

Durante l'unione è possibile mantenere una matrice dell'ultima lettura int da ciascun blocco e solo scorrere su di essa per ottenere il valore più basso. Quindi sostituisci il valore che hai appena usato con il prossimo elemento nel pezzo da cui è stato preso.

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

Questo è esattamente l'origine QuickSort allora non c'era abbastanza RAM per ordinare in memoria in modo da procedura è quello di memorizzare i risultati parziali in disco.

Che cosa si può fare è:

1. Scegli un perno.
2. Leggere di seguito in basso i dati di file e memorizzare di pivot in temp_file_1 e dati più grandi o uguali al pivot in temp_file_2
3. Ripetere la procedura in temp_file_1 e aggiungere il risultato al result_file
4. Ripetere la procedura per temp_file_2 e aggiungere il risultato result_file

Quando le parti sono abbastanza piccoli ( come 2 appena li scambio diretto abbastanza per essere ordinata in memoria)

in questo modo sarete in grado di risolvere in blocchi e memorizzare i risultati parziali nei file temporanei e avrai un file finale con il risultato ordinato.

EDIT Ti ho detto che un ordinamento rapido era possibile.

Sembra che, dopo tutto, sarà necessario dello spazio aggiuntivo per i file temporanei.

Ecco cosa ho fatto.

Creo un file da 40 mb con numeri separati da virgole.

ho name it input:

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

_{ingresso è 40mb}

durante l'ordinamento, i file tmp con i secchi di "maggiore di", "inferiore" si creano valori e quando l'ordinamento è finito, i valori vengono inviati a un file chiamato (indovinate cosa) output

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

_{file temporanei vengono creati con i risultati parziali}

Infine tutti i file tmp sono soppressi e il risultato viene mantenuto nel file "output" con la corretta sequenza ordinata di numeri:

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

_{Infine viene creato il file "output", nota che è di 40 mb anche}

Ecco il progr completo Sono.

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

Il formato dei file è number,number,number,number

vostro formato corrente è: n u m b e r , n u m b , b e r

Per risolvere che basta leggere tutto e saltare gli spazi vuoti.

Aggiungi un'altra domanda.