Deque随机访问python中的O(n)而C++中的O(1),为什么？

Question

C++ deque:

随机访问 - 常数O(1)

Python deque:

索引访问在两端都是O(1),但在中间减慢到O(n).

如果我没有遗漏任何东西,那么其他一切对于python和C++中的deques都同样快,至少在复杂性方面.在某些情况下,有什么能让python的deque变得更好吗？如果没有,为什么他们不切换到C++有什么？

Answer 1

免责声明:这个答案很大程度上取决于杰夫的评论以及已经发布的答案为什么将双端队列实现为链表而不是圆形阵列？

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

来自pydoc:

类似于列表的序列,针对其端点附近的数据访问进行了优化.

现在,如果你想知道为什么选择这个实现,那么杰克指出的帖子已经提供了答案.