5

我有一个文件，它由一行组成：

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

在此表示中，空格分隔整数和逗号。这个字符串太大了，我无法用 RandomAccessFile.readLine() 读取它（几乎需要 4 Gb）。所以我创建了一个缓冲区，它可以包含 10 个整数。我的任务是对字符串中的所有整数进行排序。

能否请你帮忙？

编辑

@奥斯卡雷耶斯

我需要将一些整数序列写入文件，然后从中读取。其实我不知道，该怎么做。我是新手。所以我决定用chars来写整数，整数之间的分隔符是“，”，序列之间的分隔符是“\n\r”。所以我创建了一个可以读取它的怪物：

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;

}

如果您能建议如何做，请做=）

4

2 回答 2

15

这正是QuickSort的起源，当时没有足够的 RAM 在内存中进行排序，因此他们的程序是将部分结果存储在磁盘中。

所以你可以做的是：

  1. 选择一个支点。
  2. 按顺序读取文件并存储低于 temp_file_1 中枢轴的数据和大于或等于 temp_file_2 中枢轴的数据
  3. 重复 temp_file_1 中的过程并将结果附加到 result_file
  4. 对 temp_file_2 重复该过程并将结果附加到 result_file

当零件足够小时（比如 2 直接交换它们就足够在内存中排序了）

通过这种方式，您将能够按块排序并将部分结果存储在临时文件中，并且您将拥有一个对结果进行排序的最终文件。

编辑我告诉过你快速排序是可能的。

毕竟，您似乎需要一些额外的空间来存放临时文件。

这就是我所做的。

我创建了一个 40 mb 的文件，其中的数字用逗号分隔。

我把它命名为input：

输入 http://img200.imageshack.us/img200/5129/capturadepantalla201003t.png

输入为 40mb

在排序过程中，创建带有“大于”、“小于”值的桶的 tmp 文件，当排序完成时，这些值被发送到一个名为（猜猜看）的文件output

处理 http://img200.imageshack.us/img200/1672/capturadepantalla201003y.png

使用部分结果创建临时文件

最后，所有的 tmp 文件都被删除，结果以正确的数字序列保存在“输出”文件中：

输出 http://img203.imageshack.us/img203/5950/capturadepantalla201003w.png

最后创建文件“输出”，注意它也是 40 mb

这是完整的程序。

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

文件的格式是number,number,number,number

您当前的格式是：n u m b e r , n u m b , b e r

要解决这个问题，您只需阅读所有内容并跳过空白。

为此添加另一个问题。

于 2010-03-04T21:35:39.937 回答
1

以块的形式（每个 100 MB？）将其读取到内存中，一次一个块，对其进行排序并保存到磁盘。

然后打开所有有序块，读取每个的第一个元素，并将最低的附加到输出。然后读取刚刚读取的块的下一个元素并重复。

合并时，您可以保留从每个块中读取的最后一个 int 数组，并对其进行迭代以获得最低值。然后，您将刚刚使用的值替换为从中提取的块中的下一个元素。

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 
...
于 2010-03-04T21:30:02.197 回答