康志輝

(廈門軟件職業(yè)技術(shù)學(xué)院，福建廈門361024)

排序是計算機領(lǐng)域中一類非常重要的問題，在很多數(shù)據(jù)處理中占用了計算機大量的處理時間，因此尋找高效排序算法一直是人們感興趣的問題［1］。以往，人們提出了許多高效排序算法，如快速排序算法［2］、縱橫多路并行歸并算法［3］、基于MPP的并行歸并算法［4］等。但是，有關(guān)桶排序算法的研究并不多，其主要原因是并行桶排序算法的時間復(fù)雜度為O((n/p)*log(n/p))［5］，如果要加以改進(jìn)，比較困難。其次，并行桶排序算法對待排序數(shù)據(jù)的要求很高，要求數(shù)據(jù)在已知的范圍內(nèi)均勻分布或接近均勻分布［11－12］。若待排序數(shù)據(jù)的分布極其不均勻，則并行桶排序算法會退化成串行快速排序算法，此時，其時間復(fù)雜度變?yōu)镺(n*logn)［5］。本文針對以上問題，提出一種改進(jìn)的并行桶排序算法，使其對任意分布的待排序數(shù)據(jù)進(jìn)行排序的時間復(fù)雜度為O((n/p)*log(n/p))。

1 改進(jìn)的并行桶排序算法

首先，我們給出如下定義。

定義1 前k－歸并:設(shè)非降序列S1和S2長分別為m和n，序列S為S1和S2歸并的結(jié)果，則稱由S1和S2求取S前k項的操作為S1和S2的前k－歸并(其中0＜=k＜=m+n)。

定義2 后k－歸并:設(shè)非降序列S1和S2長分別為m和n，序列S為S1和S2歸并的結(jié)果，我們稱由S1和S2求取S后k項的操作為S1和S2的后k－歸并(其中0＜=k＜=m+n)。

算法的基本思想:設(shè)A為長n的無序序列，B(i)(j)［k］表示第i層第j個桶的第k個數(shù)據(jù)，處理器數(shù)為p(不妨設(shè)n能被p整除)，對A進(jìn)行排序。首先，把序列A劃分成等長子序列，將子序列與第0層的桶一一對應(yīng)，并對桶內(nèi)數(shù)據(jù)進(jìn)行快速排序，從而得到?p/2」個有序桶。然后，對第0層中的相鄰有序桶并行進(jìn)行前－歸并和后－歸并操作，從而生成第1層有序桶中的數(shù)據(jù)。從第1層開始，在以后各層的前后－歸并過程中，所產(chǎn)生的數(shù)據(jù)放入下層的相應(yīng)桶內(nèi)，只要下層桶內(nèi)有數(shù)據(jù)就開始下層桶的前后 －歸并操作，把得到的數(shù)據(jù)放到其再下層的相應(yīng)桶內(nèi)。如此，從第1層開始形成樹形結(jié)構(gòu)桶陣列，最后結(jié)果由樹根的桶得出。

算法的詳細(xì)描述如下:

輸入:無序序列A［0…n－1］，處理器個數(shù)p

輸出:有序序列 B［0…n－1］

end

本算法由三部分組成:

第一，把序列A劃分為p個n/p的等長子序列，分別放入桶B(0)(1)～B(0)(p)，處理器P1～Pp對B(0)(1)～B(0)(p)中的數(shù)據(jù)進(jìn)行快速排序，使B(0)(1)～B(0)(p)成為有序桶。

第二，處理器P1對桶B(0)(1)和B(0)(2)進(jìn)行前n/p－歸并，結(jié)果放入B(1)(1)的前n/p項，P2對桶B(0)(1)和B(0)(2)進(jìn)行后n/p－歸并，結(jié)果放入B(1)(1)的后n/p項，依次處理后面的桶，可得到長為2*n/p的有序桶B(1)(1)～B(1)(p/2)(最后一個桶序列長可能小于2*n/p)。

第三，處理器P1對桶B(1)(1)和B(1)(2)進(jìn)行前2*n/p－歸并，結(jié)果放入B(2)(1)的前2*n/p項，P3對桶B(1)(1)和B(1)(2)進(jìn)行后2*n/p－歸并，結(jié)果放入B(2)(1)的后2*n/p項，并行處理后面的桶，可得到長為4*N/n的有序桶B(2)(1)～B(2)(p/4)(最后一個桶序列長可能小于4*n/p)。此時，偶數(shù)的處理器空閑，而當(dāng)B(2)(1)和B(2)(2)的第0項有數(shù)據(jù)時(這只需要P1對桶B(1)(1)和B(1)(2)進(jìn)行一次前－歸并操作，P5對桶B(1)(3)和B(1)(4)進(jìn)行一次前－歸并操作)，P2可對B(2)(1)和B(2)(2)進(jìn)行前4*n/p－歸并，產(chǎn)生的結(jié)果放入B(3)(1)的前4*n/p項。同理，P4對B(2)(1)和B(2)(2)進(jìn)行后4*n/p－歸并，產(chǎn)生的結(jié)果放入B(3)(1)的后4*n/p項，同時并行處理第三層的桶中的數(shù)據(jù)，逐漸產(chǎn)生第四層桶的數(shù)據(jù)，且當(dāng)?shù)谒膶拥耐坝袛?shù)據(jù)時(只需要第三層的桶同時進(jìn)行一次前后－歸并操作)就開始產(chǎn)生第五層桶的數(shù)據(jù)。如此遞歸，形成了深度為?log(「p/2?)」+1的樹形結(jié)構(gòu)，最后的結(jié)果由樹根上的桶B(?log(「p/2?)」+1)(0)給出。

舉下面實例，進(jìn)一步說明算法的執(zhí)行過程。

待排序數(shù)據(jù):13，2，52，16，30，21，5，29，18，70，29，37，15，24，7，19

處理器數(shù):8

本實例對幾個隨機數(shù)據(jù)進(jìn)行排序，如上所示:(a)部分:是待排序序列根據(jù)處理器數(shù)目進(jìn)行劃分后快速排序的結(jié)果。(b)部分:1)是(a)中的相鄰子序列進(jìn)行前1－歸并和后1－歸并的結(jié)果，其詳細(xì)過程是2與16比較把2放入下一層的第一個桶的首位，13和52比較，把52放入下一層的第一個桶的末位，同時并行操作后面的桶。2)是進(jìn)行前2－歸并和后2－歸并的結(jié)果，即13與16比較，把13放入下一層的第一個桶的第二位，13與16比較，把16放入下一層的第一個桶的倒數(shù)第二位，同時并行操作后面的桶。(c)部分:1)是對(b)中得到的四個有序桶(第一層的桶)進(jìn)行前1－歸并和后1－歸并操作，分別得到其下一層的兩個數(shù)據(jù)。2)對第一層的桶進(jìn)行前后2－歸并的同時，由于第二層桶有待處理數(shù)據(jù)，且有空閑的處理器，所以開始并行的前后－歸并第二層桶中的數(shù)據(jù)。其詳細(xì)過程是，13和5比較把5放入下層第一個桶的第二位，16和30比較把30放入下層第一個桶的倒數(shù)第二位，18和15比較，37和24比較，方別把15和37放入下層第二個桶的相應(yīng)位置。同時，在下一層的桶的前1－歸并中，2和7進(jìn)行比較，把2放入第三層桶的首位，52和70進(jìn)行比較，把70放入第三層桶的末位。由于第三層只有一個桶，所以其最終結(jié)果即為我們所需要的已排序序列。

2 算法正確性分析

算法由3部分組成，第一部分的正確性已經(jīng)在相關(guān)文獻(xiàn)中得到論證。下面來證明第二部分和第三部分的正確性。

引理1 對長為m和n的有序序列S1和S2做前k－歸并和后(m+n－k)－歸并，合并其結(jié)果，即可得到S1和S2的歸并結(jié)果。

證明 設(shè)S1和S2歸并結(jié)果為S，顯然，S長為m+n，由定義1可知，前k－歸并S1和S2可以得到S的前k項，后(m+n－k)－歸并S1和S2可以得到S的后m+n－k項，合并S的前k項和后m+n－k項即可得到S。

推論1 對長為m和n的有序序列S1和S2做前k1－歸并和后k2－歸并，若k1+k2＞=m+n，合并前－歸并和后－歸并的結(jié)果，就可以得到S1和S2的歸并結(jié)果。推論2 算法在執(zhí)行完第二部分，得「p/2?個有序序列。引理2 算法第三部分最多使用p－2個處理器。

證明 在算法的第三部分，會形成一個二叉樹結(jié)構(gòu)的桶陣列。在前后－歸并過程中，每兩個桶使用兩個處理器，單個桶不使用處理器，即所使用的處理器數(shù)最多和桶的數(shù)目一樣。又在第一層，共有「p/2?個桶，由二叉樹的性質(zhì)可得第三部分的桶陣列深度為?log(「p/2?)」+1，所以所需桶的數(shù)目為2?log(「p/2?)」+1－1=p－1個，由于樹根的桶不需要處理器進(jìn)一步處理，所以最多使用的處理器數(shù)為p－2。

定理 算法結(jié)束時，最后一層的桶保存A序列的有序排列。

證明 由推論2知，算法執(zhí)行完第二部分可以得到「p/2?個有序序列，在算法的第三部分，只要桶中存在沒有被處理過的數(shù)據(jù)，就對其進(jìn)行前后－歸并操作，把每次歸并的結(jié)果放入下一層的相應(yīng)桶的相應(yīng)位置。由于對上層桶的一次前后－歸并操作可以得到其下一層的每個桶的兩個數(shù)據(jù)，而每次的前后－歸并操作最多只處理掉桶中的一個數(shù)據(jù)。所以，只要某一層開始?xì)w并操作，其上一層就能及時地供應(yīng)足夠的數(shù)據(jù)，直到上層數(shù)據(jù)處理完畢，這時，這一層中的所有數(shù)據(jù)也全部給出。由于最多使用的處理器數(shù)為p－2個，即有足夠的處理器使用，而不需要等待處理器。當(dāng)算法執(zhí)行完畢，所有的數(shù)據(jù)匯集到樹根節(jié)點的桶中，并且，桶中的數(shù)據(jù)是有序的，即算法結(jié)束時，最下層桶保存著原序列的有序排列。

3 算法時間復(fù)雜度分析

算法的第一部分，對長為n/p的序列進(jìn)行快速排序，所需時間為O((n/p)*log(n/p))。算法的第二部分，對長為n/p的有序序列執(zhí)行前后n/p－歸并操作，時間為n/p。算法的第三部分，在算法第二步完成之后開始執(zhí)行，對其形成的p/2個長為2*n/p的有序序列進(jìn)行前后－歸并操作。只要對p/2個長為2*n/p的有序序列執(zhí)行一次前后－歸并操作就可以為第2層的每個桶生成2個數(shù)據(jù)。同理，在第2層中進(jìn)行一次前后－歸并操作也可以為第3層的每個桶生成2個數(shù)據(jù)，如此，直到最后一層。由于第三部分共?log(「p/2?)」+1層，所以當(dāng)最后一層有數(shù)據(jù)時，總共需要?log(「p/2?)」次操作。而得到最后一層的桶的所有數(shù)據(jù)需要倒數(shù)第二層「n/2?執(zhí)行次前后－歸并操作，所以第三部分總的時間為?log(「p/2?)」+「n/2? －1。

綜上分析，算法總的執(zhí)行時間為T(n)=n/p*log(n/p)+n/p+?log(「p/2?)」+n/2=O(n/p*log(n/p))，算法成本為C(n)=p*T(n)=O(n*log(n/p))。

4 結(jié)論

本文針對多核計算環(huán)境下的桶排序算法優(yōu)化，突破了經(jīng)典的并行桶排序算法中要求原始數(shù)據(jù)在已知的范圍內(nèi)服從均勻分布或接近均勻分布的限制。這種改進(jìn)的并行桶排序算法可以對任意分布的數(shù)據(jù)進(jìn)行排序操作，其時間復(fù)雜度為O((n/p)*log(n/p))，這與經(jīng)典并行桶排序算法對均勻分布的數(shù)據(jù)的排序時間復(fù)雜度是相同的。

［1］楊磊，宋濤.基于數(shù)組的桶排序算法［J］.計算機研究與發(fā)展，2007，44(2):341 －347.

［2］霍紅衛(wèi)，許進(jìn).快速排序算法研究［J］.微電子學(xué)與計算機，2002(6):6－10.

［3］王穎，李肯立，李浪，等.縱橫多路并行歸并算法［J］.計算機研究與發(fā)展，2006，43(12):2180－2186.

［4］丁衛(wèi)群，計永昶，陳國良.一種基于MPP的并行歸并算法［J］.計算機研究與發(fā)展，1999，36(1):52－56.

［5］Barry Wilkinson，Michael Allen.并行程序設(shè)計［M］.北京:機械工業(yè)出版社，2005.