雷育銘

（清遠(yuǎn)職業(yè)技術(shù)學(xué)院信息技術(shù)與創(chuàng)意設(shè)計(jì)學(xué)院，廣東 清遠(yuǎn) 511510）

1 引言

在基于Java集合類求解素?cái)?shù)方陣的過(guò)程中[1]，筆者發(fā)現(xiàn)：以HashSet為例，方陣階數(shù)每增長(zhǎng)一階，在同一環(huán)境下算法運(yùn)行時(shí)間增長(zhǎng)10倍以上。就1億個(gè)組合測(cè)試時(shí)間來(lái)看，7階的運(yùn)行時(shí)間超過(guò)15小時(shí)，如下表所示：

其中，A集合包含所有N位的可逆素?cái)?shù)，B集合為A集合中不包含偶數(shù)和5的所有素?cái)?shù)。

為了解決此問(wèn)題，筆者通過(guò)精簡(jiǎn)集合樣本數(shù)、從數(shù)字拆分中刪除new操作、加快方陣旋轉(zhuǎn)、使用映射替換集合以及檢測(cè)與消除無(wú)效組合等手段，對(duì)引文[1]中的算法進(jìn)行了大幅優(yōu)化，最終使得運(yùn)行時(shí)間在7階時(shí)能夠縮短2200多倍，降為23秒左右。

2 精簡(jiǎn)集合樣本數(shù)

N階素?cái)?shù)方陣的求解，基本思路是先取樣組合后枚舉測(cè)試，主要規(guī)則、步驟為：①篩選N位可逆素?cái)?shù)構(gòu)成A集合，在A集合中繼續(xù)篩選不含偶數(shù)和5的可逆素?cái)?shù)構(gòu)成B集合；②循環(huán)從B集合取兩個(gè)不同的素?cái)?shù)分別放首尾兩行，從A集合取N-2個(gè)不同的素?cái)?shù)放中間的N-2行，組合成初始方陣M；③判斷方陣M是否為目標(biāo)方陣（即M的各列和兩條對(duì)角線任意方向上的N位數(shù)均構(gòu)成一個(gè)N位可逆素?cái)?shù)），如果不是，則返回②；④判斷M是否與已有的目標(biāo)方陣相似，如果是，直接返回②；⑤如果不是，則添加M到目標(biāo)方陣集合，返回②。流程如下：

經(jīng)過(guò)觀察分析，B集合中的可逆素?cái)?shù)是成對(duì)存在的，比如4位可逆素?cái)?shù)1193和它的逆序素?cái)?shù)3911同時(shí)存在?？紤]到每個(gè)目標(biāo)方陣同樣具有方向可逆性[1]，因此可以規(guī)定M的首行只需從B集合每對(duì)互逆的素?cái)?shù)中的較小者中取樣即可，這些較小者構(gòu)成的集合記為C集合。

至此，方陣M的各行取樣組合方法如下：

僅此一步優(yōu)化，算法步驟③需要檢測(cè)的樣本總數(shù)就縮減了一半，對(duì)縮短算法的運(yùn)行時(shí)間起到了積極作用，比如4階可以縮減近半。但隨著階數(shù)的增長(zhǎng)，縮減越來(lái)越不明顯，沒(méi)有帶來(lái)數(shù)量級(jí)的改變。

3 從數(shù)字拆分中刪除new操作

為了判斷方陣M的各列和對(duì)角線是否構(gòu)成可逆素?cái)?shù)，需要先把M的伴隨數(shù)組MA中的各個(gè)素?cái)?shù)按位拆分成單個(gè)數(shù)字，初始代碼如下：

作為對(duì)比，筆者將局部數(shù)組a改成類靜態(tài)成員對(duì)象，即a只需new一次，然后對(duì)比了兩個(gè)版本的運(yùn)行時(shí)間：

表2 1億個(gè)N位數(shù)拆分時(shí)間對(duì)比(單位:毫秒)

由此可見(jiàn)，new操作對(duì)數(shù)字拆分方法的運(yùn)行時(shí)間具有明顯影響。在相同樣本數(shù)的情況下，每次分配一個(gè)一維數(shù)組來(lái)保存結(jié)果，相比使用共享數(shù)組，會(huì)使得運(yùn)行時(shí)間翻倍。對(duì)比表1中的數(shù)據(jù)，可以看到這個(gè)改進(jìn)節(jié)省的時(shí)間，相對(duì)總體時(shí)間而言也不是關(guān)鍵的。

表1 4～8階運(yùn)行時(shí)間對(duì)比

4 加快方陣旋轉(zhuǎn)

受上一步的啟發(fā)，在判斷M是否與現(xiàn)有目標(biāo)方陣相似時(shí)，筆者對(duì)原來(lái)的旋轉(zhuǎn)方法進(jìn)行了優(yōu)化，即使用類靜態(tài)數(shù)組成員代替每次都要new的局部數(shù)組，從而減少了步驟④運(yùn)行的時(shí)間。具體代碼如下：

因?yàn)闈M足要求的目標(biāo)方陣數(shù)量有限，因此，此次優(yōu)化效果不明顯。

5 使用映射替換集合

考慮到步驟③中每一次取樣組合成新方陣M后，都需要對(duì)各個(gè)素?cái)?shù)進(jìn)行拆分。分析顯示，該步驟產(chǎn)生的組合數(shù)量是巨大的[1]。結(jié)合“3從數(shù)字拆分中刪除new操作”的測(cè)試結(jié)果，筆者決定將數(shù)字拆分操作提前到步驟②來(lái)完成，即修改構(gòu)建A、B、C三個(gè)集合的過(guò)程，在找到符合要求的素?cái)?shù)時(shí)，順便就把它們按位拆分成一維數(shù)組，再以該素?cái)?shù)為Key，以＜K，V＞對(duì)的形式保存到相應(yīng)的HashMap映射mapA、mapB、mapC中。在步驟③需要按列和對(duì)角線組合新N位數(shù)時(shí)，直接從相應(yīng)映射中以素?cái)?shù)為Key提取預(yù)先拆分好的Value數(shù)組即可。從A映射構(gòu)建B、C映射的代碼如下：

經(jīng)此優(yōu)化，測(cè)試算法在N取值4～8時(shí)的運(yùn)行情況，速度在之前幾步優(yōu)化的基礎(chǔ)上，再提升了10～30%，但沒(méi)有發(fā)生數(shù)量級(jí)的改變。

6 檢測(cè)與消除無(wú)效組合

深入分析圖2不難發(fā)現(xiàn)，為了滿足素?cái)?shù)方陣的要求，需要檢測(cè)取樣自A映射的N-2個(gè)素?cái)?shù)和取樣自B、C映射的兩個(gè)素?cái)?shù)是否有重復(fù)。如果存在重復(fù)，則組合無(wú)效，需要進(jìn)行下一輪取樣。只有檢測(cè)通過(guò)，才進(jìn)行圖1步驟③④中的操作，代碼如下：

圖1 素?cái)?shù)方陣求解流程圖

圖2 方陣各行取樣組合方法

上述代碼能夠有效檢測(cè)無(wú)效組合。當(dāng)檢測(cè)到無(wú)效組合后，通過(guò)迭代跳過(guò)。經(jīng)過(guò)仔細(xì)分析，不難發(fā)現(xiàn)這樣做的效率是非常低的，這也是算法運(yùn)行時(shí)間隨著階數(shù)增長(zhǎng)大幅飆升的根本原因。如圖2所示，取樣迭代從最后一行——即B映射——開(kāi)始。也就是說(shuō)，剛開(kāi)始的時(shí)候，中間N-2行樣本必然是相同的。假設(shè)A、B映射樣本數(shù)分別為S1、S2，為了滿足方陣組合要求，程序需要執(zhí)行T=次空迭代，即從第二行開(kāi)始，依次取A映射的第1、第2...第N-2個(gè)元素，才能使得中間N-2行處于互不相同的初始狀態(tài)。當(dāng)N=7時(shí)，！這就是算法運(yùn)行超過(guò)15個(gè)小時(shí)仍未檢測(cè)到1億個(gè)有效組合的原因。為更高效率地消除無(wú)效組合，在循環(huán)取樣開(kāi)始前，中間N-2行應(yīng)該步進(jìn)式地錯(cuò)開(kāi)，以確保它們互不相同：

后續(xù)的迭代過(guò)程中，在檢測(cè)到重復(fù)樣本后，應(yīng)該就地迭代，而不是從最后一行開(kāi)始迭代。根據(jù)此思想，優(yōu)化后的代碼框架如下：

經(jīng)過(guò)此優(yōu)化，各階運(yùn)行時(shí)間都有大幅縮減，第一個(gè)目標(biāo)方陣出現(xiàn)的組合數(shù)均有下降，更重要的是，從6階開(kāi)始算法運(yùn)行時(shí)間發(fā)生了數(shù)據(jù)級(jí)的縮減，階數(shù)的增長(zhǎng)不再對(duì)運(yùn)行時(shí)間構(gòu)成數(shù)量級(jí)的影響，如下表所示：

表3 優(yōu)化后4～8階運(yùn)行時(shí)間對(duì)比