胡圣榮,楊文君

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

?

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

胡圣榮1,楊文君2

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

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

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

在計(jì)算機(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)次移動(dòng)[1]，其中m≤n，t=[log2(n/m)]。這類算法中Kim的實(shí)現(xiàn)[2]有一定實(shí)用性，但仍很復(fù)雜。若放松嚴(yán)格的“就地”要求，允許O(log2n)的附加?？臻g，如Ellis和Markov的ShuffleMerge算法[3]，雖不是線性的，但簡(jiǎn)潔實(shí)用。Dalkilic的實(shí)現(xiàn)[4]則進(jìn)一步提高了時(shí)空性能和實(shí)用性。

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

1算法

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

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

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

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

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

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

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

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

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

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

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

L1：while(i

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

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

L4：while(i

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

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

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

else {

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

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

i++;p++;}

L5：if(p>=to) {

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

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

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

圖1采用溢出隊(duì)列的二路歸并

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

2性能分析與測(cè)試

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

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

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

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

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

對(duì)表1，算法[5]、算法Ⅰ、算法Ⅱ歸并的比較次數(shù)約為2n，移動(dòng)次數(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。

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

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

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

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

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

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

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

3結(jié)論

引入溢出隊(duì)列對(duì)歸并算法Ⅰ的緩沖區(qū)隊(duì)列進(jìn)行改進(jìn)，將理順隊(duì)列改為理順溢出隊(duì)列，結(jié)果表明對(duì)減少移動(dòng)次數(shù)是有效的：在保持算法簡(jiǎn)便、穩(wěn)定、就地進(jìn)行、比較次數(shù)最優(yōu)的情況下，當(dāng)規(guī)模足夠大后，移動(dòng)次數(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í)平, 聶永萍, 汪林林. 一種基于數(shù)據(jù)塊交換的快速穩(wěn)定原地歸并算法[J]. 重慶郵電學(xué)院學(xué)報(bào) (自然科學(xué)版), 2004, 16(4): 93-93.

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

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

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

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

收稿日期：2016-05-27

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

中圖分類號(hào)：TP311.12

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

文章編號(hào)：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