Python collections模块-deque

概览

  • deque 是用来干什么的? deque vs list vs Queue
  • deque 的初始化
  • deque 的一些方法
  • deque 的特性

deque是用来干什么的

与 list 和 Queue 对比, deque 更像 list , Python官方的描述是: deque 是一个类似列表的序列结构, 优化了两端的数据操作. 这里的两端是指序列的开始与结束, 从我们写代码的角度看, [1, 2, 3]这样的列表有左右端, 而右端往往是代码编写中操作更自然的一端, 就像我们谈到列表添加元素, 往往是添加到右端.

对于 list 来说, list.append(n) 和 list.pop() 是O(1)的复杂度,  此时操作的是右端. 然而对于 list.insert(0, n) 和 list.pop(0) 这两种左端操作来说, 就是O(n)的的复杂度, 因为Python中的列表在C语言层面是用数组实现的, 操作左端的涉及到的数据拷贝问题比较严重. 如果无法理解这个问题, 可以尝试用C语言实现一个支持动态扩容的 list.

那我们应该明白, 官方文档描述的, deque 优化的实际上应该主要是左端操作了, deque 提供了两个方法, 对应上面提到列表的左端操作,  分别是 deque.appendleft(n) 对应 list.insert(0, n) 和 deque.popleft() 对应 list.pop(0). appendleft 和 popleft 是O(1)复杂度, 由列表的 O(n) 变成了 O(1).

这篇文章我不会细说 deque 的实现细节, 只会点到即止. 当考虑到需要操作两端的数据, 你应该可以很快的联想到链表这种数据结构. 链表增加或者删除元素很容易, 但是索引访问元素会比数组耗时, deque 的实现比链表略复杂, 它使用了双向链表.

deque vs list 实际上就演变成了链表 vs 变长数组

链表
  • 链表为栈, 队列提供了良好的支持, 因为链表不要求在内存空间上连续, 可以很好的操作端点上的数据.
  • 索引访问的复杂度是O(n), 包括Python里面切片的概念, 类似 `nums[1] nums[1:3], 虽然 deque 不支持切片.
变长数组
  • 变长数组的索引访问, 常量级别的切片操作可以只花费O(1)的复杂度,
  • 当数据增加(减少) 需要扩容(缩容), 或者在左端新增(删除)元素时, 数据拷贝的代价非常大.
  • 变长数组为了避免频繁的扩容缩容, 空间总是会预留一部分, 这一部分也是空间上的损失.

deque 和 Queue 的主要区别在于:

  • deque 支持索引访问, 但是 Queue 不支持. Queue 的核心API是 put, get 两种操作.
  • 还有设计上的不同:
  • 往一个满了的队列中 put 元素, 和从一个空的队列中 get 元素这两种操作一般都是会阻塞的.
  • 但是往一个满了的 deque 中添加元素的时候, 会自动把另一端的元素移除,  从空的 deque 取出元素的时候会抛出异常.
  • 请注意满的 Queue 或者 deque 这个概念只存在于设置了其大小的时候, 因为Python里面, 如果你不设置大小的话, 我们认为它们的容量可以无限增长.
  • Queue 的这种行为更符合多线程编程的模型, 生产者消费者模型. 同时 deque 和 Queue 都是线程安全的. 关于Python里面线程安全这个概念, 我会出一个系列的文章来解释,  此时你只要知道他们是线程安全的就好了.

deque的初始化

  • 通过一个可迭代对象初始化, 常用的包括字符串, 列表, 元组, 字典, deque 的容量与可迭代对象中的元素数量无关.
from collections import deque

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

# 如果没有指定maxlen参数, deque 的容量是无限大
d.append('d')
print(d)
# deque(['a', 'b', 'c', 'd'])
  • 不指定任何参数
from collections import deque

d = deque()
print(d)
# deque([])
  • 指定maxlen参数, maxlen 决定了 deque 的容量.
from collections import deque

d = deque(maxlen=4)
print(d)
# deque([], maxlen=4)
for i in range(5): # 0, 1, 2, 3, 4
    d.append(i)
print(d)
# deque([1, 2, 3, 4], maxlen=4) 
# 设置了maxlen=4之后, deque 中的元素最多为4个

deque 的一些方法

deque的方法与列表比较相似,  简单的方法不去做详细的解释

  • append, appendleft
  • pop, popleft
  • extend, extendleft
# 用代码解释一下extendleft

l = ['a', 'b', 'c']
# d1 与 d2 初始化相同
d1 = deque('123')
d2 = deque('123')

# 操作d1 用 extendleft 方法
d1.extendleft(l)

# 操作d2, 遍历l, 依次appendleft
for i in l:
    d2.appendleft(i)

# 上述两种操作是相同的效果
print(d1)
# deque(['c', 'b', 'a', '1', '2', '3'])
print(d2)
# deque(['c', 'b', 'a', '1', '2', '3'])

assert d1 == d2
# True
  • clear: 清空 deque
  • count(n): 计算 deque 中 n 的个数
  • insert(idx, n): 在索引为idx处插入元素n
  • reverse: 反转 deque
  • rotate(n): 所有元素向右移动 n 位, 右端点的下一位是左端点. 参考蛇吃自己的尾巴.

deque的特性

  • 没有设置 maxlen 时, deque 的容量是无限大
  • 设置了 maxlen 时, deque 有满的概念, 而往一个满的 deque 中添加元素时, 它会自动移除另一端的元素. 请注意这里是另一端, 意味着如果你往一个满的 deque 中 append 时, 它会自动移除左端点 (popleft) , appendleft 时, 它会自动移除右端点 (pop).
from collections import deque

d = deque('1234', maxlen=4)
print(d)
# deque(['1', '2', '3', '4'], maxlen=4)
d.append('5')
print(d)
# deque(['2', '3', '4', '5'], maxlen=4)
# 右端新增 5, 移除了左端的 1

d.appendleft('0')
print(d)
# deque(['0', '2', '3', '4'], maxlen=4)
# 左端新增 0, 移除了右端的 5

d.extend(['a', 'b'])
print(d)
# deque(['3', '4', 'a', 'b'], maxlen=4)
# 右端新增 a, b, 移除了左端的 3, 4

d.extendleft(['c', 'e'])
print(d)
# deque(['e', 'c', '3', '4'], maxlen=4)
# 左端新增 e, c, 移除了右端的 a, b
  • 验证 deque (链表) 与 list (动态数组) 的性能
# 希望读者不要盲目修改测试代码
# 因为我可以一定程度上为我写的测试代码和其结果的正确性负责
# 如果你盲目修改导致了错误的结论... 希望你不要去误导别人

from collections import deque
from copy import deepcopy
from random import randint
import time


def timefunc(func, *args, repeat=1, cache=False, **kwargs):
    total = 0
    if cache:
        cached_args = deepcopy(args)
        cached_kwargs = deepcopy(kwargs)
    for _ in range(repeat):
        start_time = time.time()
        func(*args, **kwargs)
        end_time = time.time()
        total += (end_time - start_time)
        if cache:
            args = deepcopy(cached_args)
            kwargs = deepcopy(cached_kwargs)
    return total

# 测试索引访问
def random_access(l, idxs):
    for idx in idxs:
        _ = l[idx]

# 测试右端的新增删除
def append_pop(l, s):
    for i in range(s):
        l.append(i)
    for _ in range(s):
        l.pop()

# 测试右端新增, 左端删除
def append_popleft(l, s, is_list=True):
    for i in range(s):
        l.append(i)
    if is_list:
        for _ in range(s):
            l.pop(0)
    else:
        for _ in range(s):
            l.popleft()


def main():
# 保证相同的测试项,数据量级相同.
    N = 10000
    idxs = [randint(0, N - 1) for _ in range(N)]
    l = [n for n in range(N)]
    d = deque(l)
    list_random_access = timefunc(random_access, l, idxs, repeat=100)
    deque_random_access = timefunc(random_access, d, idxs, repeat=100)
    print("list random access: ", list_random_access)
    print("deque random access: ", deque_random_access)

    l = []
    d = deque()
    list_append_pop = timefunc(append_pop, l, 100000, repeat=10, cache=True)
    deque_append_pop = timefunc(append_pop, d, 100000, repeat=10, cache=True)
    print("list append pop: ", list_append_pop)
    print("deque append pop: ", deque_append_pop)


    list_append_popleft = timefunc(append_popleft, l, 100000, repeat=10, cache=True, is_list=True)
    deque_append_popleft = timefunc(append_popleft, d, 100000, repeat=10, cache=True, is_list=False)
    print("list append popleft: ", list_append_popleft)
    print("deque append popleft: ", deque_append_popleft)


main()

测试结果:

luvjoey@luvjoey-pc ~/P/benchmark> python deque_vs_list.py 
list random access :  0.029722213745117188
deque random access:  0.09007883071899414
list append pop :  0.1275017261505127
deque append pop:  0.1163034439086914
list append popleft :  10.22320556640625
deque append popleft:  0.11370468139648438

首先明确一点, 过分的纠结性能不是一件好事. 数据结构的选择是基于应用场景的, 我之所以做性能测试主要是想验证我对数据结构的认知是正确的.

  • 索引访问 deque 劣于 list
  • 右端的新增, 删除元素 deque 略优于 list
  • 右端新增, 左端删除 deque 远优于 list
展示评论