为什么在 collections.deque 的中间添加或删除比在那里查找慢？

Question

这个关于某些数据结构的算法复杂性的 wiki.python.org 页面对 collections.deque 对象说了以下内容：

A deque (double-ended queue) is represented internally as a doubly linked list. (Well, a list of arrays rather than objects, for greater efficiency.) Both ends are accessible, but even looking at the middle is slow, and adding to or removing from the middle is slower still.

两个问题：

1) 是否可以添加到 deque 的中间？我在 API.

中没有看到任何这样做的方法

2) 为什么在 deque 中间删除（或添加）比查找慢？这是一个双向链表，所以一旦找到要添加的对象，add/remove 应该是一个常量时间操作。

Answer 1

可以使用 remove() 方法或 del 关键字删除项目。无法插入项目。（唯一可能的插入方式不会出现在 API 文档中是切片分配，这在 deque 上无效。）
因为正如描述所说，它实际上是一个双向链表的数组。因此，插入或删除内容可能需要将元素从一个数组移动到另一个数组。（我没有看过实现，但我知道 deque 在查找元素时使用步幅技术，我假设所用数组的大小与步幅长度相同，即 62。）你'删除项目时，我也必须定期 list 移动大量内存，但至少它都在一个块中，并且可以有效地移动。

Answer 2

1) 看起来 deque.insert() 是在 Python 3.5

中添加的

2) 来自来源：https://github.com/python/cpython/blob/d16a1520c2b22c3cbde7547937ba283db3e88ff5/Modules/_collectionsmodule.c#L952-L958

insert(), remove(), and delitem() are implemented in terms of rotate() for simplicity and reasonable performance near the end points. If for some reason these methods become popular, it is not hard to re-implement this using direct data movement (similar to the code used in list slice assignments) and achieve a performance boost (by moving each pointer only once instead of twice).

它变慢的原因是它的实现方式。

Answer 3

可以用python3.5插入。 index(), insert(), and copy()是python3.5、new in python 3.5才有的三个新方法，早期版本无法插入双端队列：

The deque class now defines index(), insert(), and copy(), as well as supports + and * operators. This allows deques to be recognized as a MutableSequence and improves their substitutability for lists. (Contributed by Raymond Hettinger issue 23704.)

您可以使用 del 或 deque.remove:

从双端队列的中间删除

 deq = deque([1,2,3,4,5,6])
 del deq[4] 
 deq.remove(3)

为什么在 collections.deque 的中间添加或删除比在那里查找慢？

Why is adding to or removing from the middle of a collections.deque slower than lookup there?

python

time-complexity

deque