Sortowanie ogromny plik w Javie

Question

Mam plik, który składa się z jednego rzędu:

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

W tej reprezentacji, obowiązuje całkowite oddzielenie i przecinki. Ten ciąg jest tak duży, że nie mogę go odczytać za pomocą funkcji RandomAccessFile.readLine() (wymagane prawie 4 GB). Tak więc stworzyłem bufor, który może zawierać 10 liczb całkowitych. Moim zadaniem jest posortowanie wszystkich liczb całkowitych w ciągu znaków.

Czy mógłbyś, proszę, pomóc?

EDIT

@Oscar Reyes

muszę napisać kilka sekwencje liczb do pliku, a następnie odczytać z niego. Właściwie to nie wiem, jak to zrobić. Jestem nowicjuszem. Postanowiłem więc użyć znaków do zapisania liczb całkowitych, ograniczniki między liczbami całkowitymi to ",", a delimetry między sekwencjami to "\ n \ r", które. Tak, że stworzył potwora, który brzmi ona:

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; 

} 

Jeśli mógłbyś doradzić jak to zrobić, zrób to =)

Answer 1

przeczytał go do pamięci w kawałkach (100 MB każdy), jeden kawałek? naraz, posortuj go i zapisz na dysku.

Następnie otwórz wszystkie zamówione kawałki, przeczytaj pierwszy element każdego z nich i dodaj najniższy wynik. Następnie przeczytaj następny element porcji, którą właśnie przeczytałeś i powtórz.

Podczas scalania możesz zachować tablicę ostatnich int przeczytanych z każdej porcji i po prostu iterować po niej, aby uzyskać najniższą. Następnie zastępujesz użytą wartość następnym elementem w kawałku, z którego została pobrana.

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

To jest dokładnie pochodzenie QuickSort wtedy nie było wystarczająco dużo pamięci RAM do sortowania w pamięci więc procedura jest przechowywanie cząstkowe wyniki w dysku.

Więc co można zrobić, to:

1. Wybierz pivot.
2. Czytaj kolejno dane plików i zapisywanie niższy niż pivot w temp_file_1 i danych większych lub równych przegubu w temp_file_2
3. powtórzyć procedurę temp_file_1 i dołącz wynik result_file
4. powtórzyć procedurę dla temp_file_2 i dołączyć wynik do result_file

Gdy części są na tyle małe ( jak 2 tylko bezpośrednia zamiana ich wystarczy być klasyfikowane w pamięci)

ten sposób będziesz móc sortować w porcje i przechowują częściowe wyniki w plikach tymczasowych, a otrzymasz końcowy plik z wynikiem posortowanym.

EDIT Powiedziałem ci, że szybki sposób jest możliwy.

Wygląda na to, że potrzebujesz więcej miejsca na pliki tymczasowe.

Oto co zrobiłem.

Tworzę plik 40 mb z liczbami oddzielonymi przecinkami.

nazwać go input:

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

_{Wejście jest 40MB}

Podczas sortowania, TMP pliki z wiadra "większe niż", "mniejsze niż" wartości są tworzone a po zakończeniu sortowania wartości są wysyłane do pliku o nazwie (zgadnij co) output

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

_{pliki tymczasowe są tworzone z cząstkowych wyników}

Wreszcie wszyscy TMP pliki są usuwane, a wynik jest przechowywany w pliku „wyjściu” z poprawnym posortowanych sekwencji liczb:

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

_{końcu tworzony jest plik „wyjście”, zauważył to 40 MB też}

Oto pełna progr rano.

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

Format plików jest number,number,number,number

Twój obecny format: n u m b e r , n u m b , b e r

Aby ustalić, że po prostu trzeba to wszystko przeczytać i pominąć półwyrobów.

Dodaj kolejne pytanie.