黃志波，趙晴，孫少乙
　?。ㄈA北計(jì)算機(jī)系統(tǒng)工程研究所，北京 100083）

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

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

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

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