好文分享 — 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 的功力！