如果有一張圖片作為範本,我們想基於其中的結構,使之擴展、成為更大張的圖片,這個過程稱為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幾秒!不過,這一年多持續調整實作、在函數式不變特性中,去尋找求變的過程,我們可以思考許多策略,無論是在演算法,或者是在函數式,不管行得通或行不通,都讓我得到了許多的啟發。

專欄作者


熱門新聞

Advertisement