Deque 与 list 性能比较

小开

不管怎样:

巨蟒3

deque.pop vs 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 vs 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

巨蟒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。

小开

Could anyone explain me what I did wrong here

是的，创建列表或 deque 的时间决定了时间。相比之下，做爸爸的时间是微不足道的。

相反，你应该把你要测试的东西(弹出速度)从设置时间中分离出来:

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

也就是说，deques 和 list 在性能方面的真正区别是:

对于 附录左()和 Popleft ()，分离器具有 O (1)速度，而对于 Insert (0，value)插入(0，值)和 流行(0)，分离器具有 O (n)性能。
列表追加性能时好时坏，因为它在引擎盖下使用了 Realloc ()。因此，它在简单代码中的计时往往过于乐观(因为 realloc 不必移动数据) ，而在实际代码中的计时则非常慢(因为碎片化迫使 realloc 移动所有数据)。相反，deque append 性能是一致的，因为它从不重新分配，也从不移动数据。

小开

我建议你参考一下 Https://wiki.python.org/moin/timecomplexity

Python 列表和 deque 对于大多数操作(push、 pop 等)都具有类似的复杂性

小开

我找到了解决这个问题的方法，并且认为我应该提供一个带有上下文的例子。
使用 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

注意: deque 有一个内置的 rotate方法，这是 deque 的一个非常常见的用法，但是为了便于可视化比较，我在这里手动进行操作。

现在让我们 %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

非常有趣的是，这两种数据结构都公开了一个惊人相似的接口，但是性能却大相径庭:)

小开

出于好奇，我试着插入 list vs appleleft () of deque 的开头部分。
显然 Deque 是赢家。