排序5万个数字

Question

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

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

我不能使用标准算法

因此我问你关于方法和算法:)

好的..我读过有关并行合并的内容......但对我来说并不清楚.

解决方案,第一个版本

代码位于此处

Answer 1

5000万不是特别大.我会把它们读进记忆中.对它们进行排序并将其写出来.它应该只需几秒钟.你需要多快？你需要它是如何编译的？

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

其中一个关键因素是缓存的大小.如果数据在缓存中,则比较本身非常便宜.由于L3缓存是共享的,因此您只需要一个线程就可以充分利用它.

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

Answer 2

从头到尾,合并排序似乎是并行化和分发的最佳选择,因为它使用了分而治之的方法.有关更多信息,请进行" 并行合并排序 "和" 分布式合并排序 ".

对于单机,多核的示例,请参阅Java中的正确多线程快速排序或合并算法？.如果您可以使用Java 7 fork/join,请参阅:" Java 7:更多并发 "和" Java 7中的Fork/Join并行性 " ".

要在多台机器上分发它,请参阅Hadoop,它有一个分布式合并排序实现:请参阅MergeSort和MergeSorter.同样感兴趣的是:Hadoop在16.25小时内对Petabyte进行排序,在62秒内对TB进行排序