【Python】List V.S Set 時間複雜度比較 Time Complexity

前言:

剛剛在看 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 是對的!

• 

•