生成與查詢螺旋矩陣的在線算法研究

彭海洋

(河南牧業(yè)經(jīng)濟(jì)學(xué)院,河南 鄭州 475000)

1 螺旋矩陣的概念與其傳統(tǒng)離線算法

矩陣在計(jì)算機(jī)中通常用于映射線性空間內(nèi)的運(yùn)動(dòng),特別是對(duì)于圖形學(xué)方面能夠方便地進(jìn)行變換等操作。 螺旋矩陣作為矩陣的一種,自身的規(guī)律性可使其作為密鑰等應(yīng)用于加密或其他算法中[1]。 螺旋矩陣即一個(gè)由整數(shù)填充的二維矩陣,從左上角的值為初值,向順時(shí)針?lè)较蛞来芜f增,按照“右-下-左-上”的順序依次對(duì)矩陣各項(xiàng)賦值,如此循環(huán)直至填充矩陣所有空間。對(duì)于空間而言,一般將一個(gè)n×n大小的矩陣稱為n階矩陣。 螺旋矩陣的各項(xiàng)值會(huì)隨階數(shù)n的不同產(chǎn)生變化,如圖1 所示。

圖1 4 階螺旋矩陣和5 階螺旋矩陣

在實(shí)際應(yīng)用中,螺旋矩陣的階數(shù)具有任意性,通常需要以指定階數(shù)作為參數(shù),由此生成一個(gè)特定階數(shù)的矩陣。 目前,構(gòu)建特定階數(shù)的螺旋矩陣可使用模擬算法:定義矩陣邊長(zhǎng)為n,以一個(gè)二維數(shù)組matrix[n][n]作為儲(chǔ)存矩陣的數(shù)據(jù)結(jié)構(gòu)。 從matrix[1][1]開(kāi)始,按照規(guī)律依次將一個(gè)遞增的值賦予各項(xiàng)[2]。 如算法1 所示,這種預(yù)先將矩陣內(nèi)容存儲(chǔ)在內(nèi)存中的算法,可稱為離線算法。

對(duì)于生成螺旋矩陣問(wèn)題,可利用算法1 將矩陣構(gòu)建完成后,依次循環(huán)輸出各項(xiàng)值。 由于n階矩陣共有n2項(xiàng),所以在理想情況下利用此算法,構(gòu)建時(shí)將循環(huán)n2次,輸出時(shí)再次循環(huán)n2次。 設(shè)算法中所有語(yǔ)句頻度之和為f(n),則有:

對(duì)于查詢螺旋矩陣問(wèn)題,同樣可先行構(gòu)建完整矩陣。 由于這些算法一般由高級(jí)程序設(shè)計(jì)語(yǔ)言編寫(xiě),且作為儲(chǔ)存結(jié)構(gòu)的二維數(shù)組是順序表,各項(xiàng)物理地址相鄰,具有隨機(jī)存儲(chǔ)的特性。 因此,無(wú)須循環(huán)即可進(jìn)入所需地址空間并返回相應(yīng)值。 即在項(xiàng)數(shù)為n2的螺旋矩陣中,查詢某項(xiàng)值的平均查找長(zhǎng)度為:

由此可見(jiàn),在查詢問(wèn)題中,語(yǔ)句頻度為:

當(dāng)n充分大時(shí),f1(n) 與f2(n)皆與n2同階,記作T(n)=O(f(n))= O(n2)。 所以此算法在這兩種問(wèn)題上的時(shí)間復(fù)雜度同為O(n2)。

僅從時(shí)間效率上來(lái)看,雖然算法1 的求解速度尚可接受,但在整體上依然存在局限性。 由于在求解中占用的臨時(shí)工作單位數(shù)為n2,則在生成與查詢問(wèn)題中,對(duì)每一項(xiàng)都存在n2-1 規(guī)模的空間浪費(fèi)。 以C++語(yǔ)言為例,通過(guò)實(shí)驗(yàn)得知,在VC 環(huán)境下,若以在棧區(qū)分配數(shù)組空間的方式編寫(xiě)程序,當(dāng)n大于10 000 時(shí)就會(huì)因棧內(nèi)存不足導(dǎo)致編譯終止,即無(wú)法計(jì)算10 000 階及以上階數(shù)的螺旋矩陣。

2 螺旋矩陣在線算法的假設(shè)與分析

雖然可以通過(guò)在堆區(qū)手動(dòng)分配內(nèi)存的方式計(jì)算更大階數(shù)的螺旋矩陣,但在實(shí)際應(yīng)用中求解較大階數(shù)的螺旋矩陣所需時(shí)間與空間的代價(jià)或不可接受。 算法1的不足在于借用了龐大的輔助數(shù)組,通過(guò)觀察可發(fā)現(xiàn),螺旋矩陣的每一項(xiàng)數(shù)值僅與其矩陣階數(shù)有關(guān)。 即當(dāng)螺旋矩陣的階數(shù)n被確定后,矩陣第i項(xiàng)的值隨之確定,此值記作matrixI。 同時(shí)無(wú)論階數(shù)n如何變化,矩陣排布規(guī)律依然不變。 所以,可先行假設(shè)matrixI與其項(xiàng)數(shù)i對(duì)于所在矩陣的階數(shù)n有簡(jiǎn)單對(duì)照關(guān)系,且此對(duì)照關(guān)系能夠封裝為函數(shù),在程序中通過(guò)少量計(jì)算求值。 如式(4)所示:

在推導(dǎo)SpiralMatrix 函數(shù)的具體算法之前,可先羅列目前可用的參數(shù)以供輔助研究:(1)當(dāng)前矩陣項(xiàng)數(shù)i:由用戶查詢時(shí)輸入,或在生成時(shí)作為循環(huán)參數(shù)依次傳入函數(shù)。 (2)矩陣階數(shù)n:此值由用戶指定,控制當(dāng)前矩陣大小。

求解螺旋矩陣第i項(xiàng)值時(shí),可將項(xiàng)數(shù)i轉(zhuǎn)化為坐標(biāo)xy后計(jì)算。 由于矩陣外環(huán)的值可由四角定位,其值也與階數(shù)n有明顯關(guān)系,但對(duì)于內(nèi)層環(huán)而言,各環(huán)變換皆不相同,難以通過(guò)簡(jiǎn)單計(jì)算求值。 觀察規(guī)律后發(fā)現(xiàn):一個(gè)階數(shù)為n的螺旋矩陣,皆能拆為「n/2層循環(huán)遞增的單環(huán),且內(nèi)環(huán)初始值為外環(huán)末值+1。 即矩陣可拆分為多層單環(huán),求解內(nèi)環(huán)時(shí),可將其內(nèi)環(huán)作為階數(shù)是當(dāng)前環(huán)大小的矩陣外環(huán),求值后再次累加各外環(huán)末值,為方便計(jì)算,本文將最外環(huán)定義為0 環(huán)。 具體如圖2 所示。

圖2 螺旋矩陣各項(xiàng)空間關(guān)系

于是,對(duì)于一種用于生成與查詢螺旋矩陣的在線算法,需要解決以下幾個(gè)問(wèn)題:(1)輸入項(xiàng)數(shù)i,得到對(duì)應(yīng)坐標(biāo)xy;(2)通過(guò)坐標(biāo)得到當(dāng)前項(xiàng)所在層數(shù);(3)求解在相應(yīng)階數(shù)的螺旋矩陣中,保證xy坐標(biāo)為其外環(huán)時(shí)所對(duì)應(yīng)的值;(4)循環(huán)累加各外環(huán)末值;(5)返回最終值。 若以算法方式描述,如算法2 與算法3 所示。

3 螺旋矩陣在線算法的推導(dǎo)

3.1 由項(xiàng)數(shù)i 計(jì)算對(duì)應(yīng)坐標(biāo)

本文為方便理解,設(shè)置“1”為初始值,代替計(jì)算機(jī)常用初值“0”。 在可視為二維數(shù)組的矩陣中,當(dāng)前項(xiàng)數(shù)值每增大一個(gè)階數(shù)值(矩陣邊長(zhǎng)),其y坐標(biāo)就增加1,所以“項(xiàng)數(shù)i/階數(shù)n”的商即為第i項(xiàng)所對(duì)應(yīng)y坐標(biāo)。同樣,二者相除后所得余數(shù)即為x坐標(biāo)。

在大多編程語(yǔ)言中可通過(guò)“%”運(yùn)算符直接求得余數(shù),但當(dāng)被除數(shù)同為階數(shù)時(shí),即當(dāng)目標(biāo)項(xiàng)位于矩陣右邊界時(shí),所得商為0。 為了保持算法的統(tǒng)一,盡量將需要判斷的地方以數(shù)學(xué)方式計(jì)算。 所以在進(jìn)行除法與求余操作前,可先將項(xiàng)數(shù)i值-1,使“0”暫時(shí)作為初值代入計(jì)算,最后將結(jié)果+1,補(bǔ)回先前扣除值。 計(jì)算公式如式(5)與式(6)所示。

3.2 由二維坐標(biāo)計(jì)算當(dāng)前所在層

明顯看出,階數(shù)為n的螺旋矩陣最大層數(shù)為「n/2,此值記作deep,如式(7)所示。 同時(shí),橫縱坐標(biāo)皆為deep的項(xiàng)即為所在矩陣的中心點(diǎn)。 所以若要計(jì)算當(dāng)前坐標(biāo)所在層數(shù),只需計(jì)算與中心坐標(biāo)的距離,再用最大層數(shù)deep減去該值。

這里所求距離基于矩陣空間,與計(jì)算物理空間距離不同。 首先計(jì)算x坐標(biāo)與y坐標(biāo)相對(duì)中心線的距離,然后比較兩者大小,其中與中心線較遠(yuǎn)的值為當(dāng)前坐標(biāo)在矩陣空間下相較其矩陣中心的距離,即當(dāng)前所在層,或稱當(dāng)前所在深度,記作curDeep。 本文設(shè)定最外層的深度為0,所以在得到curDeep的結(jié)果后再次-1。 如式(8)所示。

但是,通過(guò)實(shí)踐發(fā)現(xiàn),式(7)的求解算法只在奇數(shù)階的矩陣中能夠得到正確值。 對(duì)于偶數(shù)矩陣而言,其中心坐標(biāo)并不對(duì)應(yīng)任何一項(xiàng)。 從空間上看,由螺旋矩陣最后4 項(xiàng)包圍。 所以,式(7)會(huì)將本處同一層的4 項(xiàng)計(jì)算出不同的深度。 解決方案是拋棄層數(shù)只能為整數(shù)的固有思維,將偶數(shù)階的層數(shù)設(shè)定在兩個(gè)整數(shù)之間,即為層數(shù)deep額外增加0.5。 同樣,為保持算法統(tǒng)一,可將奇偶數(shù)的判定值取反后作為額外增加值的權(quán)重。 改進(jìn)后的算法如式(9)所示。

3.3 求解坐標(biāo)為外環(huán)時(shí)的數(shù)值

當(dāng)前xy坐標(biāo)值是基于n階矩陣所對(duì)應(yīng)的空間位置,若將所處位置視為外環(huán),則必須將“此處深度為0”作為條件求得所符合的新階數(shù),同時(shí)計(jì)算基于此階數(shù)下對(duì)應(yīng)的坐標(biāo)。 通過(guò)觀察發(fā)現(xiàn),當(dāng)前深度每增加1,目標(biāo)階數(shù)隨之減少2。 因?yàn)楹罄m(xù)仍需要完整矩陣階數(shù)n,所以新定義當(dāng)前階數(shù)為curN,并由式(10)賦值。

坐標(biāo)方面,首先設(shè)定矩陣坐標(biāo)原點(diǎn)在左上角,定義為(1,1)。 則坐標(biāo)的更新實(shí)際上是將坐標(biāo)原點(diǎn)由(1,1)更改為(curDeep,curDeep)的操作,僅需要通過(guò)與上文的當(dāng)前深度值curDeep相減,即可正確更新坐標(biāo)。 由于先前坐標(biāo)不再使用,為節(jié)省空間可直接修改坐標(biāo)值。 如式(11)所示。

當(dāng)xy坐標(biāo)原先就處于外環(huán)時(shí),所減去的深度值為0,保持其值不變。 這就是本文定義最外環(huán)深度為0 的原因。

現(xiàn)在,問(wèn)題可暫時(shí)轉(zhuǎn)化為:一個(gè)寬度為curN的四邊環(huán),各值以順時(shí)針?lè)捶较蜻f增,保證xy在其環(huán)上,求對(duì)應(yīng)的值。

對(duì)于每一個(gè)環(huán),初值總為1,末值可看作從初值累加四次邊長(zhǎng)-1 的值,即curN-1,記作last, 由式(12)賦值。

為方便研究,可先在空間上將環(huán)從左上角到右下角分開(kāi),使其成為左下部分與右上部分。 對(duì)于左下部分各值,可視為以先從Y 軸向下再?gòu)腦 軸向右的順序依次“遠(yuǎn)離”末值。 由于不存在同時(shí)在兩個(gè)方向上的“移動(dòng)”,則X 軸與Y 軸分別與末值所在坐標(biāo)的差值之和,即為與末值空間上的距離,然后用末值減去這個(gè)距離,得到處于左下部分的項(xiàng)的值。 定義為valueI_left。由末值坐標(biāo)(1,2),得出式(13)。

同理,對(duì)于右上部分各值,可視為依次“遠(yuǎn)離”初值,且距離越遠(yuǎn)數(shù)值越大,該值定義為valueI_right。 由末值坐標(biāo)(1,2),得出式(14)。

可見(jiàn),當(dāng)坐標(biāo)y值大于x值時(shí),此項(xiàng)位于左下部分,反之處于右上部分。 可利用三目運(yùn)算符,將式(13)與式(14)合成式(15),并把值合并定義為valueI。

至此,已獲得可構(gòu)建出矩陣的所有數(shù)據(jù),不妨先行驗(yàn)證一次。 本文使用for 循環(huán)語(yǔ)句,定義整型變量I,循環(huán)自增至n2,以I為參數(shù),求出對(duì)應(yīng)值后輸出,同時(shí)每輸出n個(gè)值后換行。 設(shè)置n值為12,構(gòu)建12 階矩陣作為示例,如圖3 所示。 輸出符合預(yù)期,只需再求出各外環(huán)末值之和,便可構(gòu)建正確的螺旋矩陣。

圖3 螺旋旋矩拆解為各單環(huán)

3.4 求解各外環(huán)末值之和

由式(12)可計(jì)算出某一階外環(huán)的末值。 對(duì)于求解各外環(huán)末值之和問(wèn)題,可從當(dāng)前矩陣最外環(huán),即深度為0 的環(huán)開(kāi)始,到當(dāng)前深度環(huán)為止,循環(huán)使用式(12)求出對(duì)應(yīng)環(huán)末值并累加。 本文研究在線算法的目的之一,是要規(guī)避算法中出現(xiàn)的循環(huán)結(jié)構(gòu)。 為得到簡(jiǎn)潔的公式,先由循環(huán)思想出發(fā),定義deepI為循環(huán)計(jì)算中累計(jì)求值所使用的當(dāng)前階數(shù),循環(huán)語(yǔ)句為式(16)。

定義各外環(huán)末值之和為acc,在循環(huán)語(yǔ)句中累加,如式(17)所示。

通過(guò)通項(xiàng)公式簡(jiǎn)單計(jì)算,可得到式(19),這是一個(gè)不包含deepI的公式,計(jì)算結(jié)果為各外環(huán)末值之和。 最后將式(15)中的valueI與acc相加,即可直接計(jì)算得到當(dāng)前項(xiàng)在螺旋矩陣中的值。

最后,同樣以12 階為例,順序計(jì)算后輸出,檢驗(yàn)算法準(zhǔn)確度,如圖4 所示。

圖4 12 階的螺旋矩陣

可以看到,在生成螺旋矩陣方面,本文研究的算法可準(zhǔn)確計(jì)算矩陣各項(xiàng)值,所以本算法也可應(yīng)用在查詢螺旋矩陣問(wèn)題上。

4 螺旋矩陣在線算法與傳統(tǒng)離線算法在性能上的對(duì)比

在生成螺旋矩陣問(wèn)題中,由于不可避免地需要遍歷一次大小為n2的矩陣,則本算法的時(shí)間復(fù)雜度與算法1 的時(shí)間復(fù)雜度相同,為O(n2)。 而在空間上,本算法省去了預(yù)先構(gòu)建矩陣的操作,無(wú)需使用輔助數(shù)組,空間復(fù)雜度為S(1),小于算法1 的空間復(fù)雜度S(n2),性能上整體優(yōu)于算法1。 在查詢螺旋矩陣問(wèn)題中,同樣因?yàn)闊o(wú)需提前計(jì)算矩陣各值,所以本算法的時(shí)間復(fù)雜度降至O(1),空間復(fù)雜度同樣降至S(1)。 在性能上全面優(yōu)于算法1。

如圖5、圖6、圖7 和圖8 所示,展示了傳統(tǒng)離線算法與在線算法在求解這兩種問(wèn)題時(shí)分別在時(shí)間與空間上的差異。 其中編譯與運(yùn)行環(huán)境為VC,所有變量在棧區(qū)定義,查詢項(xiàng)為項(xiàng)數(shù)中間值n2/2,記錄時(shí)間不包括輸入與輸出所占的時(shí)間。 所有結(jié)果為多次實(shí)驗(yàn)取平均值。

圖5 生成操作的時(shí)間對(duì)比

圖6 生成操作的內(nèi)存空間對(duì)比

圖7 查詢操作的時(shí)間對(duì)比

圖8 查詢操作的內(nèi)存空間對(duì)比

從圖表可直觀看出,除了在生成操作上在線算法較常規(guī)算法有系數(shù)級(jí)別的額外時(shí)間損耗外,對(duì)于其余3種操作,在線算法在效率上都遠(yuǎn)遠(yuǎn)優(yōu)于常規(guī)算法,特別是在線算法也可計(jì)算常規(guī)算法無(wú)法求解的大階數(shù)螺旋矩陣。