前言:
剛剛在看 PyCon 2018 ( Big-O: How Code Slows as Data Grows )的演講紀錄(詳細介紹在下面~),看完後好奇自己寫 Python 測試 Big-O 比較時間一番!
這篇會介紹到
- PyCon 2018 演講主題
- Big-O 時間複雜度介紹
- Python 各資料結構 Time Complexity 比較
- List 與 Set 時間比較
PyCon 2018 演講主題
主題: Big-O: How Code Slows as Data Grows
講者: Ned Batchelder
這場演講的主題是在介紹 Big-O 對程式的影響,後面會介紹到 Python 怎麼利用不同的 type 降低 Big-O 的 Order,影片長度大概30分鐘左右,講者用蠻生活化的例子介紹不同 Order 的比較,蠻精彩的!!推薦大家如果聽得懂英文的話可以聽聽看!
Big-O 時間複雜度介紹
Big-O 應該是資工一定會學到的東西吧!
不過不知道我的讀者是不是也有一些其他科系的呢?
我這邊也解釋一下 Big-O 吧!
Big-O 英文名稱為 Big O Notation,在課本或是網路上你會看到很多種名稱
像是:
- Complexity
- time complexity
- algorithmic complexity
- asymptotic complexity
那 Big-O 可以用來幹嘛呢?
Big-O 主要是用來評估演算法是否快速的指標。
我舉兩個例子說明會更明白
Constant Time O(1)
像下面這段程式碼,不管我的 mlist 多大都不會影響到我取第四個元素的時間,這樣的演算法就是常數時間。
mlist = [1,2,5,7,7,4] print(mlist[3])
Linear Time O(n)
至於下面這段程式碼,單純傳入一個全是數字的陣列,找到想搜尋的數字後回傳數字的index,我們可以發現隨著我傳進 function 的 list 擴大,我搜索的時間也會隨之線性上升,像這樣的演算法我們稱為「Linear Time」演算法。
def findNum(mlist: list, num:int): for index, n in enumerate(mlist): if num == n: return index return None findNum([i for i in range(100)], 35)
其他複雜度:
符號 | 名稱 |
---|---|
O(1) | 常數 Constant Time |
O(n) | 線性 Linear Time |
O(log n) | 對數 Log Time |
O(n log n) | 線性對數,很多有名的排序演算法就是這個 Order 喔! |
O(n^2) | 平方,基本上這樣的演算法寫CPE就會被題目阻擋了QAQ |
O(n!) | 階乘 |
Python 各資料結構 Time Complexity 比較:
這邊主要介紹的是 CPython 的比較,在 Wiki Python 也有特別放一頁介紹這些資料結構的時間複雜度。
list:
Data Structure | 運算 | Big-O 時間複雜度 | |
---|---|---|---|
list | Copy | O(n) | |
list | Insert | O(n) | |
list | x in list | O(n) |
set:
Data Structure | 運算 | Big-O 時間複雜度 | |
---|---|---|---|
set | x in list | O(1) | |
set | 差集 | O(n) |
dict:
Data Structure | 運算 | Big-O 時間複雜度 | |
---|---|---|---|
dict | x in list | O(1) | |
dict | get、set | O(1) |
可以看得出來其實 set 比 list 快很多(當然是在某些時候啦!)
如果沒有相同元素的話,使用 set 應該是會比較好的!
List 與 Set 時間比較:
看完演講,就想要試試看實際 search 的速度!
不過結果有點出乎意料之外,似乎陣列裡的資料會影響搜尋的速度(儘管都只是數字)
Code 解釋:
為了在 Python “中" 測量時間,我使用的是 timeit.timeit
但是她只能接受 string 的程式碼
所以我就分別把 list 和 set 的程式碼放入 sList 和 sSet 中去執行
為了不要有塊取記憶體的影響,我還特地加入 垃圾回收 的機制,結果在下面的兩張圖!
import matplotlib.pyplot as plt from timeit import timeit import numpy as np import gc gc.collect() sList = "True if 5164546151651 in [i for i in range({})] else False" sSet = "True if 5164546151651 in (i for i in range({})) else False" ltime = [] stime = [] testLevel = np.arange(10000) for topCell in testLevel: print(topCell) ltime.append( timeit(sList.format(topCell), number=1) ) stime.append( timeit(sSet.format(topCell), number=1) ) gc.collect() plt.plot(np.arange(len(testLevel)), ltime, "r") plt.plot(np.arange(len(testLevel)), stime, "b") plt.show()
紅色線是 Set 的速度表示
紅色線是 Set 的速度表示
Y軸是速度
X軸是 0~10000分別的測試
可以發現在陣列資料為 0~3500 時 Set 速度瞬間變慢!!
還在理解原因,不過可以從左右兩張圖了解到
Set 普遍比 List 搜尋速度快一些!
證明 Big-O 是對的!
0~10000 速度 Set(紅色)比List(藍色)速度快一些