一、背景介绍
在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来计算滑动窗口的最大值。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/243899.html
微信扫一扫 
支付宝扫一扫 