多線程快速排序或合併排序

Question

如何爲Java實現併發快速排序或合併排序算法？

我們在使用默認的Java排序算法只有一個核心（！）正在工作的16位（虛擬）核心Mac上出現了問題，而且，看到非常精細的機器完全不好充分利用。所以我們寫了自己的（我寫了它），並且確實獲得了很好的加速（我寫了一個多線程的快速排序，並且由於它的分區性質，它很好地並行化，但我也可以寫一個mergesort）多達4個線程，它是專有代碼，我寧願使用來自信譽良好的源代碼，而不是使用我重新發明的輪子。

唯一一個我在網上找到是不如何用Java編寫多線程快速排序的例子，它是忙循環（這實在太可怕了）使用：

while (helpRequested) { } 

http://broadcast.oreilly.com/2009/06/may-column-multithreaded-algor.html

因此，除了無緣無故地丟失一個線程外，它還確保通過在while循環（這是令人驚歎的）中的忙循環來殺死perfs。

因此，我的問題：你知道任何正確的多線程quicksort或Java中的合併實現將來自信譽良好的源？

我強調了一個事實，即我知道複雜性保持O（n log n），但我仍然非常喜歡看到所有這些內核開始工作而不是空閒。請注意，對於其他任務，在同一個16個虛擬核心Mac上，我通過並行化代碼（我並不是指併發專家）加速到x7。所以即使艱難的複雜性保持O（n log n），我真的很感激x7或x8甚至x16的加速。

Answer 1

給一個嘗試fork/join framework by Doug Lea：

public class MergeSort extends RecursiveAction { 
    final int[] numbers; 
    final int startPos, endPos; 
    final int[] result; 

    private void merge(MergeSort left, MergeSort right) { 
     int i=0, leftPos=0, rightPos=0, leftSize = left.size(), rightSize = right.size(); 
     while (leftPos < leftSize && rightPos < rightSize) 
      result[i++] = (left.result[leftPos] <= right.result[rightPos]) 
       ? left.result[leftPos++] 
       : right.result[rightPos++]; 
     while (leftPos < leftSize) 
      result[i++] = left.result[leftPos++]; 
     while (rightPos < rightSize) 
     result[i++] = right.result[rightPos++]; 
    } 

    public int size() { 
     return endPos-startPos; 
    } 

    protected void compute() { 
     if (size() < SEQUENTIAL_THRESHOLD) { 
      System.arraycopy(numbers, startPos, result, 0, size()); 
      Arrays.sort(result, 0, size()); 
     } else { 
      int midpoint = size()/2; 
      MergeSort left = new MergeSort(numbers, startPos, startPos+midpoint); 
      MergeSort right = new MergeSort(numbers, startPos+midpoint, endPos); 
      coInvoke(left, right); 
      merge(left, right); 
     } 
    } 
} 

（來源：http://www.ibm.com/developerworks/java/library/j-jtp03048.html?S_TACT=105AGX01&S_CMP=LP）

Answer 2

你可能沒有考慮這一點，但它可能會幫助看一下，從更高層次上的具體問題，例如，如果您不僅僅排序一個數組或列表，使用傳統算法可以更容易地同時對各個集合進行排序，而不是嘗試同時對單個集合進行排序。

Answer 3

爲什麼你認爲平行排序會有幫助？我認爲大多數排序是I/O界限，而不是處理。除非你的比較做了很多計算，否則加速是不太可能的。

Answer 4

對不起，但你要求的是不可能的。我相信別人提到排序是IO界限，他們很可能是正確的。來自IBM的Doug Lea的代碼是一件很好的工作，但我相信它主要是作爲如何編寫代碼的一個例子。如果你在他的文章中注意到，他從未發佈過基準，而是發佈了其他工作代碼的基準，例如計算平均值和並行尋找最小最大值。如果您使用通用合併排序，快速排序，使用加入分叉池的雙合併排序，以及使用快速排序加入分叉池編寫的基準，以下是測試的基準。你會看到合併排序對於100或更小的N是最好的。快速排序1000到10000，如果你有100000和更高的分數，使用加入分叉池的快速排序比其他的快。這些測試是運行30次的隨機數組的陣列，爲每個數據點創建一個平均值，並且運行在具有大約2個RAM的四核上。在下面我有快速排序的代碼。這大多表明，除非你試圖對一個非常大的數組進行排序，否則你應該退出嘗試改進你的代碼排序算法，因爲並行的在小N上運行速度非常慢。

Merge Sort 
10 7.51E-06 
100 1.34E-04 
1000 0.003286269 
10000 0.023988694 
100000 0.022994328 
1000000 0.329776132 


Quick Sort 
5.13E-05 
1.60E-04 
7.20E-04 
9.61E-04 
0.01949271 
0.32528383 


Merge TP 
1.87E-04 
6.41E-04 
0.003704411 
0.014830678 
0.019474009 
0.19581768 

Quick TP 
2.28E-04 
4.40E-04 
0.002716065 
0.003115251 
0.014046681 
0.157845389 

import jsr166y.ForkJoinPool; 
import jsr166y.RecursiveAction; 

// derived from 
// http://www.cs.princeton.edu/introcs/42sort/QuickSort.java.html 
// Copyright © 2007, Robert Sedgewick and Kevin Wayne. 
// Modified for Join Fork by me hastily. 
public class QuickSort { 

    Comparable array[]; 
    static int limiter = 10000; 

    public QuickSort(Comparable array[]) { 
     this.array = array; 
    } 

    public void sort(ForkJoinPool pool) { 
     RecursiveAction start = new Partition(0, array.length - 1);   
     pool.invoke(start); 
    } 

    class Partition extends RecursiveAction { 

     int left; 
     int right; 

     Partition(int left, int right) { 
      this.left = left; 
      this.right = right; 
     } 

     public int size() { 
      return right - left; 
     } 

     @SuppressWarnings("empty-statement") 
     //void partitionTask(int left, int right) { 
     protected void compute() { 
      int i = left, j = right; 
      Comparable tmp; 
      Comparable pivot = array[(left + right)/2]; 

      while (i <= j) { 
       while (array[i].compareTo(pivot) < 0) { 
        i++; 
       } 
       while (array[j].compareTo(pivot) > 0) { 
        j--; 
       } 

       if (i <= j) { 
        tmp = array[i]; 
        array[i] = array[j]; 
        array[j] = tmp; 
        i++; 
        j--; 
       } 
      } 


      Partition leftTask = null; 
      Partition rightTask = null; 

      if (left < i - 1) { 
       leftTask = new Partition(left, i - 1); 
      } 
      if (i < right) { 
       rightTask = new Partition(i, right); 
      } 

      if (size() > limiter) { 
       if (leftTask != null && rightTask != null) { 
        invokeAll(leftTask, rightTask); 
       } else if (leftTask != null) { 
        invokeAll(leftTask); 
       } else if (rightTask != null) { 
        invokeAll(rightTask); 
       } 
      }else{ 
       if (leftTask != null) { 
        leftTask.compute(); 
       } 
       if (rightTask != null) { 
        rightTask.compute(); 
       } 
      } 
     } 
    } 
} 

Answer 5

我最近幾天一直在面對多線程排序問題。正如on this caltech slide所解釋的那樣，只需簡單地多線程處理線程明顯數量（分割數）上的分割和征服方法的每一步就能做到最好。我想這是因爲雖然你可以在你的機器的所有64個內核的64個線程上運行64個分區，但這4個分區只能運行在4個線程，2個2和1個1等等上，所以對於很多級別遞歸的機器未被充分利用。

昨晚我發現了一個解決方案，可能對我自己的工作很有用，所以我會在這裏發佈。

因此，你的排序函數的第一個標準是基於最大尺寸s的整數，可以是一個實際的整數或字符串中的字符，例如這個整數或字符完全定義了排序的最高級別，那麼我認爲有一個非常快速（和簡單）的解決方案。只需使用該初始整數將排序問題分爲較小的排序問題，然後使用您選擇的標準單線程排序算法對其進行排序。我認爲，可以一次性完成對各個班級的劃分。在完成獨立排序之後沒有合併問題，因爲您已經知道第1課中的所有內容都在第2課之前排序，依此類推。

示例：如果您希望根據strcmp（）進行排序，則使用字符串中的第一個字符將數據分爲256個類，然後在下一個可用線程中對每個類進行排序，直到完成全部任務。

這種方法充分利用了所有可用的內核，直到問題解決，我認爲它很容易實現。儘管如此，我還沒有實現它，所以可能存在我還沒有找到的問題。它顯然不適用於浮點類型，並且對於大型s來說效率不高。它的性能也將嚴重依賴於用於定義類的整數/字符的熵。

這可能是Fabian Steeg用較少的話來建議的，但我明確表示在某些情況下可以從更大的排序中創建多個更小的排序。

Answer 6

剛剛編碼了上面的MergeSort和性能非常差。

代碼塊引用「coInvoke（left，right）;」但沒有提及這個，並用invokeAll（左，右）替換它;

測試代碼：

MergeSort mysort = new MyMergeSort(array,0,array.length); 
ForkJoinPool threadPool = new ForkJoinPool(); 
threadPool.invoke(mysort); 

但不得不停止它因表現不佳。

我看到上面的文章已經快一年了，也許事情現在已經改變了。

我發現替代本文中的代碼的工作：http://blog.quibb.org/2010/03/jsr-166-the-java-forkjoin-framework/

Answer 7

爪哇8提供java.util.Arrays.parallelSort，其使用fork-join框架並行排序陣列。該文件提供了有關當前執行的一些細節（但這些都是不規範票據）：

的排序算法是並行排序合併，打破了陣列分爲子陣列本身是排序，然後合併。當子數組長度達到最小粒度時，使用適當的Arrays.sort方法對子數組進行排序。如果指定數組的長度小於最小粒度，則使用適當的Arrays.sort方法對其進行排序。該算法需要一個不大於原始數組大小的工作空間。 ForkJoin公共池用於執行任何並行任務。

似乎沒有成爲列表（即使RandomAccess列表應該玩排序不錯）相應的並行排序方法，所以你需要使用toArray，那種陣列，並將結果返回到列表。 （我已經問了一個關於這個問題here。）