排序50 000 000个数字

Question

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

如何做到这一点？也许有用链接）

我不能使用标准算法

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

行..我读到并行归并......但它并不清楚我。

解决方案，第一个版本

code is located here

Answer 1

从我的头顶，merge sort似乎是最好的选择，当谈到并行化和分布，因为它使用分而-conquer的方法。欲了解更多信息，谷歌为“并行合并排序”和“分布式合并排序”。

对于单机，多核示例，参见参见Correctly multithreaded quicksort or mergesort algo in Java?。如果您可以使用Java 7 fork/join，请参阅：“Java 7: more concurrency”和“Parallelism with Fork/Join in Java 7”。

对于在许多机器分配它，看到Hadoop，它具有分布式合并排序的实现：看MergeSort和MergeSorter。也感兴趣：Hadoop Sorts a Petabyte in 16.25 Hours and a Terabyte in 62 Seconds

Answer 2

比许多元素排序，你最好的拍摄是Merge Sort。它通常是数据库使用的算法。尽管速度不如Quick Sort，但它使用中间存储器，因此不需要大量内存来执行排序。

此外，正如sje397和Scott在评论中指出的，Merge Sort具有高度的可并行性。

Answer 3

这取决于很多问题领域。例如，如果所有数字都是正整数，最好的办法可能是创建一个0-MAX_INT数组，然后在读取文件时计算每个数字出现的次数，然后用非零值打印出每个整数，无论多少次发生，零计数。这是一个O（n）“排序”。有这样的官方名称，但我忘记它是什么。

顺便说一句，我在Google面试中被问到了这个问题。从问题的限制我想出了这个解决方案，这似乎是他们正在寻找的答案。 （我拒绝了这份工作，因为我不想动。）

Answer 4

他们不是很多。如果它们是10个字节长的扩展例如它将是一个500M字节的数组，它几乎可以留在我的手机上！ ;） 所以我会说，如果只是这样的话，那就去换Quicksort吧。

Answer 5

5000万不是特别大。我只是把它们读入内存。对它们进行排序并写出来。它应该只需要几秒钟。你需要多快？你需要它是如何完成的？

在我的旧labtop上花了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 6

不要怕大数目。实际上，5亿个数字并不是那么大。所以如果数字是整数，那么每个数字的大小是4字节，因此需要为这个数组分配的整个存储空间是5 000 000 * 4/1024/1024 = 190.7兆字节，相对较小。数学完成后，您可以继续执行以O（nLogn）运行的QuickSort。注意.net数组中的内置排序方法使用QuickSort，即时通讯不知道这是否也是在Java中的情况。

整理我的机器上250个000 000整数花了约2分钟，所以要为它:)

Answer 7

50e6是很少的今天，不要让事情复杂得多，他们需要的是...

bash$ sort <file> sorted.file