双端队列deque，性能更好

用惯了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 --

相关文章