python: deque与list性能比较

Question

在Python的文档中，我看到deque是一种特别的集合，它在从左边或右边添加和删除元素时非常高效。比如，文档中提到：

deque是栈和队列的一个扩展（这个名字读作“deck”，是“双端队列”的缩写）。deque支持线程安全、内存高效的从两边添加和删除元素，性能大致在O(1)的水平，无论是从哪一边操作。

虽然列表对象也支持类似的操作，但它们是为了快速处理固定长度的操作而优化的，因此在进行pop(0)和insert(0, v)这些操作时，会产生O(n)的内存移动成本，因为这些操作会改变底层数据的大小和位置。

我决定使用ipython进行一些比较。有人能告诉我我在这里做错了什么吗：

In [31]: %timeit range(1, 10000).pop(0)
 10000 loops, best of 3: 114 us per loop

In [32]: %timeit deque(xrange(1, 10000)).pop() 
10000 loops, best of 3: 181 us per loop

In [33]: %timeit deque(range(1, 10000)).pop()
1000 loops, best of 3: 243 us per loop

Answer 1

出于好奇，我试着在列表的开头插入元素，和用deque的appendleft()方法进行比较。
结果很明显，deque表现更好。

Answer 2

我找到了这个问题，想分享一个例子并加点背景信息。
使用双端队列（Deque）的一个经典场景是对集合中的元素进行旋转或移动，因为（正如其他人提到的），在两端进行添加或删除操作时，它的效率非常高（O(1)），因为这些操作只是移动引用，而不像列表那样需要在内存中实际移动对象。

下面是两个看起来非常相似的左旋转函数的实现：

def rotate_with_list(items, n):
    l = list(items)
    for _ in range(n):
        l.append(l.pop(0))
    return l

from collections import deque
def rotate_with_deque(items, n):
    d = deque(items)
    for _ in range(n):
        d.append(d.popleft())
    return d

注意：这是双端队列非常常见的用法，所以它有一个内置的 rotate 方法，但为了方便比较，我在这里手动实现了一下。

现在我们来用 %timeit 测试一下。

In [1]: def rotate_with_list(items, n):
   ...:     l = list(items)
   ...:     for _ in range(n):
   ...:         l.append(l.pop(0))
   ...:     return l
   ...: 
   ...: from collections import deque
   ...: def rotate_with_deque(items, n):
   ...:     d = deque(items)
   ...:     for _ in range(n):
   ...:         d.append(d.popleft())
   ...:     return d
   ...: 

In [2]: items = range(100000)

In [3]: %timeit rotate_with_list(items, 800)
100 loops, best of 3: 17.8 ms per loop

In [4]: %timeit rotate_with_deque(items, 800)
The slowest run took 5.89 times longer than the fastest. This could mean that an intermediate result is being cached.
1000 loops, best of 3: 527 µs per loop

In [5]: %timeit rotate_with_list(items, 8000)
10 loops, best of 3: 174 ms per loop

In [6]: %timeit rotate_with_deque(items, 8000)
The slowest run took 8.99 times longer than the fastest. This could mean that an intermediate result is being cached.
1000 loops, best of 3: 1.1 ms per loop

In [7]: more_items = range(10000000)

In [8]: %timeit rotate_with_list(more_items, 800)
1 loop, best of 3: 4.59 s per loop

In [9]: %timeit rotate_with_deque(more_items, 800)
10 loops, best of 3: 109 ms per loop

很有趣的是，这两种数据结构的接口看起来非常相似，但它们的性能却截然不同 :)

Answer 3

我建议你去看看这个链接：https://wiki.python.org/moin/TimeComplexity

Python中的列表和双端队列（deque）在大多数操作（比如添加、删除等）上的复杂度是差不多的。

Answer 4

这段内容的意思是：

Python 3

deque.pop 和 list.pop 的区别

> python3 -mtimeit -s 'import collections' -s 'items = range(10000000); base = [*items]' -s 'c = collections.deque(base)' 'c.pop()'
5000000 loops, best of 5: 46.5 nsec per loop 
    
> python3 -mtimeit -s 'import collections' -s 'items = range(10000000); base = [*items]' 'base.pop()'
5000000 loops, best of 5: 55.1 nsec per loop

deque.appendleft 和 list.insert 的区别

> python3 -mtimeit -s 'import collections' -s 'c = collections.deque()' 'c.appendleft(1)'
5000000 loops, best of 5: 52.1 nsec per loop

> python3 -mtimeit -s 'c = []' 'c.insert(0, 1)'
50000 loops, best of 5: 12.1 usec per loop

Python 2

> python -mtimeit -s 'import collections' -s 'c = collections.deque(xrange(1, 100000000))' 'c.pop()'
10000000 loops, best of 3: 0.11 usec per loop
    
> python -mtimeit -s 'c = range(1, 100000000)' 'c.pop()'
10000000 loops, best of 3: 0.174 usec per loop
   
> python -mtimeit -s 'import collections' -s 'c = collections.deque()' 'c.appendleft(1)'
10000000 loops, best of 3: 0.116 usec per loop
    
> python -mtimeit -s 'c = []' 'c.insert(0, 1)'
100000 loops, best of 3: 36.4 usec per loop

正如你所看到的，appendleft 和 insert 的表现特别出色。

Answer 5

有人能告诉我我哪里做错了吗？

是的，你的时间主要花在创建列表或双端队列上。相比之下，执行pop操作所花的时间几乎可以忽略不计。

所以你应该把你想测试的内容（即pop的速度）和准备时间分开：

In [1]: from collections import deque

In [2]: s = list(range(1000))

In [3]: d = deque(s)

In [4]: s_append, s_pop = s.append, s.pop

In [5]: d_append, d_pop = d.append, d.pop

In [6]: %timeit s_pop(); s_append(None)
10000000 loops, best of 3: 115 ns per loop

In [7]: %timeit d_pop(); d_append(None)
10000000 loops, best of 3: 70.5 ns per loop

说到这里，双端队列和列表在性能上的真正区别是：

• 双端队列的appendleft()和popleft()操作的速度是O(1)，而列表的insert(0, value)和pop(0)操作的速度是O(n)。

• 列表的添加性能有时好有时差，因为它在内部使用realloc()。结果是，在简单代码中，它的时间表现往往过于乐观（因为realloc不需要移动数据），而在实际代码中，它的时间表现则很慢（因为内存碎片会迫使realloc移动所有数据）。相比之下，双端队列的添加性能是稳定的，因为它从不重新分配内存，也不移动数据。