波函式塌縮與函數式

如果有一張圖片作為範本，我們想基於其中的結構，使之擴展、成為更大張的圖片，這個過程稱為Texture synthesis，此時，可以將這類演算擴展用於遊戲或3D建模，創造隨機的世界或模型，就像先前專欄〈理解波函數塌縮演算〉談過的波函數塌縮，就是一個可行的方案，而我就曾經在OpenSCAD實現了波函數塌縮。

不過，最初的實現版本只是堪用而己，效能頗為不彰，只是算個20乘20大小的拼接，就必須花上40幾秒，我不禁一直執著於尋找更好的實現方式。而執著的原因在於，OpenSCAD具有函數式典範，波函式塌縮需要持續地塌縮盤面，在不可變動特性與需要頻繁變動之間，若我們以命令式角度來看，兩者存在著很大的衝突。

變動與不變的衝突？

最基本的衝突情境就是，20乘20就有400個位置，每個位置又有多個候選的拼接磚，成立三維的立體資料結構；塌縮改變了某位置的狀態，也改變了整個盤面的狀態；接著，傳播又要改變多個位置的狀態，也就要多次改變盤面的狀態。

就命令式而言，這不成問題，指定索引更新資料就好，然而，就函數式而言，狀態改變意謂著重組相關資料，這可是大問題！

改變思考的方式是必要的，現今開發者應該對一些從命令式轉換為函數式的思維有點認識，先前專欄〈在不變中求變〉談過一些，我近來又整理了一些函數式模式，從這些角度來切入，確實是有些幫助，大致上少了10秒左右的時間吧！

然而，算個20乘20拼接還要花上30幾秒，我仍然覺得不滿意，表面看來，這是效能的問題，不過，後來發現我想探究的問題有兩個：效能瓶頸真的是來自於函數式典範的不可變動特性嗎？演算法本身真的就要頻繁地變動狀態嗎？

我需要畫清界線，但這個界線不是指函數式中純粹與不純粹的界線，而是要釐清哪些問題來自於演算法，哪些問題來自函數式！

想畫出這道界線的第一步，就是讓程式碼更為清晰，在進入效能最佳化階段之前，先持續進行重構，關於這部分的做法與效益，我在先前專欄〈重構與效能〉曾經提過。

演算法的調整

確實地，在重構過程中，我找到了很多不合理或重複的運算。在命令式典範中，因為可以直接改變資料的狀態，所以，在資料量不大的情況下，這類運算的成本或許能夠忽略；不過，在函數式的實作時會被放大，在重複使用一些運算成果後，執行的時間確實有少一些。

這是屬於演算法（實作時）的問題，就波函式塌縮而言，確實有不少狀態、權重或熵值的重複計算；不過，還有個關鍵的地方，那就是：如何尋找「塌縮」與「傳播」的位置。在重構之前的程式碼裡，我並沒有發現一件事：自己每次都是在400格的盤面上，尋找這些位置。

對於「塌縮」，其實，在每一代的塌縮前，都會確認是否整個盤面都完成塌縮，反過來想，這就是在尋找哪些位置沒有完成塌縮，所以，在下一代塌縮時，我們只要針對這些位置去搜尋就可以了，如此一來，每代塌縮位置的搜尋集合就會越來越小；對於「傳播」，只要鄰居的候選磚數量只有一個，根本就不用進行傳播處理。

說穿了，這就是分支修剪的概念，而且，確實又成功地減少了執行的時間，同時表示在命令式的世界裡，如果採取類似的方式，應該也能對效能有很大的改進。

下一個待調整目標是搜尋，因為波函式塌縮有許多情境（狀態、權重或熵值）都要進行搜尋，搜尋牽涉到資料結構，我嘗試過使用陣列，並在排序後二元搜尋，效能沒有明顯改進，後來嘗試使用字典進行雜湊搜尋，以空間換時間的方式確實奏效，執行需要的時間縮減到20幾秒左右。

然而，在一次偶發的奇想裡，我試著使用原生的search函式取代雜湊搜尋，執行時間降至10幾秒！這點令我訝異，仔細想想，建立字典或雜湊碼計算需要成本，二元搜尋的比較與事先的排序也需要成本，然而我的實作中，每次要搜尋的資料量不多，以至於這些成本掩蓋了效益，search函式搜尋雖然是線性，然而在資料量不大又是原生函式的情況下，反而有更好的表現。

函數式的策略

不可否認地，函數式有些計算，確實會造成負擔，遞迴就是其中之一，遞迴堆疊需要成本，而且有遞迴上限的問題。

在OpenSCAD如果想要避免這類問題，方式之一，是實現尾遞迴（tail recursion），因為OpenSCAD支援可以將簡單的尾遞迴形式展開為迭代的作法。

不過尾遞迴的實現，不會是天下掉下來直接有的，這意謂著要將函式拆分為更小的任務，才能看出哪邊構成了尾遞迴的模式，也就是說，需要先退出效能最佳化階段，對每個遞迴函式進行更細部的重構。

在這個過程中，會發現到一件事實，有些任務根本就不必使用遞迴，使用list comprehension就可以了！在重構之前，只是因為摻雜過多任務而看不出來，在具有list comprehension的其他語言（例如Python），應該也可以善用這種方式來改進程式的可讀性與效能。

在某位置的狀態塌縮處理上，原本是要收集某些不相容的狀態，然後從該位置刪除那些狀態；現在可以轉變為另一個角度思考，只收集相容的拼接磚，作為該位置的拼接磚集合就可以了。

當然，最終盤面狀態還是需要進行更新，然而，函數式不可變動特性的另一面就是：未變動的資料可以重用，這就涉及了資料結構，以及狀態的切分與重組。

以二維陣列來說，我們可以將資料切分為逐列（row），如果更新的是x行（column）、y列的資料，實際上，只要針對y列更新，其他未變動的列可以直接參考重用。

這其實是函數式的優點之一，可共用資料結構，例如樹狀結構，在比對狀態之後，若某個子樹並沒有變動，整個子樹拿來用就可以了，在前端有些函數式典範框架中虛擬DOM的方案，就是以類似概念作為出發點。

用一年縮短40秒

經過了一番調整，實際上效果如何呢？最初原本40幾秒才能完成的運算，降至8秒左右！還能不能再降呢？確實還存在著可調整的地方，只是這與波函式塌縮作者提倡的塌縮位置選擇策略有關了，作者是基於最小熵，經過實測，最小熵位置的運算有其成本，就我的建模需求而言，只要找尋最少候選拼接數量的位置就可以了，現在只要2秒多，就可以完成運算了。

從初次實作到目前的版本，我花費了一年多，將運算時間縮短了40幾秒！不過，這一年多持續調整實作、在函數式不變特性中，去尋找求變的過程，我們可以思考許多策略，無論是在演算法，或者是在函數式，不管行得通或行不通，都讓我得到了許多的啟發。