基于Java的多線程快速排序設(shè)計與優(yōu)化

黃志波，趙　晴，孫少乙

(華北計算機(jī)系統(tǒng)工程研究所，北京 100083)

?

基于Java的多線程快速排序設(shè)計與優(yōu)化

黃志波，趙晴，孫少乙

(華北計算機(jī)系統(tǒng)工程研究所，北京 100083)

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

Fork/Join；多線程；快速排序；算法優(yōu)化

引用格式：黃志波，趙晴，孫少乙. 基于Java的多線程快速排序設(shè)計與優(yōu)化[J].微型機(jī)與應(yīng)用，2016,35(16)：23-25，28.

0　引言

排序一直是程序開發(fā)中的一個重點(diǎn)，尤其在一些應(yīng)用開發(fā)中經(jīng)常用到，在搜索開發(fā)中也是重點(diǎn)研究對象。所以人們對排序的研究一直堅持不懈。在眾多排序算法中，快速排序是一個表現(xiàn)極其優(yōu)秀的算法。該算法于1962年由Tony Hoare首次提出[1]，它基于分治思想，使得排序性能得到極大的提升[2]。如今的電腦或者手機(jī)一般都是多核處理器，為了提高用戶體驗(yàn)，應(yīng)該充分利用其所擁有的硬件設(shè)備。本文主要講述多線程下快速排序的設(shè)計與優(yōu)化過程，對普通快速排序[3]、基于多線程的快速排序以及基于Fork/Join的多線程排序進(jìn)行了比較。

1　單線程快速排序

快速排序是基于比較的一種排序算法，而基于比較的排序算法的最佳性能為O(nlgn)?？焖倥判虻倪\(yùn)行時間與數(shù)據(jù)劃分是否對稱有關(guān)，且與選擇了哪一個元素作為劃分基準(zhǔn)有關(guān)[4]。在信息論里面，N個未排序的數(shù)字，共有N！種排法，但是只有一種是想要的(譬如遞增或者遞減)。也就是說，排序問題的可能性有N！種，而任何基于比較的排序基本操作單元都是“比較a和b”，而這個比較一般是有兩個結(jié)果，這樣恰好可將剩下來的排序減少為N!/2種。因此當(dāng)選定某個位置的元素作為pivot(基準(zhǔn))時，若能恰好將原序列平均分為兩個子序列，那么遞歸的次數(shù)將會顯著地減少，從而排序的效率將有所提高。因此均衡地分割序列一直是一個重點(diǎn)研究方向，如隨機(jī)選取基準(zhǔn)、三數(shù)選中等策略。此外還有兩種情況是研究排序算法時必須考慮的[5]，第一種情況就是當(dāng)序列中大部分?jǐn)?shù)據(jù)甚至全部數(shù)據(jù)相等，也就是大量數(shù)據(jù)重復(fù)時；第二種情況是當(dāng)序列中大部分?jǐn)?shù)據(jù)甚至整個序列已經(jīng)是有序的[6]。這兩種情況都會使得快速排序的性能變得最壞，也就是O(n2)。針對第一種情況研究者們已經(jīng)提出了三分序列的解決方案；第二種情況就是如何恰當(dāng)?shù)剡x取比較基準(zhǔn)，固定地選取首部或者尾部元素作為基準(zhǔn)顯然不是最佳的，人們提出了隨機(jī)選取元素與三數(shù)選中兩種方法加以改進(jìn)。本文中分別采用隨機(jī)選取元素和以尾端數(shù)據(jù)作為基準(zhǔn)來實(shí)現(xiàn)的算法，目的是使算法設(shè)計更簡練，其次是為了使單線程與多線程在核心算法上保持一致性。由于快速排序算法核心算法是一致的，故只在本節(jié)展開描述，接下來的章節(jié)中就不贅述了。

快速排序偽代碼[6]如下。

QuickSort(a, l, r)

if l

QuickSort(a, l, k-1)

QuickSort(a, k+1, r)

其中Partition函數(shù)是核心函數(shù)，在測試時根據(jù)測試數(shù)據(jù)類型的不同采用相應(yīng)的最優(yōu)實(shí)現(xiàn)算法。

針對有序數(shù)據(jù)Partition函數(shù)代碼設(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;

針對隨機(jī)數(shù)據(jù)和重復(fù)數(shù)據(jù)Partition函數(shù)設(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;

為了防止因?yàn)閿?shù)字比較大，超出int類型最大值，均用long類型，該類型基本上完全適用于實(shí)際應(yīng)用當(dāng)中。

2　多線程快速排序

由于快速排序是采用分治策略，并且基準(zhǔn)左右序列的遞歸排序是互不影響的，因此完全可以考慮采用多線程來做并行處理，每次基于基準(zhǔn)產(chǎn)生左右分塊序列的時候，可以分別用一條線程來執(zhí)行左右序列的排序工作，這樣能在充分利用計算機(jī)性能的條件下，使排序算法表現(xiàn)更優(yōu)，從而增大排序速度。一種實(shí)現(xiàn)是將需要排序的數(shù)組分成多組，然后對每組實(shí)現(xiàn)一個線程來快速排序，最后用歸并排序算法的思想合并這些數(shù)組，最終實(shí)現(xiàn)原序列的排序過程。這種實(shí)現(xiàn)方式在合并時需要額外時間，并且還需要額外的空間進(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)建線程。為了能最大化測試機(jī)器的性能，采用線程池來管理線程。

線程之間切換也是極為耗時間的，因此常常需要根據(jù)當(dāng)前機(jī)器的處理器數(shù)目來創(chuàng)建線程數(shù)。獲取測試機(jī)器的cpu數(shù)目：

private static final int N=Runtime.getRuntime().availableProcessors();

執(zhí)行排序線程的線程池：

private static Executor pool= Executors. newFixedThreadPool(N);

為了防止競爭條件的產(chǎn)生，隊列中的線程是有順序的，必須是某些線程執(zhí)行完后等待在隊列中的剩余線程才能繼續(xù)進(jìn)行，這也是結(jié)合算法來設(shè)計的。由此可以看到此方案存在不足之處，即線程之間存在鎖，而鎖會極大地影響多線程的性能。

下面是排序時首先調(diào)用的方法,參數(shù)count記錄當(dāng)前正在執(zhí)行的線程數(shù)，因?yàn)樵贘ava中++i和i++(--操作同理)操作不是線程安全的，在使用的時候需要加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接口時，必須重寫run方法。

@Override

public void run() {

quicksort(left, right);

synchronized (count) {

if (count.getAndDecrement() == 1)

count.notify();}}

這是真正進(jìn)行排序的方法，當(dāng)隊列中還有尚未執(zhí)行的任務(wù)時，就繼續(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)建的線程到一個特定的閾值時，即執(zhí)行回滾，繼續(xù)遞歸地創(chuàng)建線程，以避免恒定的上下文切換的開銷。

3　基于Fork/Join框架多線程快速排序

Fork/Join框架是Java7提供的一個用于并行執(zhí)行任務(wù)的框架，即把大任務(wù)分割成若干個小任務(wù)，最終匯總每個小任務(wù)的結(jié)果后得到之前大任務(wù)的結(jié)果。其中Fork用來做分割任務(wù)操作，而Join則是將分割后的小任務(wù)執(zhí)行結(jié)果進(jìn)行合并的操作。該框架之所以能在多線程編程表現(xiàn)優(yōu)異，是因?yàn)樗谝粋€叫作Work-stealing的核心算法。該算法是指線程從其他線程隊列里獲取任務(wù)來執(zhí)行。也就是說當(dāng)需要做一個比較大的任務(wù)時，可以把這個任務(wù)分割為若干互不依賴的子任務(wù)。為了減少線程間的競爭，把這些子任務(wù)分別放到不同的隊列里，并為每個隊列創(chuàng)建一個單獨(dú)的線程來執(zhí)行隊列里的任務(wù)，這樣就實(shí)現(xiàn)了線程和隊列一一對應(yīng)。比如某線程T負(fù)責(zé)處理T隊列里的任務(wù)，但是有的線程先執(zhí)行完了自己隊列里的任務(wù)，而其他線程對應(yīng)的隊列里還有任務(wù)在等待處理。與其讓已經(jīng)執(zhí)行完隊列中任務(wù)的線程等著，不如讓它去幫其他線程執(zhí)行任務(wù)，于是它就去其他線程的隊列里竊取一個任務(wù)來執(zhí)行。但是這當(dāng)中其實(shí)也存在一個問題，就是當(dāng)它與被竊取任務(wù)的線程同時訪問同一個隊列時，仍會有竊取任務(wù)線程與被竊取任務(wù)線程之間的競爭，為了減少這種現(xiàn)象的出現(xiàn)，通常會使用雙端隊列，被竊取任務(wù)線程永遠(yuǎn)從雙端隊列的頭部拿任務(wù)執(zhí)行，而竊取任務(wù)的線程永遠(yuǎn)從雙端隊列的尾部拿任務(wù)執(zhí)行。

Work-stealing算法的優(yōu)點(diǎn)是充分利用線程進(jìn)行并行計算，并減少了線程間的競爭，其缺點(diǎn)是在某些情況下還是存在競爭，比如雙端隊列里只有一個任務(wù)時，并且消耗了更多的系統(tǒng)資源，比如創(chuàng)建多個線程和多個雙端隊列。

Fork/Join框架工作步驟如下：

(1)分割任務(wù)。首先需要有一個fork類來把大任務(wù)分割成子任務(wù)，當(dāng)子任務(wù)還是很大時，就需要不停地分割，直到分割出的子任務(wù)足夠小[9]。在算法實(shí)現(xiàn)時以數(shù)據(jù)量大小為依據(jù)來分割任務(wù)。

(2)執(zhí)行任務(wù)并合并結(jié)果。被分割的子任務(wù)分別放在雙端隊列里，啟動后的線程分別從雙端隊列里獲取任務(wù)執(zhí)行。在同一個進(jìn)程中的線程可以共享數(shù)據(jù)，各子任務(wù)執(zhí)行完的結(jié)果都統(tǒng)一放在一個隊列里，啟動一個線程從隊列里拿數(shù)據(jù)，然后合并這些數(shù)據(jù)。但是在快速排序時，因?yàn)樗莾?nèi)排序，所以可以不用進(jìn)行最后的數(shù)據(jù)合并過程，實(shí)際上，原序列排序后就是所要的結(jié)果。如此一來，只要專注于分割任務(wù)和排序就行了。

當(dāng)創(chuàng)建一個ForkJoin任務(wù)時，通常情況下不需要直接繼承ForkJoinTask類，而只需要繼承它的子類，F(xiàn)ork/Join框架提供了兩個子類：RecursiveAction：沒有返回結(jié)果的任務(wù)；RecursiveTask：有返回結(jié)果的任務(wù)。

因?yàn)椴恍枰蝿?wù)有返回結(jié)果，因此采用子類RecursiveAction。ForkJoinTask需要通過ForkJoinPool來執(zhí)行，主任務(wù)被分割出的子任務(wù)會添加到當(dāng)前工作線程所維護(hù)的雙端隊列中，進(jìn)入隊列的頭部。當(dāng)某個工作線程的隊列里暫時沒有任務(wù)可執(zhí)行時，它就會隨機(jī)地從其他工作線程所維護(hù)的隊列的尾部獲取一個任務(wù)。

需要設(shè)定子任務(wù)分割限制條件，即數(shù)據(jù)量的大小，這里將其設(shè)定為286，因?yàn)檫@個數(shù)字是快速排序最佳實(shí)現(xiàn)的閾值，可以參考JDK源碼。

private int THRESHOLD = 286;

ForkJoinTask需要實(shí)現(xiàn)compute方法，在該方法中首先需要判斷當(dāng)前任務(wù)是否足夠小，如果足夠小就直接執(zhí)行任務(wù)，即調(diào)用排序方法排序，否則就需要分割成兩個子任務(wù)，通過invokeAll方法將兩個子任務(wù)分別進(jìn)行fork，被fork后的子任務(wù)會再次調(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　測試

為了更直觀以及更全面地進(jìn)行比較，測試時生成了三組數(shù)據(jù)，均為1 000萬個，但分別為隨機(jī)的生成不同數(shù)字，大量重復(fù)數(shù)字以及有序數(shù)字。同時為了使測試順利進(jìn)行，算法會稍作調(diào)整。當(dāng)數(shù)據(jù)為隨機(jī)數(shù)據(jù)和重復(fù)數(shù)據(jù)時，partition方法以尾端數(shù)字作為基準(zhǔn)排序；當(dāng)數(shù)據(jù)為有序數(shù)據(jù)時，采用隨機(jī)獲取基準(zhǔn)來進(jìn)行排序。此外由于數(shù)據(jù)量比較大，故保存在txt文本文檔里。排序完成后寫到新建文檔里，可便于檢查排序是否正確以及是否完整。本測試只比較排序時間。因?yàn)槲臋n的讀寫不是本文討論的問題，所以就不展開敘述了。測試機(jī)器為MacBook Pro841，CPU數(shù)目為4，運(yùn)行內(nèi)存為16 GB。測試過程中為了使結(jié)果更具有一般性，采用多次測試取平均值。測試數(shù)據(jù)如表1所示。

表1　測試數(shù)據(jù)比較　(ms)

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

5　結(jié)論

本文總結(jié)了單線程下快速排序不斷優(yōu)化的歷程，并設(shè)計了多線程下排序的優(yōu)化方法。從實(shí)驗(yàn)測試結(jié)果看出，隨著時代的進(jìn)步，機(jī)器不斷更替，重新思考以前一些算法問題時有了另一層面的思維方式，往往在新的思維方式下會取得不一樣的成就[11]。排序問題一直是研究的熱點(diǎn)，而快速又更是備受關(guān)注[12]。此外關(guān)于多線程還有一種處理方案就是基于actor模型的多線程框架，這也是一種多線程處理策略。在實(shí)驗(yàn)中也嘗試過，不過并未取得理想效果，因此就不展開敘述了，若讀者有興趣，可以試著去實(shí)現(xiàn)并優(yōu)化算法。

[1] CORMEN T H, LEISERSON C E, RIVEST R L, et al.算法導(dǎo)論原書(第二版)[M].北京：高等教育出版社，2006.

[2] HOARE C A R. Quicksort[J]. The Computer Journal, 1962(5):10-15.

[3] 胡云.幾種快速排序算法實(shí)現(xiàn)的比較[J].安慶師范學(xué)院學(xué)報,2008,14(3):100-103.

[4] 霍紅衛(wèi),許進(jìn).快速排序算法研究[J].微電子學(xué)與計算機(jī),2002(6):6-9.

[5] 湯亞玲,秦鋒.高效快速排序算法研究[J].計算機(jī)工程，2011,37(6):77-78,87.

[6] 石壬息,張錦雄,王鈞,等.快速排序異步并行算法的多線程實(shí)現(xiàn)[J].廣西科學(xué)院學(xué)報，2005,18(1):53-54,64.

[7] 周玉林,鄭建秀.快速排序的改進(jìn)算法[J].上饒師范學(xué)院學(xué)報,2001,21(6):12-15.

[8] 邵順增.穩(wěn)定快速排序算法研究[J].計算機(jī)應(yīng)用與軟件,2014,31(7):263-266.

[9] 宋鴻陟,傅熠,張麗霞,等.分割方式的多線程快速排序算法[J].計算機(jī)應(yīng)用,2010,30(9):2374-2378.

[10] 潘思.充分利用局部有序的快速排序[J].計算機(jī)研究與發(fā)展,1986,23(9):51-56.

[11] 梁佳.一種改進(jìn)的堆排序算法[J].微型機(jī)與應(yīng)用,2015,34(6):10-12.

[12] 張旭,王春明,劉洪,等. 基于雙向鏈表排序的系統(tǒng)誤差穩(wěn)健配準(zhǔn)方法[J].電子技術(shù)應(yīng)用,2015,41(9):74-77,81.

The design and optimization for multi-thread quicksort based on Java

Huang Zhibo，Zhao Qing，Sun Shaoyi

(National Computer System Engineering Research Institute of China, Beijing 100083, China)

In order to implement multithreaded quicksort,we propose a quicksort algorithm which is based on Fork/Join framework, and try to optimize the quicksort algorithm.This algorithm mostly is used for large amounts of data required for sorting process.

Fork/Join; multi-thread; quicksort; algorithm optimization

TP31

A

10.19358/j.issn.1674- 7720.2016.16.006

2016-03-29)

黃志波(1992-)，通信作者，男，在讀研究生，主要研究方向：分布計算與并行處理。E-mail：bobo492295520@163.com。

趙晴(1964-)，男，本科，高級工程師，主要研究方向：信息的獲取與處理。

孫少乙(1990-)，男，在讀研究生，主要研究方向：智能制造與應(yīng)用。