Deque random cces O（n）in python while O（1）in C++，why？

问题描述：

随机存取 - 恒定O（1）

的Python deque：

索引访问是O（1）在两端但减慢到为O（n ）在中间。

如果我没有遗漏任何东西，其他所有东西在python和C++中都是同样快的，至少在复杂性方面是这样。有什么能让python的deque在某些情况下变得更好？如果没有，为什么他们不转向C++？

实现细节。在这两种情况下。 –

@ IgnacioVazquez - 艾布拉姆斯是不是一种同义反复？ – Sneftel

@Sneftel你是什么意思“所有的东西都是一个实现的细节？” –

答

免责声明：这个答案在很大程度上是从杰夫的评论启发和答案已张贴在Why is a deque implemented as a linked list instead of a circular array ?

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

从是pydoc：

用于数据优化列表样序列访问靠近其端点。

现在，如果你想知道为什么选择这个实施，答案已经可以在帖子中指出杰夫。

答

因为Deque是一个数据结构，应该以特定的方式使用，被第一个或最后一个元素访问，但是python有时会用它的数据结构做奇怪的事情并为它们增加更多的功能，或者使用组合数据结构

在这种情况下，Python有

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

这允许您访问的双端队列中间的数据结构元素不是这个数据结构的“核心”的操作，功能

导致“但在中间减慢O（n）。 “

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