其實這一篇真正的重點並不在 Python 本身, 只是剛好我使用的語言是 Python 而已。其實不管什麼語言都是適用的。
以下我來說明我是如何把原本執行時間為一個多小時的程式改成只要花三秒, 然後又變成零秒。
先來描述一下我的工作環境。回到我前兩篇的情境, 我手頭上有一批經銷商資料需要處理。原本使用得好好的, 但當經銷商資料筆數成長到十萬筆之後, 程式的效能就很明顯地掉下來了。
十萬筆說多不多, 說少不少, 但每遇到迴圈有套疊的情況時, 效態就變得非常的糟糕。這逼得我不能再偷懶, 非得開始想辦法解決不可。
很快地, 我找到了瓶頸所在。由於一開始思慮不周, 在一個搜尋經銷商的方法中使用了 lambda 匿名程式：
# 程式一
list(filter(lambda m: m.RetailerId == id, Retailers))
當經銷商數很少時, 這段效能是相當 OK 的。就算數目達到一千筆, 都還算快。
然而, 由於它外面還套了一個稍為小一點的迴圈, 所以它的效能指標是 O(n2)。可以想見, 當它數量來到十萬筆之後, 這段小程式就變成了元兇。執行完, 竟然要花掉一個小時以上(量測執行時間的方法可參考我在上一篇提到的 ShowDuration decorator)。
像這種問題, 我以往都會馬上去套用 Binary Search。不過在網路上搜尋時, 無意中發現原來 Python 的 list 本來就有提供 index 功能, 可以從已經排序過的 list 裡立即找到對應的 key 值：
# 程式二
keylist = []
for i in range(len(Retailers)):
keylist.append(Retailers[i].RetailerId)
index = keylist.index(retailerid)
雖然要另外加上一個 keylist (如果原來的 list 已經排序過, 就不需要再額外建立這個 keylist), 但是一執行之下, 只要花三秒! 本來要花一個多小時的, 現在變成三秒!
我不知道 Python 的這個 index 方法是採用什麼 algorithm; 但是我原本就已經把 Binary Search 方法寫好了：
def BinarySearch (arr, l, r, target):
''' Binary search an array.
'arr' must be already sorted, while 'target' must be comparable.
e.g.
arr = [ 2, 3, 4, 10, 40 ];
result = BinarySearch(arr, 0, len(arr)-1, 10)
# result = 3 (its index is 3) '''
if r >= l:
mid = int(l + (r - l)/2)
if arr[mid] == target:
return mid
elif arr[mid] > target:
return BinarySearch(arr, l, mid-1, target)
else:
return BinarySearch(arr, mid+1, r, target)
else:
return -1
不用白不用。於是我又把原來的程式套用了這個 BinarySearch() 方法：
# 程式三
keylist = []
for i in range(len(Retailers)):
keylist.append(Retailers[i].RetailerId)
index = BinarySearch(keylist, 0, len(Retailers)-1, retailerid)
沒想到一執行下去, 耗用時間竟然變成 0 秒!
Binary Search 的效能指標一般都是 O(Log(n)); 在我的環境下應該是 O(nLog(n))。不過因為我的資料「只有」十萬筆, 導致執行時間短到不足一秒, 才會顯示為 0 秒。跟一開始的做法比較起來, 簡直有天壞之別。
有時候, 稍為動點腦筋, 成果也可以十分豐碩。這就是寫程式讓人著迷的地方。