多線程快速排序算法的設(shè)計(jì)與優(yōu)化

李添銳,曹慶年,孟開元

(西安石油大學(xué) 計(jì)算機(jī)學(xué)院,陜西 西安 710065)

0 引言

排序問題不僅是計(jì)算機(jī)科學(xué)中非常重要且應(yīng)用廣泛的問題之一,而且在計(jì)算機(jī)圖形學(xué)、系統(tǒng)決策、搜索引擎等領(lǐng)域有著重要地位,并曾在2000 年被評為對工程和科學(xué)計(jì)算研究與實(shí)踐影響最大的十大問題之一[1-4]。有資料顯示,系統(tǒng)在處理排序問題上,中央處理器(Central Processing Unit,CPU)的時(shí)間占比很大,可達(dá)20%～60%[5]。在傳統(tǒng)的內(nèi)部排序算法中,由Hoare 提出的快速排序(Quick Sort)是一種效率相對較高的算法,但待排序列長度較長(大于106)時(shí),其時(shí)間成本依舊較高。因此十分有必要對快速排序算法進(jìn)行進(jìn)一步優(yōu)化。

線程(Thread)是操作系統(tǒng)能夠進(jìn)行運(yùn)算的最小單位。一個處理排序的進(jìn)程,若采用快速排序算法,其劃分的兩個子序列可分別由兩個并行執(zhí)行的線程完成。在劃分的子序列長度相同的情況下,時(shí)間消耗僅為串行執(zhí)行的50%。將多線程技術(shù)引入快速排序算法,可以大大提高排序效率。

1 快速排序以及傳統(tǒng)優(yōu)化方法

快速排序的主要步驟可以簡化如下:

雖然快速排序的效率是內(nèi)部排序算法中最快的,但在算法第4 行中,若劃分的“標(biāo)桿”選取不當(dāng),在極端情況下,每次劃分的兩個子序列長度都分別為0 和原長度減1,此時(shí)不僅時(shí)間復(fù)雜度高至O(n2),且極易引起棧溢出(Stack Overflow)導(dǎo)致排序失敗。同時(shí)對于大量重復(fù)元素的待排序列,無論怎樣選取“標(biāo)桿”,均無法避免上述問題。為了克服快速排序的缺點(diǎn),傳統(tǒng)的優(yōu)化方法如下。

1.1 標(biāo)桿選取

可以先將序列中的隨機(jī)某個元素與首元素交換,再將首元素作為標(biāo)桿。此種方法被稱為“隨機(jī)標(biāo)桿”法,但會因?yàn)樯呻S機(jī)數(shù)而增加額外的開銷。“三數(shù)取中”法可以避免此問題,其基本思想是先將序列的中間元素、首元素和末元素進(jìn)行升序排序,再將首元素作為標(biāo)桿。但以上兩種方法都無法解決大量重復(fù)元素序列的問題。

1.2 三軸排序

在每次序列劃分之后,從“標(biāo)桿”出發(fā),將兩個子序列中和“標(biāo)桿”相等的元素均交換到“標(biāo)桿”的左右兩邊,最終將原序列劃分成3 部分。通過采取適當(dāng)?shù)慕粨Q方法,排序整體的復(fù)雜度不會改變,同時(shí)減少了左右子序列的長度。此種算法極大地改進(jìn)了大量重復(fù)元素的序列。

1.3 引入插排

當(dāng)待排序列較短時(shí),采用分治遞歸操作所需的開銷已經(jīng)大于簡單排序的開銷,故引入插入排序處理較短的子序列。此方法的難點(diǎn)在于最小分段閾值k的選取,k為經(jīng)驗(yàn)值,由系統(tǒng)的遞歸開銷等因素決定。在Java 中,此k值取為32 效果最佳[6]。在C++的內(nèi)置sort()函數(shù)中,k值為16,一般情況下5～25 均可。

2 多線程優(yōu)化方法

多核CPU 的出現(xiàn)使得多線程編程方法成為可能,同時(shí)也為許多傳統(tǒng)經(jīng)典算法進(jìn)一步優(yōu)化提供了新思路[7]。

2.1 子線程處理子序列

快速排序中的遞歸操作中,可以創(chuàng)建子線程處理其中1 個子序列。在多核CPU 系統(tǒng)中,線程會分配到不同的核心上并行執(zhí)行,于是處理子序列的時(shí)間可大大縮短。引入多線程編程處理后的算法如下:

由于線程創(chuàng)建需要時(shí)間,在遞歸操作時(shí)可選用較短子序列交由子線程處理。

2.2 根據(jù)最大線程數(shù)的改進(jìn)

上述算法適用于無限創(chuàng)建線程的理想化模型,而實(shí)際情況中線程數(shù)受限于CPU 核心數(shù),故須改進(jìn)。引入多線程編程的深度d這一額外參數(shù),d=0 時(shí)為傳統(tǒng)串行方法;d>0 時(shí),構(gòu)建新線程執(zhí)行子序列,同時(shí)d自減1。d的值由系統(tǒng)CPU 核心數(shù)N決定,通常d取■log2N」。

2.3 采用線程池

當(dāng)待排序列為隨機(jī)序列時(shí),一次快排劃分后的兩個子序列的長度不同。因此會出現(xiàn)先前創(chuàng)建的線程已經(jīng)運(yùn)行結(jié)束而釋放,后續(xù)的待排子序列無法創(chuàng)建新線程的現(xiàn)象。為此可以創(chuàng)建線程池,當(dāng)線程池飽和時(shí),采用傳統(tǒng)串行算法,這樣可以時(shí)刻充分利用CPU 的各個核心。

2.4 性能測試

性能測試采用傳統(tǒng)串行快速排序和多線程優(yōu)化快速排序兩種方式分別對8 000 000 個隨機(jī)數(shù)據(jù)進(jìn)行排序,并對其時(shí)間消耗進(jìn)行對比,從而得出多線程優(yōu)化方法的改進(jìn)幅度。

在Intel(R)Core(TM)i7-6700 CPU@3.40 GHz 4核8 線程CPU 的PC 上使用C++多線程編程實(shí)現(xiàn)2.1中的算法并進(jìn)行測試。通過多次測試取平均值,測試結(jié)果如表1 所示。

表1 優(yōu)化結(jié)果比較

由于測試主機(jī)為4 核主機(jī),故算法執(zhí)行中最多有4個CPU 核心同時(shí)工作。從測試結(jié)果可以看出,4 核心多線程優(yōu)化快速排序算法的所需時(shí)間僅為傳統(tǒng)串行快速排序算法的1/4。

3 優(yōu)化上限分析

顯然,當(dāng)待排序列為升序序列,即經(jīng)過“三數(shù)取中”法后為最好情況時(shí),采用多線程編程的優(yōu)化幅度達(dá)到最大。

3.1 時(shí)間復(fù)雜度分析

在最好的情況下,設(shè)長度為n的序列的劃分操作時(shí)間消耗為P(n),不難得出:

其中,c為執(zhí)行1 條指令所需時(shí)間,設(shè)單位為us。

不妨設(shè)n=2^(k+1)-1,k=0,1,2,…如此可保證每次劃分都是最優(yōu)劃分。

傳統(tǒng)串行快速排序的時(shí)間消耗為:

推導(dǎo)后得:

若當(dāng)前CPU 的核心為2,多線程深度d=1,設(shè)系統(tǒng)創(chuàng)建1 個子線程的所需時(shí)間為td,此時(shí)多線程優(yōu)化快速排序的時(shí)間消耗F1(n)為:

推導(dǎo)后得:

相對于傳統(tǒng)單線程快速排序,時(shí)間節(jié)省率H1(n)為:

類似地,可以由數(shù)學(xué)歸納法得到d=k時(shí)的時(shí)間消耗Fk(n)和時(shí)間節(jié)省率Hk(n)

通過公式(9)可以看出,時(shí)間節(jié)省率Hk(n)是線程深度d和待排序列長度n的函數(shù)。

在保證n?d的情況下,n和d越大,節(jié)省率越高。

3.2 理論驗(yàn)證

為驗(yàn)證3.1 中的公式正確性,采用2.2 中的算法C++來實(shí)現(xiàn),待排序列長度n取1 048 591,線程深度d分別取1,2,3,經(jīng)過測試,平均td=150 μs,c=1.5×10-3μs,待排序列取最優(yōu)序列。驗(yàn)證結(jié)果如表2 所示。

表2 理論驗(yàn)證結(jié)果

可以看出,實(shí)際運(yùn)行結(jié)果和理論分析極為接近,因此,3.1 的理論分析得到了驗(yàn)證。

4 結(jié)語

快速排序是所有內(nèi)部排序算法中平均性能最優(yōu)的算法,但其本身具有許多不足之處。本文在C++平臺中實(shí)現(xiàn)了對快速排序遞歸操作的進(jìn)一步優(yōu)化,通過建立子線程并發(fā)處理兩個子序列,使得排序速度得到了大幅提高。

通過對多線程快速排序的理論分析,本文提出了此方法在優(yōu)化程度上的理論上限。在實(shí)際應(yīng)用中,由于每次劃分的子序列長度不一,因此保證線程的利用率便成了多線程算法中的關(guān)鍵。

由于內(nèi)存和CPU 核心數(shù)量的限制,不宜做更大數(shù)據(jù)量和更多線程的測試。將來的實(shí)驗(yàn)中可以考慮其他環(huán)境,進(jìn)一步驗(yàn)證優(yōu)化理論,分析線程調(diào)度的開銷等其他因素,以確定更精確的參數(shù),進(jìn)一步優(yōu)化排序性能。

和CPU 相比,GPU 的并行計(jì)算能力更加強(qiáng)大,使用CPU 優(yōu)化也是對快速排序的一種優(yōu)化方式,在未來的實(shí)驗(yàn)中也可嘗試使用GPU 優(yōu)化并和CPU 算法做對比[8]。