python - list.pop() 和 deque.pop() ——有性能差异吗？

Question

这个问题是这个问题的后续问题: deque.popleft() and list.pop(0). Is there performance difference?

在 Python 中，我可以使用 .pop() 弹出添加到列表中的最后一项。我还可以使用 dequeue 和 .pop() 弹出最后一项。

这两者之间有性能差异吗？是否有理由或用例应该使用其中一种而不是另一种？

编辑:拼写错误....将.popright更改为.pop - deque的“pop right”仍然只是.pop -谢谢ShadowRanger

Answer 1

首先，它的名字是 pop对于两者list和deque ，没有popright方法deque s。

两者之间通常没有有意义的性能差异；每隔一段时间，一个pop在deque上会导致 block 释放(它具有固定的开销，它只会使特定的 pop 的成本更高一些)，并且在 list 上它可能会导致 realloc 缩小底层存储(最终可能是 O(n) ，但只有 pop 的一小部分会导致它)；渐进地它们都是 O(1)运营。如果您list确实很大，然后缩小很多，当它缩小底层存储时，您可能会偶尔遇到性能问题，但除此之外，您不太可能注意到差异。

回答您的问题，deque作为堆栈使用时，s 的效率比 list 稍微高一些。 s;如果您要导入collections无论如何，并且需要一个基于堆栈的结构，使用 deque会给你带来一点好处(至少在 CPython 上，不能与其他实现交谈)。但这里并不值得进行微观优化；进口成本collections首先，以及基于此堆栈执行的任何有用代码的成本，可能会让您在 list 之间看到的任何微小差异相形见绌。和deque对于 pop从右边开始。一个简单的ipython3微基准:

In [24]: %%timeit from collections import deque; s = deque([0] * 10000); onethousandnones = (None,) * 1000; pop = s.pop
    ...: ; push = s.append
    ...: for _ in onethousandnones:
    ...:     pop()
    ...: for _ in onethousandnones:
    ...:     push(0)
    ...:
    ...:
104 µs ± 7.99 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [25]: %%timeit s = [0] * 10000; onethousandnones = (None,) * 1000; pop = s.pop; push = s.append
    ...: for _ in onethousandnones:
    ...:     pop()
    ...: for _ in onethousandnones:
    ...:     push(0)
    ...:
    ...:
131 µs ± 8.93 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

因此，对于 1000 次弹出操作，然后是 1000 次压入堆栈，deque基于堆栈的时间减少了 30 µs(每次操作减少了大约 15 ns)。现在不可否认的是，如果我删除调用括号来计时基本开销，则基本开销约为 50 µs，因此开销具体归因于 list是 deque 的“最低成本”的很大一部分。 ，但在程序的上下文中它仍然相当小，该程序可能正在做一些有用的事情，而不仅仅是插入和弹出到堆栈。而且无论大小如何，它都非常稳定；对于大小为 10 倍的堆栈， deque 的成本保持不变和list 。如果堆栈的增长和收缩幅度如此之大，则 list的摊销增长正在开始，它可能会因更大的重新分配而受到更多影响，但这通常不需要担心。