一個改進(jìn)的就地穩(wěn)定二路歸并算法

胡圣榮,楊文君

(1.華南農(nóng)業(yè)大學(xué) 工程基礎(chǔ)教學(xué)與訓(xùn)練中心，廣東 廣州 510642；2.懷雅遜大學(xué) 電子與計算機(jī)工程系，安大略 多倫多 M5B 2K3)

?

一個改進(jìn)的就地穩(wěn)定二路歸并算法

胡圣榮1,楊文君2

(1.華南農(nóng)業(yè)大學(xué) 工程基礎(chǔ)教學(xué)與訓(xùn)練中心，廣東 廣州 510642；2.懷雅遜大學(xué) 電子與計算機(jī)工程系，安大略 多倫多 M5B 2K3)

摘要：提出溢出隊列的概念，用于管理二路歸并過程中的動態(tài)存儲區(qū)，它位于第二歸并段的頭部，存放歸并時前段的較大者；對一個二路歸并算法進(jìn)行了改進(jìn)，將理順隊列改為理順溢出隊列，并保留了原算法簡便、就地進(jìn)行、穩(wěn)定、比較次數(shù)最優(yōu)的特點；進(jìn)行了二路歸并和二路歸并排序測試，結(jié)果表明歸并總長為n的兩個等長歸并段時移動次數(shù)約為n2/108，可減少到原算法的4/9。

關(guān)鍵詞：歸并；就地歸并；歸并排序；溢出隊列

在計算機(jī)相關(guān)學(xué)科中，有序區(qū)的歸并算法有重要意義，如用于排序問題的二路歸并排序。但經(jīng)典的歸并算法需要O(n)的輔助空間。

為此很多文獻(xiàn)研究附加空間少的甚至就地歸并的算法，其中采用了一些特殊的技術(shù)或技巧，如“內(nèi)部緩存”技術(shù)[1]、鄰塊交換的旋轉(zhuǎn)算法[1]、連續(xù)交換中的浮洞技術(shù)[1]等。不難發(fā)現(xiàn)，很多算法過于追求“就地”與“線性性能”，結(jié)果比較復(fù)雜，而線性因子也可能較大；還有些放棄了穩(wěn)定性。Geffert等的穩(wěn)定算法比較典型，最多m(t+1)+n/2t+o(m)次比較，5n+12m+o(m)次移動[1]，其中m≤n，t=[log2(n/m)]。這類算法中Kim的實現(xiàn)[2]有一定實用性，但仍很復(fù)雜。若放松嚴(yán)格的“就地”要求，允許O(log2n)的附加?？臻g，如Ellis和Markov的ShuffleMerge算法[3]，雖不是線性的，但簡潔實用。Dalkilic的實現(xiàn)[4]則進(jìn)一步提高了時空性能和實用性。

本文對一個就地歸并算法進(jìn)行了改進(jìn)，保持了原算法簡便、穩(wěn)定、就地進(jìn)行、比較次數(shù)最優(yōu)的特點，但移動次數(shù)可減少一半以上。

1算法

設(shè)二路歸并的初始?xì)w并段為A[i, j)、B[j, to)(它們存放于同一數(shù)組R中)。

算法Ⅰ[8]：對A、B段從前向后掃描，設(shè)當(dāng)前位置分別為i、p；在[j, p)之間形成動態(tài)存儲區(qū)，存儲歸并時A段大于B[p]者(它們后移而成，其值大于A段已歸并好的部分)，并組織成循環(huán)隊列。于是：

(1)若隊頭≤B[p]，則隊頭出隊(前移到A[i]位置)，原A[i]入隊(后移到原隊頭位置)，隊頭位置循環(huán)后移1位；

(2)若隊頭>B[p]，先理順隊列(隊頭開始的后段與前段交換，使隊頭位于緩沖區(qū)開始位置)，然后將B[p]前移到A[i]位置，原A[i]入隊(后移到B[p])，隊列長度增1，但隊頭位置不變。

以上方法在情況(2)時，入隊后隊列長度增1，由于是順序存儲，入隊前進(jìn)行了隊列理順操作(使入隊后隊列元素大小排列正常)，這在多次入隊時會導(dǎo)致隊列元素的多次反復(fù)移動。顯然若減少隊列的理順操作，就可減少移動量。

算法Ⅱ：修改算法Ⅰ，當(dāng)情況(2)隊頭>B[p]時，前部的A[i]入隊時仍存放到B[p]位置，但并不理順隊列，這時緩沖區(qū)中在循環(huán)隊列后又形成一個存儲區(qū)，不妨稱“溢出區(qū)”或“溢出隊列”。這時當(dāng)情況(1)隊頭≤B[p]，隊頭出隊時需要理順隊列，易見這只需理順溢出隊列即可：將它與循環(huán)隊列中隊頭開始的后段交換。交換后溢出區(qū)合并到了循環(huán)隊列中，循環(huán)隊列長度增加，(當(dāng)前)溢出區(qū)消失。

比較兩種理順操作，一種在入隊時進(jìn)行，一種在出隊時進(jìn)行；假設(shè)出、入隊概率相當(dāng)，則因歸并過程中循環(huán)隊列可能較長，隊頭之前的部分(平均)也就較長，而溢出隊列會相對短些，故理順溢出隊列的移動量會小些。后面的測試結(jié)果驗證了這種定性分析(大規(guī)模時可減少一半以上)。

與算法Ⅰ類似，歸并過程中可能出現(xiàn)兩種情況：

(1)若原B段已處理完，則理順隊列，歸并結(jié)束。

(2)若原A段已處理完，則理順隊列作為新的A段，與p開始的B段繼續(xù)歸并。

參見圖1，設(shè)循環(huán)隊列、溢出隊列長度分別為n、m，歸并算法如下：

L1：while(i

L2：if(i>=j) 結(jié)束返回;

L3：交換R[i]和R[j];f=0,n=1,m=0;//初始隊列i++,p=j+1;

L4：while(i

if(隊頭<=R[p]) {

if(m>0) {理順溢出隊列;f=f+m;n=p-j;m=0;}

隊頭出隊并置于R[i]，原R[i]入隊，i++;}

else {

交換R[i]和R[p];

if(f==0) n++; else m++;

i++;p++;}

L5：if(p>=to) {

理順隊列;交換R[i,j)和R[j,p);結(jié)束返回;}

else {理順隊列;i=j;j=p;轉(zhuǎn)L1;}

其中理順溢出隊列是交換R[j+f, p-m)和R[p-m, p)，理順隊列是交換R[j, j+f)和R[j+f, p-m)，它們是相鄰塊交換，可用旋轉(zhuǎn)算法[1]實現(xiàn)，它交換長度為m、n的相鄰兩塊移動量為m+n+GCP(m,n)，其中GCP為求最大公約數(shù)。

圖1采用溢出隊列的二路歸并

以上兩個算法，每比較一次就有一個元素到位，故若歸并長度分別為m、n的兩個有序段，比較次數(shù)最多m+n-1次。如果隊列中不出現(xiàn)理順操作，則A段元素最多入隊、出隊1次，加上B段元素的移動，移動量最好O(m+n)；但一般要多次理順隊列，移動量最壞O(mn)。兩個算法都是穩(wěn)定的。

2性能分析與測試

這里進(jìn)行了兩種測試：(1)歸并算法測試，取2個長度都為n的隨機(jī)序列，分別排序(得到有序序列)后再進(jìn)行歸并，考察歸并的比較次數(shù)、移動次數(shù)等[2-5]，結(jié)果見表1。(2)歸并排序測試，將歸并算法用于歸并排序，通過排序的比較次數(shù)、移動次數(shù)間接考察歸并的比較次數(shù)、移動次數(shù)，結(jié)果見表2。表1、表2中C、M表示關(guān)鍵字比較次數(shù)(106)、移動次數(shù)(106)；三個算法的比較次數(shù)相同。

測試時隨機(jī)序列的生成采用文[6]的長周期隨機(jī)函數(shù)，各規(guī)模下測試若干組后對結(jié)果平均。各組隨機(jī)序列是在長周期隨機(jī)序列中依次截取(不改變種子)。組數(shù)的多少自動調(diào)整：最多106組，以該規(guī)?？偱判驎r間不超過1分鐘為準(zhǔn)，但最少10組。算法[5]改自文[5](原文可能排印瑕疵，比較次數(shù)有多余)。

表1　歸并測試結(jié)果(/106)

表2　歸并排序測試結(jié)果(/106)

采用更多測試數(shù)據(jù)(略)，對表1、表2進(jìn)行類似文[7]的穩(wěn)定性擬合，結(jié)果為：

對表1，算法[5]、算法Ⅰ、算法Ⅱ歸并的比較次數(shù)約為2n，移動次數(shù)分別約為n2/4+1.85n、n2/12+6.6n、n2/27+7.8n。若n表示歸并后的總長度(兩段分別長n/2)則相應(yīng)擬合結(jié)果分別為n、n2/16+0.92n、n2/48+3.3n、n2/108+3.9n。

對表2，算法[5]、算法Ⅰ、算法Ⅱ歸并排序的比較次數(shù)約為1.44nln(n)-1.21n，移動次數(shù)分別約為n2/8+1.33nln(n)、n2/24+4.8nln(n)、n2/54+5.5nln(n)。

以上擬合結(jié)果高次項(主項)穩(wěn)定些，低次項略差(原始數(shù)據(jù)中去掉占主導(dǎo)的高次項后剩余部分精度差，波動較大)。易見，擬合結(jié)果符合歸并和歸并排序的復(fù)雜性關(guān)系[8]：

f(n)=T(n)-2T(n/2)

如對算法Ⅱ，由歸并排序移動次數(shù)導(dǎo)出的歸并移動次數(shù)為：

f(n)=T(n)-2T(n/2)

這與單獨歸并測試的擬合結(jié)果是一致的。

由測試數(shù)據(jù)及其擬合主項可見，當(dāng)規(guī)模足夠大后，算法Ⅰ的移動次數(shù)約為算法[5]的4/12=1/3，減少了2/3；而改進(jìn)的算法Ⅱ移動次數(shù)約為算法Ⅰ的12/27=4/9，又減少了5/9，即移動次數(shù)又可減少一半以上。

3結(jié)論

引入溢出隊列對歸并算法Ⅰ的緩沖區(qū)隊列進(jìn)行改進(jìn)，將理順隊列改為理順溢出隊列，結(jié)果表明對減少移動次數(shù)是有效的：在保持算法簡便、穩(wěn)定、就地進(jìn)行、比較次數(shù)最優(yōu)的情況下，當(dāng)規(guī)模足夠大后，移動次數(shù)約下降到原算法的4/9，減少了一半以上。

參考文獻(xiàn)：

[1] Geffert V, Katajainen J, Pasanen T. Asymptotically efficient in-place merging[J]. Theoretical Computer Science, 2000, 237(1): 159-181.

[2] Kim P S, Kutzner A. On optimal and efficient in place merging[M]//SOFSEM 2006: Theory and Practice of Computer Science. Springer Berlin Heidelberg, 2006: 350-359.

[3] Ellis J, Markov M. In situ, stable merging by way of the perfect shuffle[J]. The Computer Journal, 2000, 43(1): 40-53.

[4] Dalkilic M E, Acar E, Tokatli G. A simple shuffle-based stable in-place merge algorithm[J]. Procedia Computer Science, 2011, 3: 1049-1054.

[5] 范時平, 聶永萍, 汪林林. 一種基于數(shù)據(jù)塊交換的快速穩(wěn)定原地歸并算法[J]. 重慶郵電學(xué)院學(xué)報 (自然科學(xué)版), 2004, 16(4): 93-93.

[6] 胡圣榮. 關(guān)于排序算法的隨機(jī)輸入序列[J]. 武漢理工大學(xué)學(xué)報, 2006, 28(9): 105-107.

[7] 胡圣榮. 關(guān)于排序效率的數(shù)值估計[J]. 廣州城市職業(yè)學(xué)院學(xué)報, 2008, 2(1): 61-64.

[8] 胡圣榮. 一個新的就地穩(wěn)定歸并算法[J]. 河池學(xué)院學(xué)報, 2014, 34(5): 49-52.

(責(zé)任編輯夏侯國論)

收稿日期：2016-05-27

作者簡介：胡圣榮，男，華南農(nóng)業(yè)大學(xué)工程基礎(chǔ)教學(xué)與訓(xùn)練中心教授，博士。

中圖分類號：TP311.12

文獻(xiàn)標(biāo)識碼：A

文章編號：1674-0408(2016)02-0001-04

An improved in-place stable 2-way merge algorithm

HU Sheng-rong1，YANG Wen-jun2

(1. Engineering Fundamentals Teaching and Training Centre, South China Agricultural University, Guangzhou 510642，China;2. Department of Electrical and Computer Engineering, Ryerson University, Toronto Ontario M5B 2K3, Canada)

Abstract：The concept of overflow queue is proposed to manage the dynamical storage buffer, which is located in the head part of the second merge segment and formed by larger elements of the first merge segment in the merging process. The corresponding improved algorithm replaces queue reforming with overflow queue reforming, and retains the good characteristics of the original 2-way merge algorithm, it is simple, in-place, stable, and optimal in comparisons. The algorithm was tested through both merge and merge sort, the results showed the amount of key movement or assignment of the improved algorithm in merging two segments of equal length with total length of n is about n2/108, which is 4/9 of the original algorithm.

Key words：merge; in-place merge; merge sort; overflow queue