我应该使用Python双端队列还是列表作为堆栈？ [英] Should I use a Python deque or list as a stack?

问题描述

我想要一个可用作堆栈的Python对象。使用双端队列或列表是否更好，并且无论我是元素数量少还是元素数量大？

I want a Python object that I can use as a stack. Is it better to use a deque or a list and does it make a difference whether I have a small number of elements or a large number of elements?

推荐答案

您的里程可能会因您的应用程序和具体用例而异，但是在一般情况下，列表非常适合堆栈：

Your mileage may vary according to your application and precise use case, but in the general case, a list is well suited for a stack:

append 为O（1）

pop（）为O（1）-只要您不会从任意位置弹出； pop（）仅从头开始。

pop() is O(1) - as long as you do not pop from an arbitrary position; pop() only from the end.

对于这些操作，双端队列也为O（1），但需要从标准库，需要使用'O（n）'进行随机访问。除非有特定的applicatins，否则可以说是首选使用香草列表。

Deques are also O(1) for these operations, but require importing a module from the standard library, require 'O(n)' for random access. An argument could be made to prefer using vanilla lists though, unless for specific applicatins.

来自这篇文章（由list和deque的C代码的主要作者）Raymond Hettinger撰写，看来deque执行起来比列表要好一些：双端队列的pop（）操作似乎具有优势。

from this post by Raymond Hettinger, a principal author of the C code for both list and deque, it appears that deques may perform slightly better than lists: The pop() operation of deques seem to have the advantage.

In [1]: from collections import deque

In [2]: s = 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

在性能
上，双端队列和列表之间的真正差异是：

the real differences between deques and list in terms of performance are:

双端队列的appendleft（）和popleft（）的速度为O（1），而列表具有
insert（0，value）和pop（0）的O（n）性能。
列表追加
性能受到打击和错过，因为它在后台使用了realloc（）。
结果，在简单代码
中它往往具有过分乐观的时序（因为重新分配不必移动数据），而在实际代码中确实减慢了
时序（由于碎片力量）重新分配以移动所有
数据）。相反，双端队列附加性能是一致的，因为它不会重新分配
，也不会移动数据。

Deques have O(1) speed for appendleft() and popleft() while lists have O(n) performance for insert(0, value) and pop(0).
List append performance is hit and miss because it uses realloc() under the hood. As a result, it tends to have over-optimistic timings in simple code (because the realloc doesn't have to move data) and really slow timings in real code (because fragmentation forces realloc to move all the data). In contrast, deque append performance is consistent because it never reallocs and never moves data.

这篇关于我应该使用Python双端队列还是列表作为堆栈？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！