Python中Deque的随机访问时间复杂度为O(n)，而C++中为O(1)，为什么？

Question

C++中的deque:

随机访问 - 常数时间 O(1)

Python的deque:

两端的索引访问为O(1)，但在中间位置会变慢，时间复杂度为O(n)。

如果我没有遗漏什么的话，在时间复杂度方面，Python和C ++的deque执行效率相同。是否有任何使Python的deque更适合某些情况的东西？如果没有，为什么不直接改用C++呢？

- Typical User

---

具体实现细节。在两种情况下。 - Ignacio Vazquez-Abrams

@Sneftel：不行，因为OP的两个来源都是规范，而不是实现。而且完全有可能进一步的规范会使得改进的实现变得不可能。 - Ignacio Vazquez-Abrams

双端队列的中心问题并不是随机访问，而是通过选择快速在两端进行推入/弹出而产生的副作用。Python使用链表，而C++ STLs通常使用一个块的向量。因此，Python的插入几乎可以保证常数时间：为新的列表节点分配内存加上值初始化。不幸的是，对于一个链表的任意元素的访问是O(n)的。块的向量允许快速随机访问，但可能需要O(n)的时间来重新组织地图向量以便进行任何给定的插入（尽管n个插入需要O(n)的时间）。 - Gene

@IgnacioVazquez-Abrams 我不明白这为什么重要，我的问题是关于规格说明，而不是任何具体的实现。 - Typical User

为什么 deque 实现使用链表而不是循环数组？ - Jeff

Answer 1

免责声明：本答案主要受到Jeff的评论和已发布在为什么deque实现为链表而不是循环数组？的答案的启发。

您的问题性质不同，但上面的标题本身就是一个答案：在Python中，collections.deque模块使用链表实现，因此访问中间项的时间复杂度为线性。

从pydoc中可以看出：

“一种类似于列表的序列，优化了接近其端点的数据访问。”

如果您想知道为什么选择这种实现方式，答案已经在Jeff指出的帖子中提供了。

- Flynsee

Answer 2

由于Deque是一种特定使用方式的数据结构，应该通过第一个或最后一个元素进行访问， 但是Python有时会对其数据结构做出奇怪的事情，并向其中添加更多的函数，或使用组合数据结构。

在这种情况下，Python具有以下功能：

remove(value)
#Remove the first occurrence of value. If not found, raises a ValueError.

这使你能够访问deque中间的数据结构元素，但它不是此数据结构的"核心"操作，

这会导致"但在中间变慢到O(n)"。

因为在这种情况下，它的行为就像一个数组（逐个检查值）。

- zero