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

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

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

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

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