幫醜程式整型

更新於 2022/08/27發佈於 2022/05/15閱讀時間約 6 分鐘

「天啊！這程式怎麼這麼醜！」瞪著螢幕上先前寫的程式，不禁從心底冒出這樣的一句話。

因為先去研究Pytorch，所以有好一陣子沒有寫Game of Life這支程式。現在回頭再來看先前寫的，還真是有種慘不忍睹的感覺，怎麼看都覺得不順眼。究竟問題出在哪呢？先前寫的時候，還覺得自己挺有才的，居然能想到挺妙的點子來處理一些問題，怎麼這些妙點子，現在看來卻是平凡無奇，沒啥特別的。仔細想想，或許是因為使用的方法不是很好，也沒有好好發揮Python的長處，所以整支程式看起來感覺醜醜的。說得有學問一點，就是設計出來的演算法實在不怎麼樣，所以沒法運用Python的特點，讓程式簡潔、有效率。

既然知道問題出在哪裡，那就來幫程式整型囉，把它整得美美的。之所以說是整型，而不是說化妝，是因為連演算法都要換。更換演算法，可不是改改變數名稱，或者把兩行併成一行，這樣子的表面功夫而已，而是從骨子裡頭改造，面子、裡子都要重新型塑的大工程。

先來看看原先的寫法有什麼缺陷。原先的寫法，是把universe當成黑白影像，然後用處理影像的方式，一個一個cell的去看看，演化到下一代時，cell是生或是死。這樣子的做法很直觀、很容易理解，反正就是去數周邊的鄰居有幾個是活著的而已。但是稍微觀察一下就可以發現，這樣子的做法非常沒有效率。因為在大部分的情況下，活著的cell只佔少數，整個universe中，存在著大片沒有任何cell活著的死寂區域，而這些死寂區域內的cell，是沒可能在演化到下一代時活過來的。所以囉，一個一個cell的去檢查，大部分都是在做白工，實在是沒必要。

既然原先的寫法有著做很多白工的缺陷，那有沒有辦法避免做白工呢？如果能把演化到下一代時，有可能會改變狀態的cell全部找出來，然後只處理這些cell，那就不會做白工了！所以現在的問題是，怎麼判斷某一個cell在演化到下一代時，有可能會改變狀態？

一個cell在演化到下一代時的狀態，完全取決於周遭的8個鄰居，有多少個是活著的。所以囉，換個角度看，只有活著的cell的周遭鄰居，才有可能會改變狀態。也就是說，在進行演化時，需要處理的，就只有活著的cell，以及它們周遭的鄰居。至於其他的cell，因為根本不可能改變狀態，所以就無視、忽視、不需理它們。

解決問題的辦法有了，那要怎麼寫呢？最關鍵的地方，就是要把所有活著的cell，以及它們的鄰居，全給收集起來。既然要收集東西，那就得找個東西來裝。在Python裡頭，可以拿來裝東西的容器有list、tuple、dictionary、set，哪個比較合用呢？

在收集的過程中，要一個一個的把cell給裝進容器中，所以tuple不合用，因為它是immutable，只能在一開始的時候把東西裝進去，之後就不能再裝了。

某一個cell有可能同時是兩個活著的cell的鄰居，所以要把它裝進容器時，有可能它已經在容器裡頭了。list和dictionary要自己檢查、排除，才能避免把同樣的東西裝進去，不太合用。set倒是沒這個問題，同樣的東西塞進去之後，它會像魔術師的袋子一樣，自動把多的變不見，只留下一個。所以在把cell裝進set時，不需檢查裡頭的東西會不會重複，儘管裝就是了。這樣看來，set是個不錯的選擇。

裝東西用的容器有了，要收集狀態有可能改變的cell，用(x, y)來表示在那個座標位置的cell，先把活著的cell放到cells_alive這個set裡頭，然後程式可以這麼寫：

cells_need_check = set()
for x0, y0 in cells_alive:
　　cells_need_check |= {(x0+x, y0+y) for x in range(-1, 2)
　　　　　　　　　　　　　　for y in range(-1, 2) if 0 <= x0+x < width
　　　　　　　　　　　　　　if 0 <= y0+y < height}

這裡的width和height，是universe的寬和高。利用set 特有的union方法，以及comprehension，短短的幾行，就達到目的了！

接下來，要來看看在cells_need_check裡頭的cell，它周遭的鄰居，有幾個是活著的。假設現在要處理的cell是(x0, y0)，程式就這麼寫：

for x0, y0 in cells_need_check:
　　neighbors = {(x0+x, y0+y) for x in range(-1, 2) for y in range(-1, 2)}                                – {(x0, y0)}
　　neighbors_alive = neighbors & cells_alive
n = len(neighbors_alive)

要知道周圍鄰居有幾個是活著的，不需要一個一個的去數，那太麻煩了。把周遭鄰居放在neighbors這個set裡頭，它和cells_alive的intersection所得到的set，在裡頭放著的，就是周圍鄰居中活著的cell，而它的數量，用len()這個函數就可以馬上知道，不用花時間去一個一個數。

換個處理的方式，再加上好好利用Python提供的功能，「核心計算」部分的程式碼，減少了將近30%。當然啦，這只是參考用，程式寫得好不好，可不能單純用長度來衡量。

除了程式碼長度外，看起來執行速度應該也可提高不少，因為不用一網打盡地處理所有的cell，而只需要處理少數可能改變狀態的cell。當然啦，這只是就理論上來看，沒有真正實際去測。測量程式改寫後能快多少，實在是有點無聊。

至於使用的記憶體，應該少很多，因為原先用來記錄每個cell狀態的list，現在已經不需要了。現在只需要紀錄活著的cell和他們的鄰居，而這些只佔所有cell數量的少數。當然啦，這只是想當然耳的這麼認為，真正的情況是怎樣，實際去測才知道。

整型後的程式，看起來漂亮多了！

即將進入廣告，捲動後可繼續閱讀

為什麼會看到廣告

15會員

131內容數

寫點東西自娛娛人

留言0

查看全部

發表第一個留言支持創作者！

ysf的沙龍的其他內容

關於lambda function的二三事

或許就如官網文件中所說的，lambda function就只是syntactic sugar而已，所以也就沒特別在意，直到在設計Game of Life的輸入介面時，因為需要用到，兜兜轉轉，費了好些功夫和時間，總算對它的用途和用法有比較完整的認識。

#Python #python #PYTHON

user真難伺候

唉！這user可真難伺候啊～～～

#Python #python #PYTHON

奮戰matplotlib

Game of Life的輸出結果，也就是每代演化後universe的長相，程式要怎麼寫呢？現在有個二維list，裡頭放的是一堆0和1，要怎麼樣用西洋棋盤式的方式來顯示呢？這看來勢必得用到別人寫好的module來做，才能省時、省力又漂亮。第一個想到的，當然就是matplotlib這個科學繪圖用的mo

#Python #python #PYTHON

你會看「東施」和「武大郎」合演的「我可能不會愛你」嗎？

如果「李大仁」長得像「武大郎」，而「程又青」長得像「東施」，這戲，還會有人看嗎？

#Python #python #PYTHON

測試抓臭蟲

Game of Life的「核心計算」部分寫好了，短短的沒幾行，畢竟也就那麼幾條判斷規則而已，沒什麼太複雜的東東要處理。說是寫好了，但到底能不能跑、跑出來的結果對不對，那可還是在未定之天哩。

#Python #python #PYTHON

學習的技巧

在學習新事物的時候，如果能善用類比、聯想等小技巧，往往能事半功倍，但也是有可能會碰壁的。

#Python #python #PYTHON

關於lambda function的二三事

#Python #python #PYTHON