用 Orihime 演算法摺完整版龍神 3.5 - 第二篇

使用 12GB 的記憶體在 44 分鐘摺出完整龍神當然是一項成就，不過我強烈地覺得我還能做得更好。一方面，時間跟空間的消耗都還能再被改進；另一方面，我之前使用的 CP 為了要能摺平而有著一道奇怪的山摺貫穿了身體的上半部，且其腿部的姿勢被調整成了鱗片看不到的樣子。我是有辦法修改檔案來修正這些，但一旦我改變了其中任何一點，新的 CP 檔案就完全地打倒了我所作的最佳化、而執行時間又再次變得無限漫長。於是，在兩週中我再次踏上了我的龍神旅程的第二階段，而終於，我讓程式能夠在 16 分鐘中、只用了 6GB 的記憶體摺出上面描繪的版本。我將在這邊再次記錄這段旅程。

記憶體最佳化

其中一個讓我很困惑的事情是，記憶體的消耗比我估計的要多很多，於是我開始找尋軟體工程師們所說的「記憶體洩漏」，也就是程式沒有釋放掉那些配置給不再被需要的資料的記憶體空間。我發現到，在 Orihime 演算法準備那些要給解答搜尋階段使用的資料的那些階段中，有一個矩陣是記錄著所有面的相鄰關係，它使用了龐大的記憶體空間（以龍神來說大約是 5GB）、但在準備階段之後就不再被使用到了。於是僅只是把這些記憶體空間釋放掉，我馬上就把龍神的記憶體需求降低到了 7GB。 ¹

然而，7GB 聽起來還是不夠好，而我比較希望能達到 6；倒不是有什麼特別的理由，只是我覺得偶數比較好聽（以及記憶體的消耗非常接近 6）。這促使了我想出了另一個我稱為 PseudoListMatrix 的點子（可能不是什麼新發明）。在演算法的一個部份當中，有著一個很大的矩陣 M、其中每一個位置 M[i][j] 都是一個數字的列表，而如果我們用三維陣列或列表的二維陣列來儲存之都會消耗很大量的記憶體。PseudoListMatrix 的概念是去對每個 i 去儲存對某個 x 出現在 M[i][x] 中的數字列表，以及類似地對每個 j 去儲存對某個 x 出現在 M[x][j] 中的數字列表。然後，當需要用到 M[i][j] 的清單時，我們就給出 M[i][x] 清單和M[x][j] 清單的交集。一般來說，這樣會導致一個比真正的 M[i][j] 清單更大的清單，但在這邊的特定用例之下，由於清單的特性、其結果正好就是 M[i][j]。利用了這個資料結構，我總算是將記憶體消耗減少到了 6GB，且幾乎沒有犧牲掉速度。

四元樹的威力

到這邊為止，我所作的速度最佳化都是只針對搜尋階段的。當我首次成功摺出龍神的時候，搜尋階段已經快到了那 44 分鐘大部分都是花在準備階段上的。在我檢視那些準備步驟之後，我發現裡面有很多步驟都可以用一種稱為四元樹的古典資料結構來大幅加速。

基本上，電腦程式並沒有辦法真的「看到」二維平面上的物件，它所知道的只是一個以數字呈現的物件清單。如果我們需要問這樣的問題「裡面是否有兩個物件有碰撞」，那這個問題的單純解法就是去檢視每一對可能的物件、並且去對每一對計算看看是否有碰撞。於是對於 n 個物件，這就會用上 n(n-1)/2 次的比較，而這當 n 變大的時候會是一個很龐大的數字。

四元樹的想法是將二維平面分割成四個象限、並且將物件儲存在適當的象限中。如果一個象限包含了太多物件，我們就再次將它在其內部分割成四個象限、並重複上述操作。然後當我們問同樣的問題時，對於每一個物件，我們只需要拿它跟被放在同一個象限中的物件做比較即可。這大幅地降低比較次數到大約 n\log n 次而已（這尤其對較大的 n來說顯得更小）、並能快上許多地回答問題。

四元樹極為靈活，以至於在準備階段中有非常多地方是它可以被套用的，而每一次套用都會省下大概五分鐘左右的執行時間。在結合了其他的最佳化技巧（尤其是第一部份中提到的索引方法）之下，我終於把同樣的龍神 CP 的執行時間從 44 分鐘降低到了只有大約 5 分鐘。

摺出本來摺不出來的

然而，即便原本的龍神 CP 如今摺得這麼快，有一些 CP（像是上圖的版本）還是沒辦法摺成；其執行時間仍舊像是無止盡。對於這些 CP，在搜尋過程中有兩個主要的障礙：太多可能的排列、以及交換迴圈。

首先，在第一篇中，我曾經將 Orihime 演算法的搜尋過程跟解數獨來做比較。對於數獨來說，每個格子只有九個可能填入的數字，但對於這邊的子面來說，可能的排列數目是用階乘在計算的，這些數字大到超乎想像。雖然我已經套用了「將給定的約束條件中最常一鍊的順序加以固定」的想法，在某些情況中這還是會剩下數以億萬億萬計的排列要被檢查，而且這還只是一個子面，但龍神有著好幾千個子面！

其次，我在第一篇中也題到了交換演算法。雖然那是目前為止最強的加速手段，但它確實有一個小小的機率會掉進「迴圈」之中，其中兩個以上的子面會不斷地被交換到其它子面之前，並且甚至重置它們的進度。在這種情況中，理論上搜尋永遠不會結束；這比我剛才說的第一個問題更糟，因為那只會導致搜尋要執行非常非常久，但是理論上還是會完成的。

兩週下來，我對這兩個阻礙感到十分棘手，試了一堆想法但都沒有成功。終於，我領會到了這兩個問題的解答都跟「引入新資訊到搜尋過程中」有關。我設計的排列產生器有能力根據給定的約束條件來將不符合的排列過濾掉，所以如果剩下的排列還是太多，那就一定表示我給它的約束條件還不夠多。類似地，如果交換掉入了迴圈，一種馬上就能破解迴圈的辦法就是把一個尚未見過的子面交換到它們之前，因為如此一來就產生了一個我們尚未考慮過的子面序列了。

然而，只是把新的子面引入到序列之中、未必就足以產生夠多的新約束條件來縮減排列產生器。為了要快速產生更多的約束條件，我用了我在第一篇中提到的 Italiano 演算法來在每次有子面的排列被決定之後推斷出更多的交疊關係。結果這對搜尋效能來說是一大加速，跟交換演算法有得比了。在實作了這個想法之後，我終於成功了摺出了上面的版本，以及所有我之前摺不出來的樣本 CP。

最終版龍神

對我來說，上面第二個版本的龍神已經夠讓我滿意了。不過同一時間中，Avinash Karnik 和 Bodo Haag 製作了另一個版本的龍神 CP，其中整個身體都做了對摺、腿部也被往下摺，並且加入了現實中摺龍神時會被加入的頭部扭轉。這個 CP 的層次堆疊比起之前所有的版本都還要更複雜，而它再次地打倒了我最佳化過的演算法。幸好，這次並沒有什麼大問題在，只是一個之前沒有注意到的、只會發生在高度複雜的 CP 上的 bug。在修正了該 bug 之後，他們的 CP 就能在 35 分鐘內摺出。比起其它版本的龍神 CP 要久很多，但起碼是有摺出來的。

當然，我不會這麼輕易就罷手的。雖然無疑這是更加複雜的 CP，但我也還是希望能把它的執行時間降到 20 分鐘內。在我仔細觀察搜尋過程之後，我注意到這個 CP 特別有著一些其實很關鍵、但卻在初始順序中被排到很後面的子面。這會導致演算法好幾次在很深的深度中遇到死路而需要返回，光是這樣就浪費了十來分鐘。為了對付這個現象，我實作了一個新的策略說「如果在很深的深度中遇到死路，則在交換的過程中把附近的幾個子面也一起換到前面去」。這對解決該問題相當地有效，而最終將執行時間降到了僅 16 分鐘。其結果就是上面的第一張圖。

這些最佳化如今都已經成為 Oriedita 的 v0.0.10 版釋出的一部分了。

更新：

第一個圖的最新記錄是用 3GB 記憶體在 65 秒摺完。