胡圣榮

(華南農(nóng)業(yè)大學(xué) 工程學(xué)院，廣東 廣州 510642)

希爾排序效率的真實(shí)性擬合嘗試
——Sedgewick增量序列(1982)

胡圣榮

(華南農(nóng)業(yè)大學(xué) 工程學(xué)院，廣東 廣州 510642)

為了對復(fù)雜性未知的希爾排序算法進(jìn)行合理、可信的數(shù)值估計(jì)，提出擬合不變性結(jié)合擬合準(zhǔn)確性和顯著性的擬合思想和方法，并對采用Sedgewick增量序列4*22i+3*2i+1的希爾排序算法的平均比較次數(shù)進(jìn)行了數(shù)值估計(jì)，從cnαlnβ(n)形式開始，在規(guī)模為104～108的測試數(shù)據(jù)的不同區(qū)段分別擬合，根據(jù)擬合參數(shù)的變動(dòng)特點(diǎn)，進(jìn)行合理推斷并再次擬合及驗(yàn)證，從而逐步分離和確定出α=1,c=1,β=1.41，最終獲得了對各區(qū)段擬合幾乎不變的結(jié)果nln1.41(n).擬合方法本身的正確性用已知結(jié)果的排序數(shù)據(jù)進(jìn)行了驗(yàn)證.

排序；希爾排序；算法；擬合；擬合不變性

0 引言

自從1959年D.L.Shell提出希爾排序算法[1]以來，該類算法的理論分析一直都沒有很好解決[2]，有關(guān)研究大致有三方面：①理論上下限估計(jì)，如文獻(xiàn)[3]；②數(shù)值估計(jì)，如文獻(xiàn)[4-6]；③最優(yōu)增量研究，如文獻(xiàn)[7].一般地，對具體的增量序列，除少數(shù)特殊情況外都沒有理論結(jié)果，通常進(jìn)行數(shù)值估計(jì)，即采用大量隨機(jī)輸入，對輸出結(jié)果平均后進(jìn)行數(shù)據(jù)擬合.作者發(fā)現(xiàn)，這些數(shù)值估計(jì)，純粹也只能看做已有數(shù)據(jù)的一個(gè)外在的經(jīng)驗(yàn)公式，并不代表數(shù)據(jù)內(nèi)部的真實(shí)變化規(guī)律.比如，增加新的數(shù)據(jù)點(diǎn)，特別是規(guī)模更大的新數(shù)據(jù)點(diǎn)后，新的擬合結(jié)果(公式中的有關(guān)系數(shù)等)一般會(huì)有明顯變動(dòng)，而實(shí)際的平均復(fù)雜性應(yīng)該是規(guī)模的一個(gè)確定不變的函數(shù)關(guān)系.

本文試圖從實(shí)驗(yàn)數(shù)據(jù)中得到比較可信的有可能反映真實(shí)規(guī)律的擬合結(jié)果，介紹了擬合原理和方法，對Sedgewick增量序列(1982)的擬合結(jié)果具有很好的擬合不變性.

1 擬合思想與方法

1.1 擬合準(zhǔn)確性

所見文獻(xiàn)一般是對測試數(shù)據(jù)，按一定的擬合式進(jìn)行一次性的擬合，主要考察擬合的準(zhǔn)確性.如對采用Hibbard序列2t-1，即1, 3, 7, 15, 31, …和Knuth序列(3t-1)/2，即1,4,13,40,121,…的希爾排序，Knuth采用cnα形式擬合，M.A.Weiss采用c1n5/4+c2n+c3n3/4+c4n2/4+c5n1/4+c6形式，后者比前者準(zhǔn)確[5].Cotta用an2+bn和anb都能很好擬合Knuth序列[6].顯然，采用不同的擬合式必將得到不同的結(jié)果，其中總有可能找到比當(dāng)前更準(zhǔn)確的，特別地，采用插值多項(xiàng)式可通過所有樣點(diǎn)，但這顯然并不意味著“最準(zhǔn)確”.

表1 快速排序的平均比較次數(shù) /106

那么，對同一數(shù)據(jù)的多種擬合，如何判斷誰更“真實(shí)”呢？作者在文獻(xiàn)[8]中提出過一個(gè)觀點(diǎn)：擬合準(zhǔn)確性不一定代表真實(shí)性.以快速排序?yàn)槔?為某快速排序算法(快速排序有多種實(shí)現(xiàn))對1000組隨機(jī)序列排序后的平均結(jié)果.

對此數(shù)據(jù)，發(fā)現(xiàn)很多擬合式都能很好地吻合，如y=cnα、cnαlnβ(n)ln[ln(n)]、cnαlnβ(n)、cnln(n)、cnαln(n)、cnln(n)等(轉(zhuǎn)換為適當(dāng)形式后進(jìn)行線性擬合).擬合后分別求出y-yi，依次為149.91、0.612 05、0.632 00、14.752、24.584、8.959 1，其中形式較復(fù)雜的cnαlnβ(n)ln[ln(n)]擬合誤差最小，而較接近理論結(jié)果的cnln(n)并不是很好.所以擬合“準(zhǔn)確”不一定真實(shí)，反之，擬合不太精確的曲線，未必不真實(shí).當(dāng)然，準(zhǔn)確性明顯較差的形式cnα優(yōu)先值得懷疑.

1.2 擬合顯著性

另一方面，從統(tǒng)計(jì)學(xué)觀點(diǎn)看，擬合還有一個(gè)顯著性的問題[9]，一般考察擬合參數(shù)的t值、P值和總體結(jié)果的R2、AdjustedR2、F值、SignificanceF等，其中t值和F值越大越好，P值和SignificanceF越小越好，R2越接近1越好.

這里進(jìn)一步指出：擬合顯著性也不一定代表真實(shí)性.比如SignificanceF，上面6個(gè)擬合的結(jié)果分別為6.529 8E-16、7.046 8E-21、3.230 2E-25、1.882 8E-15、3.336 1E-21、8.389 4E-22，它們都很顯著，其中最顯著的是cnαlnβ(n)(此時(shí)α=0.992 20、β=1.194 8)，但它并不比cnlnβ(n)(此時(shí)β=1.0067)更真實(shí)，因?yàn)榭焖倥判虻睦碚摻Y(jié)果為O(nln(n)).當(dāng)然，擬合參數(shù)明顯不顯著的cnαlnβ(n)ln[ln(n)](其中l(wèi)n(c)、的P值為0.148 79和0.641 23較大，而其它幾個(gè)擬合式的參數(shù)P值至少在10-7以下)優(yōu)先值得懷疑(增加更多數(shù)據(jù)點(diǎn)擬合會(huì)顯著些).

1.3 擬合穩(wěn)定性

為了判斷擬合式的真實(shí)性，作者在文獻(xiàn)[8]提出擬合不變性的思想，即若該擬合式是真實(shí)的，則它在數(shù)據(jù)點(diǎn)的各子區(qū)間應(yīng)該有幾乎相同的擬合結(jié)果.這是必要條件，但顯然沒有該特點(diǎn)的擬合，真實(shí)性值得懷疑.

為了獲得擬合不變的結(jié)果，需要將數(shù)據(jù)分段，再分別擬合.根據(jù)各段上擬合參數(shù)表現(xiàn)出的特點(diǎn)，進(jìn)行合理推斷以去除數(shù)據(jù)的“毛刺”(波動(dòng))，得到簡化形式，然后再次擬合并驗(yàn)證(參數(shù)是否穩(wěn)定、擬合是否顯著等).這個(gè)過程可能要反復(fù)多次，具體實(shí)施時(shí)還可結(jié)合擬合準(zhǔn)確性和顯著性進(jìn)行.按此思想，文獻(xiàn)[8]對采用Hibbard序列和Knuth序列的希爾排序，擬合結(jié)果分別為cn1.26ln-0.5(n)和cn1.25ln-0.5(n)，特別地，當(dāng)規(guī)模n不是很大時(shí)，近似為(n1.26)和(n1.25)，這便是Knuth和M.A.Weiss的結(jié)果[5].

表2 希爾排序的平均比較次數(shù) /106

表3 區(qū)間分段情況

2 擬合過程

Sedgewick在1982年設(shè)計(jì)了一個(gè)增量序列4*22i+3*2i+1(i≥0)，即1, 8, 23, 77, 281, …，效果優(yōu)于Hibbard序列和Knuth序列，上界為O(n4/3)[2]，但具體平均情況未知.這里取該增量序列進(jìn)行希爾排序.因測試規(guī)模大，測試序列長，為避免序列數(shù)據(jù)重復(fù)(C/C++系統(tǒng)的隨機(jī)函數(shù)rand()只生成0～327 67的隨機(jī)數(shù))，隨機(jī)序列的生成采用文獻(xiàn)[10]的長周期隨機(jī)函數(shù)，但與之不同的是，這里不通過改變種子來獲得不同序列，而是在長周期隨機(jī)序列中依次截取所需長度的子序列；測試組數(shù)也自動(dòng)選?。鹤疃?06組，以當(dāng)前規(guī)模總排序時(shí)間不超過1 min為準(zhǔn)(該時(shí)間根據(jù)硬件條件設(shè)置)但最少10組.測試結(jié)果見表2.

區(qū)間分段如下：分別從低到高分4段、2段、1段，見表3所示.其中區(qū)段A、B、C、D可考察規(guī)模增加時(shí)擬合參數(shù)是否穩(wěn)定以及變化趨勢，其它幾段可考察數(shù)據(jù)點(diǎn)增加時(shí)擬合參數(shù)是否穩(wěn)定以及變化趨勢.

表4 分段擬合及參數(shù)的確定(表2數(shù)據(jù))

下面對各段分別擬合.由于增量序列有按幾何級(jí)數(shù)變化的特點(diǎn)或趨勢，根據(jù)文獻(xiàn)[8]的思想，擬合形式仍取為cnαlnβ(n)，擬合結(jié)果見表4中的基本形式.

從表4基本形式的結(jié)果看到，各區(qū)段上參數(shù)ln(c)變動(dòng)較大、β次之，而α較穩(wěn)定，基本在1上下，于是推測α=1，重新擬合，結(jié)果見表4中α=1部分.這時(shí)參數(shù)β也較穩(wěn)定了，而ln(c)基本在0附近變動(dòng)(即c接近1)，再次推測c=1后重新擬合，結(jié)果見表4最后一行.這時(shí)參數(shù)β非常穩(wěn)定，約1.408～1.409.

以上區(qū)間分段似乎較特殊，實(shí)際上其它分段結(jié)果都類似，如改變段的開始、改變段的長度等(數(shù)據(jù)略).另外，對數(shù)據(jù)序列細(xì)化，如1，1.778，3.162，5.623，10，…，以及其它數(shù)據(jù)序列，如1，2，4，6，8，10，…，結(jié)果也類似(數(shù)據(jù)略，故本文表2僅取了少量數(shù)據(jù)).

至于擬合的顯著性，表4涉及的3個(gè)擬合式(即cnαlnβ(n)、cnlnβ(n)、nlnβ(n))都很顯著，如對全段擬合的SignificanceF分別為3.075 7E-20、2.100 4E-15、5.069 4E-23.

綜合以上分析，表2數(shù)據(jù)的最終擬合結(jié)果為y=nln1.41(n).

表5 直接插入排序的平均比較次數(shù) /106

表6 分段擬合及參數(shù)的確定(表5數(shù)據(jù))

3 擬合方法的驗(yàn)證

下面用已知結(jié)果的數(shù)據(jù)來驗(yàn)證一下上述擬合方法.對表1快速排序的不變性擬合略為繁瑣一些，它需要兩項(xiàng)形式y(tǒng)=cnαlnβ(n)+n才能穩(wěn)定，這種情況擬另文介紹.作者發(fā)現(xiàn)，簡單排序都能一項(xiàng)穩(wěn)定擬合.以直接插入排序?yàn)槔瑪?shù)據(jù)見表5.該排序效率低，規(guī)模大時(shí)排序時(shí)間太長，故測試時(shí)所取數(shù)據(jù)組數(shù)依次遞減：規(guī)模量級(jí)為102、103、104、105、106時(shí)分別取10 000、1 000、1 000、100、1組.仍從cnαlnβ(n)形式開始，擬合結(jié)果見表6.

具體過程是，先由基本形式的擬合結(jié)果估計(jì)α=2；令α=2重新擬合后估計(jì)β=0；最后令α=2,β=0再擬合，結(jié)果參數(shù)c非常穩(wěn)定，約0.250最后結(jié)果為0.250 n2，而理論結(jié)果是n(n-1)/40.25 n2.這個(gè)過程與表4幾乎一樣.

4 結(jié)論

希爾排序的平均復(fù)雜性是規(guī)模n的某個(gè)確定函數(shù)，如果擬合結(jié)果是真實(shí)的，則它在各數(shù)據(jù)區(qū)段上應(yīng)該有幾乎相同的擬合結(jié)果.擬合不變性思想對判斷或推測擬合真實(shí)性提供了一種值得嘗試的可行的方法.

對采用Sedgewick增量序列4*22i+3*2i+1的希爾排序算法，本文的擬合結(jié)果nln1.41(n)具有很好的擬合不變性和顯著性，雖仍屬經(jīng)驗(yàn)估計(jì)，但很可能比其它結(jié)果更接近真實(shí).

下一步的工作是探討合適的其它擬合式及組合擬合式，因?yàn)樽髡叩墓ぷ鞅砻鲾M合式cnαln(n)對其它幾個(gè)測試序列不像本文這樣穩(wěn)定(即使增量類似，但Pratt序列[2-3]除外，對其擬合時(shí)很穩(wěn)定并能得到理論值cnln2(n)[3]，數(shù)據(jù)略).當(dāng)然，也可能出現(xiàn)幾個(gè)擬合式都較穩(wěn)定如何分辨的問題.另一個(gè)要做的工作是對穩(wěn)定擬合結(jié)果的理論證明.

[1]ShellDL.Ahigh-speedsortingprocedure[J].CommunicationsoftheACM,1959,2(7):30-32.

[2]SedgewickR.AnalysisofShellsortandRelatedAlgorithms[J].EuropeanSymposiumonAlgorithms,1996:1-11.

[3]JiangT,LiM,VitányiP.Alowerboundontheaverage-casecomplexityofShellsort[J].JACM,2000,47(5):905-911.

[4]SandersP,FleischerR.Asymptoticcomplexityfromexperiments?Acasestudyforrandomizedalgorithms[C]//AlgorithmEngineering,SpringerBerlinHeidelberg,2001:135-146.

[5]WeissMA.ShortNoteEmpiricalstudyoftheexpectedrunningtimeofShellsort[J].TheComputerJournal,1991,34(1):88-91.

[6]CottaC,MoscatoP.Amixedevolutionary-statisticalanalysisofanalgorithm'scomplexity[J].AppliedMathematicsLetters,2003,16(1):41-47.

[7]CiuraM.Bestincrementsfortheaveragecaseofshellsort[J].Lecturenotesincomputerscience,2001:106-117.

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

[9]何曉群，劉文卿.應(yīng)用回歸分析[M].北京：中國人民大學(xué)出版社，2001.

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

責(zé)任編輯：時(shí)凌

AttemptatCredibleEmpiricalStudyofShellsort——Sedgewick′s Increment Sequence in 1982

HU Shengrong

(College of Engineering,South China Agricultural University,Guangzhou 510642,China)

In order to estimate unknown complexity of Shellsort reasonably and credibly,this paper suggested combination of fitting invariability with fitting precision and significance, and accordingly the average number of comparisons of Shellsort with Sedgewick′s increment sequence 4*22i+3*2i+1 was obtained about tonln1.41(n),which was originated fromcnαlnβ(n),with parameter inferring from its appearance in different data segments among size of 104to 108,refitting and validating , the values ofα=1,c=1,β=1.41 were determined progressively. The correctness of the fitting method proposed was verified by data with known complexity.

sort; shellsort; algorithm;fit;fitting invariability

2014-05-26.

胡圣榮(1967- )，男，博士，教授，主要從事計(jì)算機(jī)數(shù)值計(jì)算相關(guān)問題研究.

TP311.12

A

1008-8423(2014)02-0218-04