双端队列deque,性能更好

2021年3月31日 / 9次阅读 / Last Modified 2021年3月31日

用惯了list对象的我,突然发现在collections模块中,还有一个与list功能很相似的deque。不过,deque的性能更好!

deque,double ended queue,读[deck],https://docs.python.org/3/library/collections.html#collections.deque

deque经过特殊优化,专门针对有需要对列表两头都进行操作的场景,而且thread-safe。list更适合fix-length的场景。具体说,就是insert(0,vaule)和pop(0)这样的操作,对list来说有些昂贵,涉及到memory move,而deque可以在接近O(1)的情况下完成。

大部分list有的成员函数deque都有,但deque特别的多了appendleft,popleft,extendleft这样的成员。

下面我们来看一下性能测试:

>>> from timeit import timeit
>>> from collections import deque
>>>
>>> timeit(setup='a=[]', stmt='for i in range(10000): a.insert(0,i)', number=10, globals=globals())
1.7959427870810032
>>> timeit(setup='a=deque()', stmt='for i in range(10000): a.insert(0,i)', number=10, globals=globals())
0.019654391333460808

TMD,快太多了.....

我觉得deque与list最大的不同,在于slice操作。对list可以非常简单轻松的做slice操作,同样的slice方式,deque就不支持,要用rotate函数来进行变通:

>>> a = deque((1,2,3,4,5,6,7,8,9))
>>> a
deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> a[0]
1
>>> a[5]
6
>>>
>>> a[5:]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: sequence index must be integer, not 'slice'
>>>
>>> a.rotate(4)
>>> a
deque([6, 7, 8, 9, 1, 2, 3, 4, 5])
>>> a.pop()
5
>>> a.pop()
4
>>> a.pop()
3
>>> a.pop()
2
>>> a.pop()
1
>>> a
deque([6, 7, 8, 9])

通过rotate和pop的组合,实现了a[5:]的效果。当然,还可以用下面的方式,先转成list,slicing后,在专为deque:

>>> a = deque((1,2,3,4,5,6,7,8,9))
>>> a = deque(list(a)[5:])
>>> a
deque([6, 7, 8, 9])

rotate这个成员函数是list没有的,比较有趣,可以输入正数和负数,值得关注。

从现在开始,python中的队列,有list,queue,deque,各具特色!

-- EOF --

本文链接:https://www.pynote.net/archives/3581

相关文章

    留言区

    邮箱地址不会被公开。 必填项已用*标注


    前一篇:
    后一篇:

    More


    ©Copyright 麦新杰 Since 2019 Python笔记

    go to top