用 Orihime 演算法摺完整版龍神 3.5

最近我花了不少力氣在改進 Orihime（由目黑俊幸先生所開發的程式）的演算法。我希望能夠讓它能摺出神谷哲史先生設計的龍神 3.5 之完整版（包括塑形過的鱗片 ¹），該模型可說是史上最複雜的創作之一。這是一趟兼對速度與空間的追求之旅，並有著無盡的挑戰。在兩週的努力之後，我終於在我的筆電上用 12G 的記憶體在 44 分鐘內完整地摺出了該 CP。在這篇文章中，我將分享這趟旅程背後的故事。

對於想試試這個最佳化過的 Orihime 版本的人，可以查看 Oriedita 的最新版釋出。（要摺龍神需要 v0.0.7 版以上，且別忘了要以加大記憶體的設定來啟動。）

緣起

這趟旅程的起點是當我準備要定案神仙魚（我最新的原創作品）的 CP。儘管該模型只是 32 單位的箱形褶，相當令我吃驚的是，Orihime 竟然要花上 75 分鐘才能把它摺出來。我深度好奇是否 Orihime 的演算法中有任何可以被最佳化而加速的部份。問題是，原版的 Orihime 之原始碼大部分都是用日文來命名變數和函數等等，這使得要讀懂原始碼變得頗具難度。

幸運的是，大概在兩個月前，Gerben Oolbekkink 先生（代號 qurben）做了一個 Orihime 的分支「Oriedita」並且將原始碼大部分都轉換成使用英文的命名法。在看了他所翻譯的原始碼之後，才幾分鐘我就看出了第一個可以被改得有效率得多的地方：

public int FaceId2PermutationDigit(int im) {
    for (int i = 1; i <= faceIdCount; i++) {
        if (faceIdList[getPermutation(i)] == im) {
            return i;
        }
    }
    return 0;
}

這個函數在搜尋合法層次堆疊順序的過程中不斷地被重複呼叫，而每次被呼叫的時候，它就會執行一次計算機科學家們所說的線性搜尋、以找出一個給定的 id 對應的數字位置。這太慢了。一個有效得多的方法是先把 id 和位置之間的對應關係儲存在一個陣列中，然後直接查看該陣列就好了。

int[] FaceId2PermutationDigitMap; // Initialized to be large enough

public void reset_map() {
    for (int i = 1; i <= faceIdCount; i++) {
        FaceId2PermutationDigitMap[faceIdList[getPermutation(i)]] = i;
    }
}

public int FaceId2PermutationDigit(int im) {
    return FaceId2PermutationDigitMap[im];
}

做了這個修改之後，我的神仙魚的執行時間瞬間從 75 分鐘掉到了只剩 500 秒，只改了一個函數就讓速度變快了九倍。

進一步最佳化

在我發表我的結果之後，一些人很快地傳給我更多之前 Orihime 要花上非常長時間（或實務上根本不可能）摺出的大 CP 樣本。確實，即使有了我所做的最佳化，那些當中有些還是沒辦法隔夜完成。再接下來的幾天之中，我在程式碼中找到了幾個可以最佳化的地方，但是那些都只導致了執行時間稍微加快，沒有一個能導致很顯著的改進。

幾天之後，我發現了這整個旅程之中最顯著的加速機制：交換演算法。簡單來說，Orihime 所作的事情跟解數獨很類似，其中模型的「子面」就像是數獨中的格子，而子面中的排列就像是可以被填入格子中的數字。Orihime 會以某種特定的順序對子面進行窮舉搜尋，試圖對每一個子面各找出一種排列是整體來說一致的。一旦演算法來到一個子面是沒有一種排列跟前面的那些子面一致的，它就會回溯到前一個子面、選取一個不同的排列，然後繼續。

不過就像數獨，有的時候先填入一些「關鍵」的格子將能夠快速許多地解開謎題，因為那些格子能很快地幫助縮小其它格子的可能數字範圍。問題是，一開始的時候哪些子面是比較關鍵的、這並不是很明顯。然而，我們倒是可以藉由觀察到「搜尋反覆地在某一個子面走入死路」來推斷這個子面比起它前面的一些子面要來得更加關鍵。此時，我們就動態地交換搜尋順序、來先處理那一個子面。

這個技巧強大到一下子就把我的神仙魚的執行時間減少到只剩三四秒鐘，而它也使得人們傳給我的其它樣本都在一個可行的時間內能被摺完，除了一個例外，就是神谷哲史的龍神 3.5。

馴服神龍

要我說出「好，我們收工了；別管那一個摺不出來的模型了吧」是很難的，因為我遠遠還沒用完我的最佳化點子。過去我曾說過「我這輩子永遠不會來摺龍神」（理由是，如果我要花上那麼多功夫來摺一個模型，那就必須是我自己的原創設計才值得），但在那一刻中，我發現我很諷刺地在認真考慮真的要來摺龍神，只是差別在於是在電腦裡頭摺。

對完整塑形的龍神來說，最大的挑戰不是在於速度，而是在於空間。它的摺痕和面實在太多了，而在原本的資料結構中需要超大量的記憶體才能執行（估計至少要 30GB 的記憶體）。利用點陣陣列來取代 32 位元整數陣列，我總算是把記憶體的總需求控制到了 12GB 以下（或可能更少），而這在我的筆電上是可以達到的。

當然，這並不表示速度完全不是個問題。即使用上了交換演算法，大概還是要花上一整天才能摺完半個龍神的 CP。為了解決之，我改良了排列產生器、使得它會把提供的約束條件中最長的一鍊的順序固定下來，這使得它要迭代過所有可能的排列的速度加快了階乘倍那麼多，使得半個龍神可以在半小時之內摺完。

我也把目黑先生用來尋找遞移閉包用的 Warshall 演算法替換成更快速的 Italiano 演算法 ²，但這個演算法再次地需要不少記憶體才能執行。我完成旅程的最後一道手續，就是最佳化 Italiano 演算法的記憶體使用。其概念相當簡單但花了我不少時間才想通：我就只是需要更頻繁地清空更新，以免它們持續地在記憶體當中累積。

於是，我終於成功地把神龍給馴服了。若想知道更多關於我所作的個別最佳化的細節，可以參見我在 qurben 的儲存庫中所做的各個 PR。

更新：

也請參閱我的龍神旅程之第二篇 ！