黃志波，趙晴，孫少乙
　　（華北計算機系統工程研究所，北京 100083）

        摘要：為實現多線程快速排序，提出基于Fork／Join框架的多線程快速排序，同時對排序算法進行優化。該算法主要用于大量數據需要進行排序處理的應用。
　　關鍵詞：Fork/Join；多線程；快速排序；算法優化　　

0引言
　　排序一直是程序開發中的一個重點，尤其在一些應用開發中經常用到，在搜索開發中也是重點研究對象。所以人們對排序的研究一直堅持不懈。在眾多排序算法中，快速排序是一個表現極其優秀的算法。該算法于1962年由Tony Hoare首次提出［1］，它基于分治思想，使得排序性能得到極大的提升［2］。如今的電腦或者手機一般都是多核處理器，為了提高用戶體驗，應該充分利用其所擁有的硬件設備。本文主要講述多線程下快速排序的設計與優化過程，對普通快速排序［3］、基于多線程的快速排序以及基于Fork／Join的多線程排序進行了比較。
1單線程快速排序
　　快速排序是基于比較的一種排序算法，而基于比較的排序算法的最佳性能為O（nlgn）。快速排序的運行時間與數據劃分是否對稱有關，且與選擇了哪一個元素作為劃分基準有關［4］。在信息論里面，N個未排序的數字，共有N！種排法，但是只有一種是想要的（譬如遞增或者遞減）。也就是說，排序問題的可能性有N！種，而任何基于比較的排序基本操作單元都是“比較a和b”，而這個比較一般是有兩個結果，這樣恰好可將剩下來的排序減少為N!/2種。因此當選定某個位置的元素作為pivot（基準）時，若能恰好將原序列平均分為兩個子序列，那么遞歸的次數將會顯著地減少，從而排序的效率將有所提高。因此均衡地分割序列一直是一個重點研究方向，如隨機選取基準、三數選中等策略。此外還有兩種情況是研究排序算法時必須考慮的［5］，第一種情況就是當序列中大部分數據甚至全部數據相等，也就是大量數據重復時；第二種情況是當序列中大部分數據甚至整個序列已經是有序的［6］。這兩種情況都會使得快速排序的性能變得最壞，也就是O（n2）。針對第一種情況研究者們已經提出了三分序列的解決方案；第二種情況就是如何恰當地選取比較基準，固定地選取首部或者尾部元素作為基準顯然不是最佳的，人們提出了隨機選取元素與三數選中兩種方法加以改進。本文中分別采用隨機選取元素和以尾端數據作為基準來實現的算法，目的是使算法設計更簡練，其次是為了使單線程與多線程在核心算法上保持一致性。由于快速排序算法核心算法是一致的，故只在本節展開描述，接下來的章節中就不贅述了。
　　快速排序偽代碼［6］如下。
　　QuickSort(a, l, r)
　　if l<r
　　then k ← Partition(a,l,r)
　　QuickSort(a, l, k-1)
　　QuickSort(a, k+1, r)
　　其中Partition函數是核心函數，在測試時根據測試數據類型的不同采用相應的最優實現算法。
　　針對有序數據Partition函數代碼設計如下:
　　int index =new Random().nextInt(right
　　-left)+left;
　　swap(arr［left］ , arr［index］);
　　long pivot = arr［left］;
　　while (left < right) {
　　while (left < right && arr［right］ >= pivot) right--;
　　if (left < right) arr［left++］ = arr［right］;
　　while (left < right && arr［left］ <= pivot) left++;
　　if (left < right) arr［right--］= arr［left］;
　　}
　　arr［left］ = pivot;
　　return left;
　　針對隨機數據和重復數據Partition函數設計如下:
　　long x = arr［right］;
　　int i = left - 1;
　　for (int j = left; j < right; j++) {
　　if (arr［j］ <= x) {
　　i++;
　　swap(arr, i, j);}}
　　swap(arr, i + 1, right);
　　return i + 1;
　　為了防止因為數字比較大，超出int類型最大值，均用long類型，該類型基本上完全適用于實際應用當中。
2多線程快速排序
　　由于快速排序是采用分治策略，并且基準左右序列的遞歸排序是互不影響的，因此完全可以考慮采用多線程來做并行處理，每次基于基準產生左右分塊序列的時候，可以分別用一條線程來執行左右序列的排序工作，這樣能在充分利用計算機性能的條件下，使排序算法表現更優，從而增大排序速度。一種實現是將需要排序的數組分成多組，然后對每組實現一個線程來快速排序，最后用歸并排序算法的思想合并這些數組，最終實現原序列的排序過程。這種實現方式在合并時需要額外時間，并且還需要額外的空間進行交換。因為快速排序是內排序，因此各自子序列排好序后，原序列就已經是排好序的了。在多線程里面進行排序，線程的建立以及切換調用才是需要考慮的問題［78］。因為電腦資源畢竟有限，不能無限地創建線程。在Java中主要是用runnable和callable接口來實現多線程，區別在于是否有返回值。而快速排序是內排序，可以不用返回值，這樣可以使得程序更加清晰明了。故此，通過實現runnable接口來創建線程。為了能最大化測試機器的性能，采用線程池來管理線程。
　　線程之間切換也是極為耗時間的，因此常常需要根據當前機器的處理器數目來創建線程數。獲取測試機器的cpu數目：
　　private static final int N=Runtime.getRuntime().availableProcessors();
　　執行排序線程的線程池：
　　private static Executor pool= Executors. newFixedThreadPool(N);
　　為了防止競爭條件的產生，隊列中的線程是有順序的，必須是某些線程執行完后等待在隊列中的剩余線程才能繼續進行，這也是結合算法來設計的。由此可以看到此方案存在不足之處，即線程之間存在鎖，而鎖會極大地影響多線程的性能。
　　下面是排序時首先調用的方法,參數count記錄當前正在執行的線程數，因為在Java中++i和i++(--操作同理)操作不是線程安全的，在使用的時候需要加synchronized關鍵字。這里采用AtomicInteger線程安全接口來實現加減操作。
　　public static void sortFunction(long［］ arr) {
　　final AtomicInteger count = new AtomicInteger(1);
　　pool.execute(new QuicksortRunnable(input,0,arr.length-1, count));
　　try {synchronized (count) {
　　count.wait();}
　　} catch (InterruptedException e) {
　　e.printStackTrace();}}
　　實現runnable接口時，必須重寫run方法。
　　@Override
　　public void run() {
　　quicksort(left, right);
　　synchronized (count) {
　　if (count.getAndDecrement() == 1)
　　count.notify();}}
　　這是真正進行排序的方法，當隊列中還有尚未執行的任務時，就繼續遞歸調用該方法。
　　private void quicksort(int pLeft, int pRight) {
　　if (pLeft < pRight) {
　　int storeIndex=partition(pLeft, pRight);
　　if(count.get()>=FALLBACK*N{
　　quicksort(pLeft, storeIndex - 1);
　　quicksort(storeIndex+1, pRight);}
　　else {count.getAndAdd(2);
　　pool.execute(new QuicksortRunnable(
　　values,pLeft,storeIndex-1, count));
　　pool.execute(new QuicksortRunnable(
　　values,storeIndex+1,pRight, count));
　　}}}
　　當創建的線程到一個特定的閾值時，即執行回滾，繼續遞歸地創建線程，以避免恒定的上下文切換的開銷。
3基于Fork/Join框架多線程快速排序
　　Fork/Join框架是Java7提供的一個用于并行執行任務的框架，即把大任務分割成若干個小任務，最終匯總每個小任務的結果后得到之前大任務的結果。其中Fork用來做分割任務操作，而Join則是將分割后的小任務執行結果進行合并的操作。該框架之所以能在多線程編程表現優異，是因為它基于一個叫作Workstealing的核心算法。該算法是指線程從其他線程隊列里獲取任務來執行。也就是說當需要做一個比較大的任務時，可以把這個任務分割為若干互不依賴的子任務。為了減少線程間的競爭，把這些子任務分別放到不同的隊列里，并為每個隊列創建一個單獨的線程來執行隊列里的任務，這樣就實現了線程和隊列一一對應。比如某線程T負責處理T隊列里的任務，但是有的線程先執行完了自己隊列里的任務，而其他線程對應的隊列里還有任務在等待處理。與其讓已經執行完隊列中任務的線程等著，不如讓它去幫其他線程執行任務，于是它就去其他線程的隊列里竊取一個任務來執行。但是這當中其實也存在一個問題，就是當它與被竊取任務的線程同時訪問同一個隊列時，仍會有竊取任務線程與被竊取任務線程之間的競爭，為了減少這種現象的出現，通常會使用雙端隊列，被竊取任務線程永遠從雙端隊列的頭部拿任務執行，而竊取任務的線程永遠從雙端隊列的尾部拿任務執行。
　　Work-stealing算法的優點是充分利用線程進行并行計算，并減少了線程間的競爭，其缺點是在某些情況下還是存在競爭，比如雙端隊列里只有一個任務時，并且消耗了更多的系統資源，比如創建多個線程和多個雙端隊列。
　　Fork/Join框架工作步驟如下：
　　（1）分割任務。首先需要有一個fork類來把大任務分割成子任務，當子任務還是很大時，就需要不停地分割，直到分割出的子任務足夠小［9］。在算法實現時以數據量大小為依據來分割任務。
　　（2）執行任務并合并結果。被分割的子任務分別放在雙端隊列里，啟動后的線程分別從雙端隊列里獲取任務執行。在同一個進程中的線程可以共享數據，各子任務執行完的結果都統一放在一個隊列里，啟動一個線程從隊列里拿數據，然后合并這些數據。但是在快速排序時，因為它是內排序，所以可以不用進行最后的數據合并過程，實際上，原序列排序后就是所要的結果。如此一來，只要專注于分割任務和排序就行了。
　　當創建一個ForkJoin任務時，通常情況下不需要直接繼承ForkJoinTask類，而只需要繼承它的子類，Fork/Join框架提供了兩個子類：RecursiveAction：沒有返回結果的任務；RecursiveTask：有返回結果的任務。
　　因為不需要任務有返回結果，因此采用子類RecursiveAction。ForkJoinTask需要通過ForkJoinPool來執行，主任務被分割出的子任務會添加到當前工作線程所維護的雙端隊列中，進入隊列的頭部。當某個工作線程的隊列里暫時沒有任務可執行時，它就會隨機地從其他工作線程所維護的隊列的尾部獲取一個任務。
　　需要設定子任務分割限制條件，即數據量的大小，這里將其設定為286，因為這個數字是快速排序最佳實現的閾值，可以參考JDK源碼。
　　private int THRESHOLD = 286;
　　ForkJoinTask需要實現compute方法，在該方法中首先需要判斷當前任務是否足夠小，如果足夠小就直接執行任務，即調用排序方法排序，否則就需要分割成兩個子任務，通過invokeAll方法將兩個子任務分別進行fork，被fork后的子任務會再次調用compute方法，檢查當前子任務是否需要繼續分割成孫任務，倘若不需要繼續分割，則執行當前子任務。compute方法代碼如下：
　　protected void compute() {
　　if (hi - lo < THRESHOLD)
　　sequentiallySort(array,lo, hi);
　　else {
　　int pivot = partition(array, lo, hi);
　　FastSort left=new FastSort(array,
　　lo, pivot-1);
　　FastSort right=new FastSort(
　　array,pivot+1, hi);
　　invokeAll(left, right);}}
4測試
　　為了更直觀以及更全面地進行比較，測試時生成了三組數據，均為1 000萬個，但分別為隨機的生成不同數字，大量重復數字以及有序數字。同時為了使測試順利進行，算法會稍作調整。當數據為隨機數據和重復數據時，partition方法以尾端數字作為基準排序；當數據為有序數據時，采用隨機獲取基準來進行排序。此外由于數據量比較大，故保存在txt文本文檔里。排序完成后寫到新建文檔里，可便于檢查排序是否正確以及是否完整。本測試只比較排序時間。因為文檔的讀寫不是本文討論的問題，所以就不展開敘述了。測試機器為MacBook Pro841，CPU數目為4，運行內存為16 GB。測試過程中為了使結果更具有一般性，采用多次測試取平均值。測試數據如表1所示。

　　上表數據顯示，對于隨機數據，由于數據分布均勻，多線程顯然比單線程排序更快速。同時對于重復數據，由于數據中有大量重復數字，因此遞歸次數顯著地增加了，也就是數據交換次數也增加了，排序所需時間也成倍遞增了，但是因為數據中存在大量重復數字，因此有些數字交換顯然是多余的［10］。因為普通多線程排序的線程是由線程池控制的，而Fork/Join多線程設計是由數據量進行線程控制，所以相比較來看普通多線程排序表現更加出色。對于有序數據，因為數據本身是有序的，采用單線程排序時，遞歸次數大幅增加而導致堆棧溢出。多線程排序時，Fork/Join多線程明顯優異于普通多線程，這跟什么時候進行真正排序相關，普通排序過早地進行排序因而比較次數以及交換次數要多于Fork/Join多線程排序。綜上所述，在設計多線程排序時，建議基于Fork/Join框架思想來實現。　　

5結論
　　本文總結了單線程下快速排序不斷優化的歷程，并設計了多線程下排序的優化方法。從實驗測試結果看出，隨著時代的進步，機器不斷更替，重新思考以前一些算法問題時有了另一層面的思維方式，往往在新的思維方式下會取得不一樣的成就［11］。排序問題一直是研究的熱點，而快速又更是備受關注［12］。此外關于多線程還有一種處理方案就是基于actor模型的多線程框架，這也是一種多線程處理策略。在實驗中也嘗試過，不過并未取得理想效果，因此就不展開敘述了，若讀者有興趣，可以試著去實現并優化算法。
　　參考文獻
　　［1］ CORMEN T H, LEISERSON C E, RIVEST R L, et al.算法導論原書(第二版)［M］.北京：高等教育出版社，2006.
　　［2］ HOARE C A R. Quicksort［J］. The Computer Journal, 1962(5):1015.
　　［3］ 胡云.幾種快速排序算法實現的比較［J］.安慶師范學院學報,2008,14(3):100103.
　　［4］ 霍紅衛,許進.快速排序算法研究［J］.微電子學與計算機,2002(6):69.
　　［5］ 湯亞玲,秦鋒.高效快速排序算法研究［J］.計算機工程，2011,37(6):7778,87.
　　［6］ 石壬息,張錦雄,王鈞,等.快速排序異步并行算法的多線程實現［J］.廣西科學院學報，2005,18(1):5354,64.
　　［7］ 周玉林,鄭建秀.快速排序的改進算法［J］.上饒師范學院學報,2001,21(6):1215.
　　［8］ 邵順增.穩定快速排序算法研究［J］.計算機應用與軟件,2014,31(7):263266.
　　［9］ 宋鴻陟,傅熠,張麗霞,等.分割方式的多線程快速排序算法［J］.計算機應用,2010,30(9):23742378.
　　［10］ 潘思.充分利用局部有序的快速排序［J］.計算機研究與發展,1986,23(9):5156.
　　［11］ 梁佳.一種改進的堆排序算法［J］.微型機與應用,2015,34(6):1012.
　　［12］ 張旭,王春明,劉洪,等. 基于雙向鏈表排序的系統誤差穩健配準方法［J］.電子技術應用,2015,41(9):7477,81.