使用Python的collections.deque優化代碼效率

一、背景介紹

在Python中，列表是一種常見的數據結構，用於存儲多個元素。列表在操作上非常方便，可以通過索引快速訪問和修改元素，也可以使用切片進行批量操作。然而，在某些情況下，列表操作的效率可能比較低，比如在需要頻繁從列表的左側或右側添加或刪除元素時。這時，我們可以使用Python中的collections.deque來優化代碼的效率。

二、collections.deque的基本用法

Python的collections模塊中提供了一個雙端隊列類deque，它實現了在隊列兩端快速添加（append）和刪除（pop）元素的操作。deque類主要提供了以下幾種方法：

1. append(x)：在deque的右側添加一個元素x，時間複雜度為O(1)。

2. appendleft(x)：在deque的左側添加一個元素x，時間複雜度為O(1)。

3. pop()：從deque的右側刪除一個元素，並返回該元素，時間複雜度為O(1)。

4. popleft()：從deque的左側刪除一個元素，並返回該元素，時間複雜度為O(1)。

下面是一個簡單的例子，演示了deque的基本用法：

from collections import deque

# 創建一個空的deque
d = deque()

# 在右側添加元素
d.append(1)
d.append(2)
d.append(3)

# 在左側添加元素
d.appendleft(0)

# 刪除右側元素
d.pop()

# 刪除左側元素
d.popleft()

# 列印剩餘元素
print(d)  # deque([1, 2])

三、deque的優勢

相較於列表，deque有以下優勢：

1. 在首尾插入和刪除元素的時間複雜度為O(1)，而列表的時間複雜度為O(n)。

2. deque可以跟list一樣按照索引和切片去操作，但是當deque中的元素非常多時，它的操作速度仍然非常快，而列表的操作速度會隨著元素數量的增加而變得越來越慢。

3. deque還提供了rotate(n)方法，可以將deque循環向右旋轉n步，如果n為負數，則循環向左旋轉。這個方法非常方便，在一些滾動窗口的場景中可以很好的應用。

下面是一個使用deque的例子，演示了如何用deque計算一個滑動窗口的最大值：

from collections import deque

def sliding_window_maximum(nums: list[int], k: int) -> list[int]:
    # 構造一個雙端隊列，存儲nums索引
    d = deque()
    res = []

    for i in range(len(nums)):
        # 將隊列中所有不在[i-k+1, i]區間的索引都刪除
        while d and d[0] < i - k + 1:
            d.popleft()
        
        # 將隊列中比當前元素小的索引都刪除
        while d and nums[d[-1]] = k - 1:
            res.append(nums[d[0]])

    return res

這個函數用於計算一個長度為k的滑動窗口，在每個窗口中返回窗口內的最大值。具體實現方法是，使用一個雙端隊列來維護元素的索引，隊列的左側存儲當前窗口內的最大值。每次向右移動窗口時，先將隊列中所有不在[i-k+1, i]區間的索引都刪除，然後將隊列中比當前元素小的索引都刪除，在將當前元素的索引加入隊列，最後將隊列左側的元素（即窗口內的最大值）加入結果列表。這個方法的時間複雜度為O(n)，是一種比較高效的計算滑動窗口最大值的方法。

四、總結

Python的collections.deque類是一種非常高效的數據結構，可以用於優化一些頻繁在列表兩端添加或刪除元素的場景。deque主要提供了append、appendleft、pop、popleft、rotate等方法，它的優勢在於在首尾插入和刪除元素的時間複雜度為O(1)，同時deque也可以跟list一樣按照索引和切片去操作。在滑動窗口這種場景中，deque的效率非常高，我們可以使用deque來計算滑動窗口的最大值。