幫醜程式整型
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 < widthif 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_aliven = len(neighbors_alive)
要知道周圍鄰居有幾個是活著的，不需要一個一個的去數，那太麻煩了。把周遭鄰居放在neighbors這個set裡頭，它和cells_alive的intersection所得到的set，在裡頭放著的，就是周圍鄰居中活著的cell，而它的數量，用len()這個函數就可以馬上知道，不用花時間去一個一個數。
換個處理的方式，再加上好好利用Python提供的功能，「核心計算」部分的程式碼，減少了將近30%。當然啦，這只是參考用，程式寫得好不好，可不能單純用長度來衡量。
除了程式碼長度外，看起來執行速度應該也可提高不少，因為不用一網打盡地處理所有的cell，而只需要處理少數可能改變狀態的cell。當然啦，這只是就理論上來看，沒有真正實際去測。測量程式改寫後能快多少，實在是有點無聊。
至於使用的記憶體，應該少很多，因為原先用來記錄每個cell狀態的list，現在已經不需要了。現在只需要紀錄活著的cell和他們的鄰居，而這些只佔所有cell數量的少數。當然啦，這只是想當然耳的這麼認為，真正的情況是怎樣，實際去測才知道。
整型後的程式，看起來漂亮多了！
為什麼會看到廣告
留言0
查看全部
