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

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

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

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

本文環境 #

• Python 3
• Google Colab

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 個兩端都能夠高效率進行 pop 與 push 操作的資料結構，而且時間效率屬於 O(1) 級別。

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() 的時間，其結果如下所示：

從實驗結果可以清楚看到，執行 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 最左邊添加新元素

以圖表示會更容易理解：

移動平均(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