2021年3月31日 / 87次阅读 / 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
《双端队列deque,性能更好》有1条留言
前一篇:用numpy构建Hadamard Matrix
后一篇:数字中的单下划线
Ctrl+D 收藏本页
©Copyright 麦新杰 Since 2019 Python笔记
The collections module provides a deque() object that is like a list with faster appends and pops from the left side but slower lookups in the middle. [ ]