排序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