java - 排序 50 000 000 个数字

Question

假设我们需要对 50 000 000 个数字进行排序。假设这些数字存储在一个文件中。解决这个问题最有效的算法是什么？排序的并行算法...

怎么做？也许有用的链接)

我不会用标准算法

所以我问你方法和算法:)

好的..我读到了关于并行归并排序的内容...但我并不清楚。

解决方案，第一个版本

code is located here

Answer 1

5000万不算特别多。我只是将它们读入内存。将它们分类并写出来。它应该只需要几秒钟。你需要多快？您需要它有多复杂？

在我的旧 labtop 上花了 28 秒。如果我有更多的处理器，它可能会快一点，但大部分时间都花在读取和写入文件上(15 秒)，这不会更快。

其中一个关键因素是缓存的大小。如果数据在缓存中，比较本身就非常便宜。由于三级缓存是共享的，一个线程就可以充分利用它。

public static void main(String...args) throws IOException {
    generateFile();

    long start = System.currentTimeMillis();
    int[] nums = readFile("numbers.bin");
    Arrays.sort(nums);
    writeFile("numbers2.bin", nums);
    long time = System.currentTimeMillis() - start;
    System.out.println("Took "+time+" secs to sort "+nums.length+" numbers.");
}

private static void generateFile() throws IOException {
    Random rand = new Random();
    int[] ints = new int[50*1000*1000];
    for(int i= 0;i<ints.length;i++)
        ints[i] = rand.nextInt();
    writeFile("numbers.bin", ints);
}

private static int[] readFile(String filename) throws IOException {
    DataInputStream dis = new DataInputStream(new BufferedInputStream(new FileInputStream(filename), 64*1024));
    int len = dis.readInt();
    int[] ints = new int[len];
    for(int i=0;i<len;i++)
        ints[i] = dis.readInt();
    return ints;
}

private static void writeFile(String name, int[] numbers) throws IOException {
    DataOutputStream dos = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(name), 64*1024));
    dos.writeInt(numbers.length);
    for (int number : numbers)
        dos.writeInt(number);
    dos.close();
}