Java外部排序效率

Question

我必须在 java 中编写一个外部排序程序，给定一个包含任意数量整数的文件 A，仅使用文件 B(大小相同)作为临时存储对它们进行排序。在第一阶段，我将文件 block 读入 ram，使用内置的 java 排序并写回文件 B，但事实证明这非常慢。我想知道我的代码中是否存在明显的低效率？请注意，input1 和 output 是 RandomAccessFile Objcets，BUFFER_SIZE 是在运行时由可用内存量决定的 block 大小。

public void SortBlocks() throws IOException{
    int startTime = (int) System.currentTimeMillis();
    input1.seek(0);output.seek(0);
    DataInputStream in = new DataInputStream(new BufferedInputStream(new FileInputStream(input1.getFD()),2048));
    DataOutputStream out = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(output.getFD()),2048));
    int[] buffer = new int[BUFFER_SIZE];
    int j=0;
    for(int i=0; i<input1.length();i+=4){
        buffer[j] = in.readInt();
        j++;
        if(j == BUFFER_SIZE){
            writeInts(buffer,out,j);
            j=0;
        }
    }
    writeInts(buffer,out,j);
    out.flush();
    SwitchIO();
    int endTime = (int) System.currentTimeMillis();
    System.out.println("sorted blocks in " + Integer.toString(endTime-startTime));
}

    private static void writeInts(int[] Ints, DataOutputStream out, int size) throws IOException{
    Arrays.sort(Ints,0,size);
    for(int i=0;i<size;i++){
        out.writeInt(Ints[i]);
    }
}

提前感谢您的反馈。

Answer 1

最明显的低效是使用 input1.length()，这是一个相对昂贵的操作，您要在每个 int 值上调用它。

我不明白为什么在默认 (8192) 会更有效时减小缓冲区大小。

如果您正在读取文件，我会使用 ByteBuffer 作为 IntBuffer。瓶颈可能是您读取和写入数据的方式。按 native 顺序使用 int 值将提高翻译性能。 (而不是默认哪个big endian)

如果您将文件作为内存映射文件进行访问，您可能能够优雅地处理大于内存大小的文件。