The Nature of Code閱讀心得與Python實作：5.6 Algorithmic Efficiency..
這一節的標題是
Algorithmic Efficiency (or: Why Does MySketchProgram Run So Slowly?)
因為方格子標題字數限制，所以沒完整顯現
在模擬群聚行為時，隨著boid的數量越來越多，需要的計算量也會越來越多，導致程式的執行速度也跟著越來越慢，最後甚至於動彈不得。增加硬體設備的等級可以改善這個現象，不過除非你有錢到不知道怎麼花，不管是誰，花錢買設備升級這個主意，終究不會是首選。那有什麼其他可以不花錢的好方法嗎？在寫程式時使用效率比較好的演算法，就是個不錯的主意。
演算法百百種，哪種比較好呢？你怎麼知道這個演算法的效率會比那個好？要評估演算法的效率，可以使用大O表示法(big O notation)；這裡的O所代表的，是order的意思。大O表示法通常用來描述在最差的狀況下，演算法需要經過多少回合(cycle)的計算才能完成工作。例如，假設有10顆外觀一模一樣的湯圓，其中只有一顆是芝麻內餡，其他的都是花生內餡。要想找出那顆唯一的芝麻湯圓，我們得一顆一顆去看包的是哪種內餡。運氣好的話，選中的第一顆就是芝麻內餡；運氣背到極點的話，要看到第10顆才能找到那顆芝麻湯圓。同樣的道理，如果要在N顆湯圓中找到唯一的一顆芝麻湯圓，最好的狀況是第一顆就選中了，最差的狀況則是要檢查到最後一顆，也就是第N顆，才能找到那顆芝麻湯圓。這也就是說，要想在N樣東西裡頭找到特定的一樣東西，在最差的狀況底下，我們會需要執行N次的檢查工作才能找到那樣東西。所以，把檢查一次算一個回合的話，以大O表示法來描述這個找芝麻湯圓工作的工作量，就會記成O(N)。再來看看模擬群體行為時的狀況。要計算轉向力時，對於每一隻boid而言，除了要檢查自己本身的位置、速度之外，還要去檢查其他boid的位置、速度，然後再進行計算。所以，如果現在有N隻boid，那總共就需要檢查N2次。因此，如果檢查一次boid的位置、速度算一個回合的話，那這個計算量以大O表示法來表示，就會是O(N2)。
所以呢？同樣一件事，演算法的計算量是O(N)或O(N2)有什麼太大的差別嗎？當然有！而且當N越大，這差別就會越大！簡單的列個表，就足以說明這一切了。
N O(N)計算量 O(N2)計算量
1 1 1
10 10 100
100 100 10000
1000 1000 1000000
10000 10000 100000000
所以，當N=10000時，O(N2)的計算量，就足足是O(N)計算量的10000倍之多！從另一個角度來看，當N變成原來的10倍時，O(N)的工作量也會變成原來的10倍，但是O(N2)的計算量，卻會變成原來的102=100倍。這也就是為什麼在模擬群體行為時，明明只讓boid的數量增加一些，但卻很容易就讓程式跑起來卡卡的原因了；因為它是O(N2)啊！
模擬群體行為時，boid的數量要多，這樣才能顯現出效果；10隻boid和100隻boid所展現出的群體行為，視覺效果真的差很多。那怎麼辦呢？那可是個O(N2)的工作啊！boid的數量稍微多一點，就會讓計算量增加不少，讓模擬的效果大打折扣。那有沒有什麼好辦法可以讓計算量少一點呢？針對這個問題，Reynolds設計了一個叫做「bin-lattice spatial subdivision」的演算法，可以大大地減少模擬群體行為時的計算量。接下來，就來看看他是怎麼做的。
Spatial Subdivisions
在模擬群體行為時，boid並不會與所有其他的boid互動，而只會和自己的鄰居互動，因為自主代理人只具有有限的感知能力。那要怎麼判斷其他的boid是不是自己的鄰居呢？做法挺簡單的，就是設立一個門檻值；如果某個boid跟自己的距離小於這個門檻值，那這個boid就是自己的鄰居。所以，在計算轉向力時，完全可以無視不是自己鄰居的那些boid。因此，先前我們埋頭苦幹，把和所有其他的boid之間的距離都算出來，然後一一檢查是不是小於門檻值，藉此來找出鄰居的做法，實在是浪費了太多的力氣在沒有實質效益的事情上了，根本沒那個必要；直接無視那些不是鄰居的boid不就好了？但是問題來了，不一個一個去計算、檢查，那又怎麼會知道誰是鄰居、誰不是鄰居呢？
在Reynolds於2000年所發表的論文〈Interaction with Groups of Autonomous Characters〉中，他提出了一個巧妙的方法，可以在不需要計算和其他boid間的距離的情況下，就能找出所有的鄰居。Reynolds所提出的方法叫做「bin-lattice spatial subdivision」，簡稱「binning」。接下來，就來看看這個方法是怎麼做的。
Reynolds提出的bin-lattice spatial subdivision演算法原理其實很簡單，就如字面上可以看出來的，是一種空間切割術，就把boid活動的空間切成一小格一小格的，這樣子在你自己所在的格子以及附近格子裡頭的那些boid，才有可能是你的鄰居。為什麼呢？因為格子是我們切的，大小我們都知道。要知道某個boid和自己的距離，就只需要去數彼此之間相隔了幾個格子就可以了，完全不需要去計算實際的距離。當然啦，用格子數出來的距離只是個大概的數字，是個估計值。不過可以肯定的是，當超過一定數量的格子時，和那個格子之間的距離，就一定會超過判斷是不是鄰居的門檻值；這也就是說，在那個格子裡頭的boid，一定不會是鄰居，可以不用理他。所以，要找出所有的鄰居，並不需要去計算、檢查所有的boid，而就只需要去計算、檢查自己所在的格子，以及附近幾個格子內的boid就可以了。透過這樣子的做法，就可以避免做一大堆浪費力氣又沒有實質效益的計算工作，進而大大地減少所需的計算量。
原理知道了，接下來就來看看程式要怎麼寫。假設我們把boid的活動空間切成一格一格的方格。在程式中，會用到下列的變數：
resolution：方格的寬度cols：整數，方格直行的數量rows：整數，方格橫列的數量boids：存放所有boid的listgrids：大小為rows×cols的二維list；每個元素皆為list，用來存放位於該方格內之所有boid
假設boid是在寬為WIDTH像素、高為HEIGHT像素的二維空間中活動。根據方格的寬度將其切割成一格一格的方格後，直行和橫列的數量分別為
cols = WIDTH // resolution
rows = HEIGHT // resolution
根據這個結果來造一個二維list，讓這個list的元素對應到方格
grid = [[[] for _ in range(cols)] for _ in range(rows)]
然後把所有的boid，根據他所在的位置，將其歸屬到對應的grid元素中
col = int(boid.position.x / resolution)
if col < 0:
col = 0
elif col >= cols:
col = cols - 1
row = int(boid.position.y / resolution)
if row < 0:
row = 0
elif row >= rows:
row = rows - 1
grid[row][col].append(boid)
這裡要注意的是，因為boid.position.x和boid.position.y都是浮點數，所以算出直行的行數和橫列的列數之後，需要轉為整數，這樣在存取grid的元素時，才不會因為索引值不是整數而出現錯誤。
如果是在身處位置3×3方格範圍中的boid才有可能是鄰居的話，我們就只需要計算、檢查這些boid就夠了。要找出這些boid，程式可以這樣寫：
col = int(boid.position.x / resolution)
row = int(boid.position.y / resolution)
neighbors = []
for i in range(-1, 2):
for j in range(-1, 2):
cell_row = row + i
cell_col = col + j
if 0<=cell_row<rows and 0<=cell_col<cols:
neighbors += grid[cell_row][cell_col]
這樣子，在neighbors這個list中的，就是所有有可能是鄰居的boid了。因此，在計算轉向力時，就只需要去計算、檢查這些boid就夠了。
下面這個例子，就用bin-lattice spatial subdivision演算法來加快模擬boid群聚行為時的程式執行速度。執行結果可以發現，即便boid數量已經高達500隻，依舊可以跑得很順。
Example 5.12: Bin-Lattice Spatial Subdivision
在Boid類別中加入用於找出boid所在位置所屬方格的方法：
def locate_cell(self, boid, resolution):
col = int(boid.position.x / resolution)
if col < 0:
col = 0
elif col >= cols:
col = cols - 1
row = int(boid.position.y / resolution)
if row < 0:
row = 0
elif row >= rows:
row = rows - 1
return row, col
修改Flock類別的run()方法，加入找出所在位置3×3方格範圍內所有boid的功能。
def run(self, grid, resolution):
for boid in self.boids:
# 找出所在位置3x3方格範圍內的所有boid
row, col = boid.locate_cell(boid, resolution)
neighbors = []
for i in range(-1, 2):
for j in range(-1, 2):
cell_row = row + i
cell_col = col + j
if 0<=cell_row<rows and 0<=cell_col<cols:
neighbors += grid[cell_row][cell_col]
boid.flock(neighbors)
boid.update()
boid.check_edges()
boid.show()
新增顯示切割空間格線以及標示滑鼠游標所在位置3×3方格範圍的函數。
def show_grid_lines(cols, rows, resolution):
color = (255, 200, 200)
width, height = resolution*cols, resolution*rows
# 畫橫線
for y in range(0, height, resolution):
pygame.draw.line(screen, color, (0, y), (width-1, y))
pygame.draw.line(screen, color, (0, height-1), (width-1, height-1))
# 畫直線
for x in range(0, width, resolution):
pygame.draw.line(screen, color, (x, 0), (x, height-1))
pygame.draw.line(screen, color, (width-1, 0), (width-1, height-1))
def show_neighborhood(cols, rows, resolution):
mouse_x, mouse_y = pygame.mouse.get_pos()
col = int(mouse_x / resolution)
row = int(mouse_y / resolution)
for i in range(-1, 2):
for j in range(-1, 2):
cell_row = row + i
cell_col = col + j
if 0<=cell_row<rows and 0<=cell_col<cols:
rec_x = resolution*cell_col
rec_y = resolution*cell_row
rect = pygame.Rect(rec_x, rec_y, resolution, resolution)
pygame.draw.rect(screen, (255, 150, 150, 100), rect)
主程式：
# python version 3.10.9
import math
import random
import sys
import pygame # version 2.3.0
pygame.init()
pygame.display.set_caption("Example 5.12: Bin-Lattice Spatial Subdivision")
WHITE = (255, 255, 255)
screen_size = WIDTH, HEIGHT = 650, 400
screen = pygame.display.set_mode(screen_size)
FPS = 60
frame_rate = pygame.time.Clock()
n = 500 # boid的數量
flock = Flock()
for _ in range(n):
flock.add_boid(Boid(random.randint(0, WIDTH), random.randint(0, HEIGHT)))
resolution = 50
cols = WIDTH // resolution
rows = HEIGHT // resolution
grid = [[[] for _ in range(cols)] for _ in range(rows)]
while True:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
sys.exit()
elif event.type == pygame.MOUSEMOTION and event.buttons[0]:
# 按滑鼠左鍵拖曳可以投放boid
x, y = event.pos
flock.add_boid(Boid(x, y))
screen.fill(WHITE)
# 標示滑鼠游標所在位置3x3方格範圍
show_neighborhood(cols, rows, resolution)
# 顯示切割空間的格線
show_grid_lines(cols, rows, resolution)
# 清空grid的元素
for row in grid:
for item in row:
item.clear()
# 根據boid所在的位置將其歸屬到對應的grid元素中
for boid in flock.boids:
row, col = boid.locate_cell(boid, resolution)
grid[row][col].append(boid)
flock.run(grid, resolution)
pygame.display.update()
frame_rate.tick(FPS)
使用bin-lattice spatial subdivision演算法來降低模擬群聚行為時所需的計算量時，有個原書沒提到的小細節需要注意，那就是切割空間所用的格子邊長，至少要和判斷是否為鄰居的門檻值的大小一樣大。例如，如果align()方法中的門檻值設定為50，也就是
neighbor_distance = 50
那切割空間所用的格子邊長，也就是resolution，就必須大於或等於50；否則的話，有些原本符合門檻值的其他boid，就有可能會位於3×3方格範圍之外，因而被排除。
另一個處理這種情況的辦法，就是動態地擴大原本的3×3方格範圍。那要調整成多大範圍呢？計算方式很簡單，假設
n = math.ceil(門檻值 / resolution)
那就調整成
(2n+1)×(2n+1)
就可以了。
bin-lattice spatial subdivision演算法效果究竟有多好呢？Reynolds在論文中指出，工作量可以由O(N2)降為O(kN)，其中k是在一定的範圍內，boid可能聚集的最大數量。因此，從這裡可以很清楚地看出來，boid分佈得越平均k值會越小，而bin-lattice spatial subdivision演算法的效果就會越好。那萬一boid就老是會聚集在某一處呢？這時候bin-lattice spatial subdivision演算法的效果豈不是會大打折扣？尤有甚者，boid如果都集中在同一個方格內，那將會使得k=N，而工作量沒有減少，依舊是O(N2)；這樣豈不是回到原點，有沒有使用bin-lattice spatial subdivision演算法都一樣？
既然boid分佈不平均擠在一起會降低bin-lattice spatial subdivision演算法的效果，那把格子切小一點讓k值變小不就好了？這樣做也是可以的啦！不過，看看Example 5.12中的那張圖，有些區域其實挺空曠的，根本就沒幾隻boid在那裡，把這些空曠區域的格子切小一些，其實效益不大。那怎麼辦呢？切還是不切？
空曠的地方切大一點，擁擠的地方切小一點不就得了？又何必執著於所有格子都要一樣大！
要做到可以動態地根據擁擠的程度來決定方格的大小，可以使用quadtree這個資料結構。使用這個資料結構，可以在一個格子內的boid數量過多時，就動態地將這個格子分割成四等分，這樣每個格子內的boid數量就可以降下來，不至於過於擁擠；從下面這個例子可以看出其效果。
Example 5.13: Quadtree
程式如下：
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
class Rectangle:
def __init__(self, x, y, w, h):
# 中心點為(x, y)，寬、高為2*w、2*h的矩形
self.x = x
self.y = y
self.w = w
self.h = h
def contains(self, point):
return (self.x-self.w <= point.x < self.x+self.w and
self.y-self.h <= point.y < self.y+self.h)
def intersects(self, rectangle):
return not (self.x-self.w > rectangle.x+rectangle.w or
self.x+self.w < rectangle.x-rectangle.w or
self.y-self.h > rectangle.y+rectangle.h or
self.y+self.h < rectangle.y-rectangle.h)
class Quadtree:
def __init__(self, boundary, capacity):
self.boundary = boundary # Rectangle物件
self.capacity = capacity
self.points = []
self.divided = False
def subdivide(self):
x = self.boundary.x
y = self.boundary.y
w = self.boundary.w
h = self.boundary.h
nw = Rectangle(x-w/2, y-h/2, w/2, h/2)
self.northwest = Quadtree(nw, self.capacity)
ne = Rectangle(x+w/2, y-h/2, w/2, h/2)
self.northeast = Quadtree(ne, self.capacity)
sw = Rectangle(x-w/2, y+h/2, w/2, h/2)
self.southwest = Quadtree(sw, self.capacity)
se = Rectangle(x+w/2, y+h/2, w/2, h/2)
self.southeast = Quadtree(se, self.capacity)
self.divided = True
def insert(self, point):
if not self.boundary.contains(point):
return False
if len(self.points) < self.capacity:
self.points.append(point)
return True
else:
if not self.divided:
self.subdivide()
if self.northwest.insert(point):
return True
elif self.northeast.insert(point):
return True
elif self.southwest.insert(point):
return True
elif self.southeast.insert(point):
return True
def query(self, rectangle, found):
if not self.boundary.intersects(rectangle):
found = []
else:
for point in self.points:
if rectangle.contains(point):
found.append(point)
if self.divided:
self.northwest.query(rectangle, found)
self.northeast.query(rectangle, found)
self.southwest.query(rectangle, found)
self.southeast.query(rectangle, found)
return found
def show(self):
x = self.boundary.x
y = self.boundary.y
w = self.boundary.w
h = self.boundary.h
for point in self.points:
pygame.draw.circle(screen, (0, 0, 0), (point.x, point.y), 1)
if self.divided:
pygame.draw.line(screen, (0, 0, 0), (x, y-h), (x, y+h))
pygame.draw.line(screen, (0, 0, 0), (x-w, y), (x+w, y))
self.northwest.show()
self.northeast.show()
self.southwest.show()
self.southeast.show()
# python version 3.10.9
import random
import sys
import pygame # version 2.3.0
pygame.init()
pygame.display.set_caption("Example 5.13: Quadtree")
WHITE = (255, 255, 255)
screen_size = WIDTH, HEIGHT = 640, 360
screen = pygame.display.set_mode(screen_size)
FPS = 60
frame_rate = pygame.time.Clock()
boundary = Rectangle(WIDTH/2, HEIGHT/2, WIDTH/2, HEIGHT/2)
capacity = 8
quadtree = Quadtree(boundary, capacity)
n = 2000 # 點的數量
for _ in range(n):
point = Point(random.gauss(WIDTH/2, WIDTH/8), random.gauss(HEIGHT/2, HEIGHT/8))
quadtree.insert(point)
while True:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
sys.exit()
screen.fill(WHITE)
x, y = pygame.mouse.get_pos()
rect = pygame.Rect(x-50, y-50, 100, 100)
pygame.draw.rect(screen, (255, 150, 150), rect)
rectangle = Rectangle(x, y, 50, 50)
found_points = quadtree.query(rectangle, found=[])
for point in found_points:
pygame.draw.circle(screen, (50, 50, 50), (point.x, point.y), 2)
quadtree.show()
pygame.display.update()
frame_rate.tick(FPS)
在這個例子中，我們把每個格子的最大容量設定成8，也就是說，每個格子裡頭最多只會有8個點。但是，在圖片中特別用不同顏色標註出來的格子當中，卻有不只8個點在其中。這是怎麼回事？程式有錯？當然不是！這個程式是根據原書程式網站上的程式所改寫的，而且原書程式執行的結果也會出現這個現象。
那到底是怎麼了？怎會這樣？
原來，一個格子裡頭之所以會出現超過最大容量數量的點，是因為其中有些點並不屬於那個格子，只不過是畫的時候被畫在一起罷了。當我們把點一個一個塞進quadtree中時，如果格子滿了，我們會把這個格子切成四塊，並把這四個格子當成裡頭空空如也沒有任何點的全新格子，然後繼續把點塞進去。所以，當最後畫出來的時候，因為大小格子是畫在一起的，大格子裡頭的點，有可能會剛好出現在小格子的範圍內，這樣看起來就好像有超過最大容量數量的點被放進小格子當中了。
上述的做法，改用有學問一點的說法來說，就是我們把資料點一個一個放進quadtree的節點(node)中，當節點(node)滿了，就生出四個子節點(child node)，然後繼續把後續的資料點放到子節點中。要注意的是，生出子節點之後，父節點仍保有原來放進去的資料點，並未把他持有的資料點丟給子節點。所以，最後畫圖的時候，由於子節點是包含在父節點的範圍之中，如果父節點所保有的資料點剛好位於子節點的範圍中，那看起來就像是子節點，也就是某個格子，含有超過其最大容量限制的資料點數量了。
那要怎麼做，才能讓所有格子裡頭的資料點數量都不超過最大容量限制呢？方法其實挺簡單的，當節點生出子節點之後，把它原本持有的資料點全都丟給子節點就可以了。這樣做之後，就只有最尾端的葉節點(leaf node)會持有資料點，自然也就不會有父節點和子節點中的資料點同時出現在一個格子中的情況發生了。程式部分，只要修改Quadtree類別的insert()方法就可以了。在修改Quadtree類別時另外增加了depth和max_depth兩個屬性，用來追蹤並控制樹的最大深度。修改後的__init__()、insert()方法如下：
def __init__(self, boundary, capacity, max_depth, depth=0):
self.boundary = boundary # Rectangle物件
self.capacity = capacity
self.points = []
self.divided = False
self.max_depth = max_depth # 分割深度上限，超過此值則不再分割
self.depth = depth
def insert(self, point):
if not self.boundary.contains(point):
return False
if len(self.points) < self.capacity and not self.divided:
self.points.append(point)
return True
elif self.depth >= self.max_depth:
self.points.append(point)
return True
else:
if not self.divided:
self.subdivide()
for pt in self.points:
if self.northwest.insert(pt):
continue
elif self.northeast.insert(pt):
continue
elif self.southwest.insert(pt):
continue
else:
self.southeast.insert(pt)
self.points = []
if self.northwest.insert(point):
return True
elif self.northeast.insert(point):
return True
elif self.southwest.insert(point):
return True
elif self.southeast.insert(point):
return True
Exercise 5.20
修改Flock類別的run()方法：
def run(self, quadtree, threshold):
for boid in self.boids:
rectangle = Rectangle(boid.position.x, boid.position.y, threshold, threshold)
neighbors = quadtree.query(rectangle, found=[])
boid.flock(neighbors)
boid.update()
boid.check_edges()
boid.show()
修改Quadtree類別的insert()、query()方法：
def insert(self, boid):
point = Point(boid.position.x, boid.position.y)
if not self.boundary.contains(point):
return False
if len(self.boids) < self.capacity:
self.boids.append(boid)
return True
else:
if not self.divided:
self.subdivide()
if self.northwest.insert(boid):
return True
elif self.northeast.insert(boid):
return True
elif self.southwest.insert(boid):
return True
elif self.southeast.insert(boid):
return True
def query(self, rectangle, found):
# range為Rectangle物件
if not self.boundary.intersects(rectangle):
found = []
else:
for boid in self.boids:
point = Point(boid.position.x, boid.position.y)
if rectangle.contains(point):
found.append(boid)
if self.divided:
self.northwest.query(rectangle, found)
self.northeast.query(rectangle, found)
self.southwest.query(rectangle, found)
self.southeast.query(rectangle, found)
return found
主程式：
# python version 3.10.9
import math
import random
import sys
import pygame # version 2.3.0
pygame.init()
pygame.display.set_caption("Exercise 5.20")
WHITE = (255, 255, 255)
screen_size = WIDTH, HEIGHT = 650, 400
screen = pygame.display.set_mode(screen_size)
FPS = 60
frame_rate = pygame.time.Clock()
n = 500 # boid的數量
threshold = 50 # 判斷是否為鄰居的門檻值
flock = Flock()
for _ in range(n):
flock.add_boid(Boid(random.randint(0, WIDTH), random.randint(0, HEIGHT)))
boundary = Rectangle(WIDTH/2, HEIGHT/2, WIDTH/2, HEIGHT/2)
capacity = 5
while True:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
sys.exit()
elif event.type == pygame.MOUSEMOTION and event.buttons[0]:
# 按滑鼠左鍵拖曳可以投放boid
x, y = event.pos
flock.add_boid(Boid(x, y))
screen.fill(WHITE)
quadtree = Quadtree(boundary, capacity)
for boid in flock.boids:
quadtree.insert(boid)
flock.run(quadtree, threshold)
quadtree.show()
pygame.display.update()
frame_rate.tick(FPS)
在模擬boid的群聚行為時，使用bin-lattice spatial subdivision演算法和quadtree哪種效率比較高呢？比較起來，使用bin-lattice spatial subdivision演算法跑起來順暢多了。
為什麼？！原本不是希望利用quadtree來動態地決定方格的大小，好避免bin-lattice spatial subdivision演算法因boid過度擁擠而效率不彰嗎？怎麼搞到最後不僅沒比較好，反而效果比較差呢？
仔細觀察模擬的過程可以發現，boid並不是常常會擠在一起，而且擁擠的程度也不是那麼高。這也沒什麼好奇怪的，因為要讓boid展現出群聚行為的三條規則中，就有一條是「分離」，也就是boid會避免因彼此太靠近而撞在一起；這可能就是quadtree沒有達到預期效果的原因之一。
另一個quadtree沒有達到預期效果的原因，可能在於比起bin-lattice spatial subdivision演算法分割空間的的過程，建造quadtree的過程明顯要複雜多了。除此之外，在檢查某個範圍內有哪些boid時，比較一下Boid類別的locate_cell()方法和Quadtree類別的query()方法就可以很明顯看出來，query()方法要複雜很多。所以囉，不管是在建造方面或使用方面，quadtree都比人家複雜很多，那效率比人家差，應該也不會是什麼太奇怪的事了。
模擬boid的群聚行為時，使用不同方法執行速度上的差異，可以參考〈Comparing bins and quadtree optimizations of the boids simulation to the naïve approach〉
More Optimization Tricks
除了使用效率比較高的演算法之外，還有一些寫程式時的小技巧，可以讓程式跑得快一些。
在使用向量來處理問題時，常常會需要計算向量的大小。計算向量的大小需要開根號，這挺花時間的，能免則免。那在什麼樣的情況下可以不必真的把向量的大小算出來，但是又能夠達到原來的目的呢？這種情況通常會出現在比較大小的時候。例如，要判斷向量v=(x, y)的長度是不是大於10，把程式
if math.sqrt(x*x+y*y) > 10:
:
:
改寫成
if (x*x+y*y) > 100:
:
:
因為不需要開根號，所以在執行速度上就會比較快。在pygame.Vector2中，也有提供幾個可以避免計算開根號的的方法：
pygame.Vector2.magnitude_squared()
pygame.Vector2.length_squared()
pygame.Vector2.distance_squared_to()
另一個可以減少計算量加快程式執行速度的技巧，就是善用查表法。有些計算式的值會一再用到，與其每次都花時間重新計算，不如把這些值存起來，要用的時候直接拿出來用還比較快；尤其像是三角函數這類計算耗時的函數更是如此。例如，下列程式
for _ in range(10000):
print(math.sin(math.pi/10))
如果改寫成
value = math.sin(math.pi/10)
for _ in range(10000):
print(value)
那就只需計算1而不是10000次sin的值，執行速度當然會比較快。
在下面這個例子中，因為要一再用到sin和cos的值，所以就先將這些值算出來並存放在list中。這個list就是我們所需要的對照表，當後續要用到這些sin、cos的值時，就直接查表，這樣可以省下不少重複計算sin、cos值的時間。
Example 5.14: Sin/Cos Lookup Table
# python version 3.10.9
import math
import sys
import pygame # version 2.3.0
pygame.init()
pygame.display.set_caption("Example 5.14: Sin/Cos Lookup Table")
WHITE = (255, 255, 255)
screen_size = WIDTH, HEIGHT = 650, 400
screen = pygame.display.set_mode(screen_size)
FPS = 60
frame_rate = pygame.time.Clock()
center_x = WIDTH/2
center_y = HEIGHT/2
sin_value = []
cos_value = []
# 建立sin、cos查詢表，角度的單位為「度」，精確度為1度
for i in range(360):
angle_deg = i*math.pi/180
sin_value.append(math.sin(angle_deg))
cos_value.append(math.cos(angle_deg))
frame_count = 0
while True:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
sys.exit()
screen.fill(WHITE)
# sin的值介於-1和1之間，所以圓的半徑會在0~100之間變化
radius = 50 + 50*sin_value[frame_count % 360]
for theta in range(0, 360, 5):
x = center_x + radius*cos_value[theta]
y = center_y + radius*sin_value[theta]
pygame.draw.circle(screen, (0, 0, 0), (x, y), 2)
frame_count += 1
pygame.display.update()
frame_rate.tick(FPS)
查表這個技巧說穿了，其實就是以空間換取時間。這就好比把東西先買回來堆在家裡，要用時就不需要多花時間出門去買；佔用了家裡的空間，但卻可以節省出門購買的時間。
原書另外還提到要避免建立太多向量物件，以免因為佔用太多記憶體空間而影響執行速度。雖然現在的電腦記憶體都很夠用，但在寫程式時還是應該要盡量避免太揮霍記憶體的寫法。不過，也不要因為想要減少記憶體用量，而影響了程式的可讀性。例如，把程式
def seek(self, target_position):
desired = target_position - self.position
if desired.length() > 1.e-5:
desired.scale_to_length(self.max_speed)
steer = desired - self.velocity
if steer.length() > self.max_force:
steer.scale_to_length(self.max_force)
self.apply_force(steer)
改成
def seek(self, target_position):
desired = target_position - self.position
if desired.length() > 1.e-5:
desired.scale_to_length(self.max_speed)
desired = desired - self.velocity
if desired.length() > self.max_force:
desired.scale_to_length(self.max_force)
self.apply_force(desired)
雖然少用了一個變數steer，但程式的可讀性就沒那麼好了。
Exercise 5.21
略
