Python 效能之鬼!你應該學會使用的 deque !

Posted on  Apr 1, 2024  in  Python 程式設計 - 中階  by  Amo Chen  ‐ 4 min read

程式的效能並不是天生具備,而是榨出來的,特別是對於 Python 這門程式語言而言,如果想要做到 High Performance 的話,有些魔鬼就藏在細節裡。

舉常見的 list 為例,你知道 list 在執行 pop(0)insert(0, value) 是效率較差的嗎?如果你的應用必須經常呼叫 pop(0)insert(0, value) 的話,建議你換個資料結構吧!使用 deque 將會帶來效率的提升!

本文將帶你認識 Python 的 deque 以及它在何種特定情況下能夠帶來效率的提升!

本文環境

deque 介紹

deque (其發音為 deck)又稱 “double-ended queue” ,是 Python collections 模組所提供的 1 個類別 。使用方法則與 Python 內建資料型態 List 雷同。

deque 是堆疊(stack)與佇列(queue)的一般化(generalization),也就是說你可以把 deque 當作 stack 或者 queue 使用都沒問題。

可能有人會好奇—「 list 也可以當 stack 或者 queue 使用,為什麼 Python 還要特別提供 1 個 deque 呢?」

官方文件其實已經為此做出解答,原因在於 deque 是 1 個兩端都能夠高效率進行 poppush 操作的資料結構,而且時間效率屬於 O(1) 級別。

deque.png

p.s. Python deque 也是 thread-safe 的資料型態

Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

而單純使用 list 是無法兩端都能夠做到時間效率 O(1) 的,只要是使用 list 操作 pop(0)insert(0, the_value) 就會有 O(n) 的時間成本,因為要重新對記憶體裡的 list 排順序,例如執行 insert(0, v) 之後,第 1 個元素要改成排第 2 個,第 2 個元素要改成排第 3 個,以此類推。

Though ~list~ objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

deque vs list 效能實驗

我們針對 deque 與 list 進行 1 項各自執行 pop(0) 的實驗,如此就能夠對 list 在 pop(0)insert(0, the_value) 的效率問題有更實際的體會。

首先,我們可以建立 1 個 list, 裡面含有 100,000 個隨機整數,並且利用該 list 建立 1 個 deque:

from collections import deque
from random import randint

x = [randint(0, 10000) for _ in range(0, 100000)]
dq = deque(x)

接著用 Google Colab 的 %time 試著測量 2 者分別使用 pop(0)popleft() 的時間,其結果如下所示:

deque-time.png

從實驗結果可以清楚看到,執行 x.pop(0) 將 list 清空耗時約 964ms, 但是 dq.popleft() 卻只耗時 16.7ms, 兩者在效能的差距如此驚人!

因此,如果你的 Python 應用程式碼的 list 有 pop(0), insert(0, the_value) 等操作的話,建議使用 deque 取代 list ,絕對是可以提升一些效率。

deque 使用方法

deque 的使用方法很簡單,只要給定它 1 個 iterable 就可以轉成 deque, 此外也可以為 deque 設定 1 個最大長度(maxlen):

deque([iterable[, maxlen]])

例如,以下將 list [1, 2, 3, 4, 5] 轉為 deque:

>>> from collections import deque
>>> list = [1, 2, 3, 4, 5]
>>> dq = deque(list)
>>> dq
deque([1, 2, 3, 4, 5])

以下設定最大長度為 3, 而且故意給定超過長度 3 的 list, 可以看到超過長度之後,最左邊的元素會被捨棄,也就是 1, 2 被捨棄:

>>> from collections import deque
>>> deque([1, 2, 3, 4, 5], 3)
deque([3, 4, 5], maxlen=3)

這樣的效果,等同於只取最後 n 個元素,因此,我們可以用 deque 製作類似 Linux tail 指令的 Python 程式:

$ tail -n 10 file.txt

上述 tail 指令如果用 deque 實作,如下所示:

def tail(filename, n=10):
    with open(filename) as f:
        return deque(f, n)

appendleft() 與 popleft()

使用過 list 的人一定對 pop()append(x) 不陌生, deque 也有相同的方法,作用也與 list 的 pop()append(x) 相同。

與 list 不同的是, deque 額外提供 popleft()appendleft(x) 2 個方法,其作用為:

  • popleft() 取出 deque 最左邊元素,並從 deque 中移除該元素
  • appendleft(x) 從 deque 最左邊添加新元素

以圖表示會更容易理解:

deque.png

移動平均(Moving Average)

使用 deque 的 popleft()appendleft(x) 2 個方法可以很簡單地實作移動平均(移動平均是商業/股票分析常見的分析項目之一,詳見 Moving Average)。

import itertools
from collections import deque


def moving_average(iterable, n=3):
    it = iter(iterable)
    d = deque(itertools.islice(it, n-1))
    d.appendleft(0)
    s = sum(d)
    for elem in it:
        s += elem - d.popleft()
        d.append(elem)
        yield s / n

上述 moving_average() 函式會從第 1 個元素開始做算 n 個數值的平均,例如 moving_average([40, 30, 50, 46, 39, 44], 2) ,它會算 [40, 30] 的平均、[30, 50] 的平均、 [50, 46] 的平均、以此類推。

rotate()

deque 還有個有趣的方法 rotate(n=1) ,這個方法的效果等同於將最右邊的元素 pop 之後,新增到 deque 的最左邊,等同於下列程式碼:

dq.appendleft(
    dp.pop()
)

rotate() 的參數為 n 代表做幾次 rotate 的意思,預設為 1 ,舉 deque([1, 2, 3, 4]) 為例,經過 2 次 rotate 就會變成 deque([3, 4, 1, 2]) :

>>> from collections import deque
>>> dq = deque([1, 2, 3, 4])
>>> dq.rotate(2)
>>> dq
deque([3, 4, 1, 2])

rotate() 相當適合用在輪詢(round-robin)等用途之上。

總結

雖然 deque 並不在學習 Python 的必要路徑之上,而且也相對較少文章探討使用 deque 的時機與效能優勢,但對於寫出高效率的 Python 程式而言, deque 肯定是必須認識的其中一項。

以上!

Enjoy!

References

https://docs.python.org/3/library/collections.html#collections.deque

對抗久坐職業傷害

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

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

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

贊助我們的創作

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

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