您的位置:

Python deque:高效地进行双端操作

一、概述

Python deque(双端队列)是Python标准库collections模块中的一个数据容器,它是一种具有线性表的性质,并且可以在队列的两端进行添加和删除元素。与列表相比,deque除了支持队列和栈的操作,还提供了旋转、均摊复杂度为O(1)的appendleft和popleft方法。

有时候我们需要使用队列,找到最前面/最后面的项目,或者需要从中删除一些项目,那么deque就可以派上用场。deque是一个双端队列,可以在队列的头部或尾部快速插入和删除元素,具有高效地进行双端操作的特性。

二、deque基础使用

Deque实例可以从左端和右端添加或删除元素。更具体来说,在deque开头添加和删除元素是O(1)的操作,但将一个元素插入中间是比较慢的,因为它需要移动内部元素以为新元素腾出空间。以下是deque的基本操作。


from collections import deque

d = deque()
d.append('a')           # 添加到队列右侧
d.appendleft('b')       # 添加到队列左侧
d.extend(['c', 'd'])    # 在队列右侧添加多个元素
d.extendleft(['e', 'f'])# 在队列左侧添加多个元素

print(d)                # deque(['f', 'e', 'b', 'a', 'c', 'd'])

d.pop()                 # 从队列右侧删除元素
d.popleft()             # 从队列左侧删除元素

print(d)                # deque(['b', 'a', 'c'])

三、deque的高效性

deque作为一个双端队列,在队列两端同时添加和删除元素的时候具有高效性。例如,可以使用deque在一个大数组上模拟一个滑动窗口,下面我们通过一个例子来演示deque的高效性。

我们有一个长度为100,000的列表,要在其中找到长度为100的最大子序列。假设我们用列表进行求解的话,代码会是这样的:


a = [...]    # 长度为100,000的列表
k = 100

largest_sum = float('-inf')
for i in range(len(a)-k):
    current_sum = sum(a[i:i+k])
    largest_sum = max(largest_sum, current_sum)

在上面的代码中,我们遍历了列表中的每个子序列,并在其中找到了最大子序列。但是由于要遍历很多子序列,时间复杂度为O(n * k)。

改用deque,我们可以将时间复杂度降至O(n),如下所示。


from collections import deque

a = [...]         # 长度为100,000的列表
k = 100

d = deque()
largest_sum = float('-inf')
for i, item in enumerate(a):
    # 弹出过期数据
    if len(d) == k:
        d.popleft()

    # 加入新数据
    d.append(item)

    if len(d) == k:
        current_sum = sum(d)
        largest_sum = max(largest_sum, current_sum)

在上面的代码中,我们使用deque维护了一个长度为100的滑动窗口,时间复杂度为O(n),具有比上面使用列表更高的效率。

四、deque的其他用途

除了作为双端队列,deque还有其他的用途。比如,在操作系统中,deque被用来存储系统调用。在图形学和游戏中,deque被用来存储和管理动画帧。在Web框架中,deque被用来存储客户请求和消息日志。

五、总结

deque是Python标准库中的一个双端队列,具有线性表的性质,并且可以在队列的两端进行添加和删除元素。与列表相比,deque除了支持队列和栈的操作,还提供了旋转、均摊复杂度为O(1)的appendleft和popleft方法。deque可用于从队列中查找最前面/最后面的项目,或者需要从中删除一些项目,具有高效地进行双端操作的特性。该数据容器在操作系统、游戏等领域有广泛应用。