Sắp xếp một tập tin rất lớn trong Java

Question

Tôi có một tập tin, trong đó bao gồm một hàng:

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

Trong đại diện này, không gian tách các số nguyên và dấu phẩy. Chuỗi này quá lớn đến nỗi tôi không thể đọc nó với RandomAccessFile.readLine() (gần 4 Gb cần thiết). Vì vậy mà tôi tạo ra một bộ đệm, có thể chứa 10 số nguyên. Nhiệm vụ của tôi là sắp xếp tất cả các số nguyên trong chuỗi.

Bạn có thể, vui lòng trợ giúp?

EDIT

@ Oscar Reyes

tôi cần phải viết một số chuỗi các số nguyên vào một tập tin và sau đó đọc từ nó. Thực ra tôi không biết, làm thế nào để làm điều đó. Tôi là một người mới. Vì vậy, tôi quyết định sử dụng ký tự để viết số nguyên, dấu phân cách giữa các số nguyên là "," và dấu phân cách giữa các chuỗi là "\ n \ r". Vì vậy mà tôi tạo ra một con quái vật mà đọc nó:

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; 

} 

Nếu bạn có thể tư vấn cho làm thế nào để làm điều đó, xin vui lòng làm điều đó =)

Answer 1

đọc nó vào bộ nhớ trong khối (100 MB mỗi), một đoạn? tại một thời điểm, sắp xếp nó và lưu vào đĩa.

Sau đó mở tất cả các khối đã đặt hàng, đọc phần tử đầu tiên của mỗi phần và thêm phần thấp nhất vào đầu ra. Sau đó đọc phần tử tiếp theo của đoạn bạn vừa đọc và lặp lại.

Khi hợp nhất, bạn có thể giữ một mảng nội dung cuối cùng được đọc từ mỗi đoạn và chỉ cần lặp lại nó để có giá trị thấp nhất. Sau đó, bạn thay thế giá trị bạn vừa sử dụng với phần tử tiếp theo trong đoạn dữ liệu mà nó được lấy từ đó.

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

Đây chính xác là nguồn gốc QuickSort sau đó không đủ RAM để sắp xếp trong bộ nhớ để chúng lưu trữ một phần kết quả trong đĩa.

Vì vậy, những gì bạn có thể làm là:

1. Chọn một trục.
2. đọc tuần tự tập tin và lưu trữ dữ liệu của bạn thấp hơn so với trục trong temp_file_1 và dữ liệu lớn hơn hoặc bằng với trục trong temp_file_2
3. Lặp lại các thủ tục trong temp_file_1 và thêm kết quả để result_file
4. Lặp lại thủ tục temp_file_2 và gắn kết quả để result_file

Khi phần đủ nhỏ ( như 2 chỉ trực tiếp trao đổi chúng đủ để được sắp xếp trong bộ nhớ)

Bằng cách này bạn sẽ có thể sắp xếp trong khối và lưu trữ một phần kết quả trong các tập tin tạm thời và bạn sẽ có một tập tin cuối cùng với kết quả được sắp xếp.

EDIT Tôi đã nói với bạn rằng sắp xếp nhanh là có thể.

Dường như bạn sẽ cần thêm một chút dung lượng cho các tệp tạm thời.

Đây là những gì tôi đã làm.

Tôi tạo tệp 40 mb với các số được phân tách bằng dấu phẩy.

tôi đặt tên cho nó input:

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

_{Input là 40MB}

Trong sắp xếp, các file tmp với xô "lớn hơn", "thấp hơn" giá trị được tạo ra và khi các loại kết thúc, các giá trị được gửi đến một tập tin gọi là (đoán những gì) output

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

_{file Temp được tạo ra với kết quả phần}

Cuối cùng tất cả các file tmp được xóa và kết quả được lưu trong hồ sơ "đầu ra" với dãy được sắp xếp đúng các số:

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

_{Cuối cùng các tập tin "đầu ra" được tạo ra, hãy chú ý đó là 40 mb quá}

Dưới đây là toàn bộ progr là.

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

Định dạng của file là number,number,number,number

định dạng hiện tại của bạn là: n u m b e r , n u m b , b e r

Để khắc phục điều đó bạn chỉ cần phải đọc tất cả và bỏ qua những khoảng trống.

Thêm một câu hỏi khác cho điều đó.