好文分享 — Python Big O: the time complexities of different data structures in Python

Python 的其中一項優點是內建很多高實用性的資料結構(data structure)供人使用,需要的時候信手捻來即可,不需要特別安裝套件或者花時間重新實作,例如 Deque, Set, Counter, Heap, Dict, List 等等,每一個都有各自適用的情境,不過我們卻相對少認真關注它們在各種情境的效率,這導致新手容易寫出效率較低的 Python 程式碼。

譬如下列範例實際上是時間複雜度 O(n^2) 的情況:

target_ids = [...] # n elements
data = [...] # m elements
counts = defaultdict(int)
for x in data:
    if x['id'] in target_ids:
        counts[x['id']] += 1

造就上述程式碼的原因在於開發者沒意識到 in List 實際上是時間複雜度為 O(n) 的操作 ,再加上外層的 for 迴圈,使得整體時間複雜度為 O(m x n) ,我們可以簡化為 O(n^2) 表示,屬於時間效率不好的情況。

另外,當我們還需要找出 counts 裡的前 k 名時,又可能進一步產生下列程式碼:

top_3_values = sorted(counts.values(), reverse=True)[:3]
for k, v in counts.items():
    if v in top_3_values:
        print(k, v)

上述程式在 sorted(...) 的部分,時間效率為 O(n * log n) ,而 for 迴圈的部分同樣有 O(n^2) 的問題。

但這些種種的問題,其實只要對 Python 各種資料結構在各種情境的時間複雜度有些了解,就可以避免效率問題,前述的程式可以改成:

from collections import Counter
target_ids = set([...]) # n elements

data = [...] # m elements
counts = Counter()
for x in data:
    if x['id'] in target_ids:
        counts[x['id']] += 1

for k, v in counts.most_common(3):
    print(k, v)

上述程式將 target_ids 改為使用 Set, 如此一來,在執行 in target_ids 的時間複雜度會變為 O(1) ,第 1 個 for 迴圈整體時間複雜度就從 O(n^2) 變為 O(n) ;另外, counts 也改為使用 Counter, 我們可以借助其 most_common(k) 方法,以時間複雜度 O(n log k) 取得前 k 名,相較於前述效率較差的 O(n * log n) + O(n^2) 的寫法,我們透過適合的資料結構將時間效率降為 O(n log k) ,而且程式也變得更簡潔。

而這些常用的資料結構與各種情況下的時間複雜度,都有好心人整理在 “Python Big O: the time complexities of different data structures in Python” 一文,大家可以花點時間看完,增強一下 Python 的功力!

FOLLOW US

對抗久坐職業傷害

研究指出每天增加 2 小時坐著的時間,會增加大腸癌、心臟疾病、肺癌的風險,也造成肩頸、腰背疼痛等常見問題。

然而對抗這些問題,卻只需要工作時定期休息跟伸展身體即可!

你想輕鬆改變現狀嗎?試試看我們的 PomodoRoll 番茄鐘吧! PomodoRoll 番茄鐘會根據你所設定的專注時間,定期建議你 1 項辦公族適用的伸展運動,幫助你打敗久坐所帶來的傷害!

贊助我們的創作

看完這篇文章了嗎? 休息一下,喝杯咖啡吧!

如果你覺得 MyApollo 有讓你獲得實用的資訊,希望能看到更多的技術分享,邀請你贊助我們一杯咖啡,讓我們有更多的動力與精力繼續提供高品質的文章,感謝你的支持!