發表於 Python

【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 是對的!

作者:

一位 熱愛資工領域、喜歡好笑事物、偶爾打打網球 的學生 ! For A Better Me!

發表迴響

Please log in using one of these methods to post your comment:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.