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

Question

CPython的deque被实现为64项的双向链表大小的"块"(阵列).除了链表两端的那些块外,这些块都是满的.在IIUC中,当pop/ popleft删除块中的最后一项时,块被释放; 当append/ appendleft尝试添加新项目并且相关块已满时,将分配它们.

我理解使用链接列表而不是链接项列表所列出的优点:

但是为什么不是首先使用单个动态大小的圆形数组而不是双链表呢？

AFAICT,圆形阵列将保留所有上述优点,并维持(atortized)成本pop*/ append*at O(1)(通过分配,就像在中list).此外,它还可以提高从当前O(n)到索引的索引查找成本O(1).循环数组也可以更简单地实现,因为它可以重用大部分list实现.

我可以在C++这样的语言中看到支持链表的论证,其中可以O(1)使用指针或迭代器从中间删除项目; 但是,python deque没有API来执行此操作.

Answer 1

改编自我在python-dev邮件列表上的回复:

双端队列的主要目的是使两端的弹出和推动变得有效.这就是当前的实现方式:每次推送或弹出的最坏情况常量时间,无论deque中有多少项.在小型和大型中击败"摊销的O(1)".这就是为什么这样做的原因.

其他一些deque方法因此比列表慢,但是谁在乎呢？例如,我曾经用过双端队列的唯一索引是0和-1(窥视一端或另一端的双端队列),并且实现也使得访问这些特定索引的时间也是恒定的.

事实上,来自Raymond Hettinger的消息由Jim Fasarakis Hilliard在他的评论中引用:

证实了这一点

__getitem__投入的唯一原因是支持快速访问头部和尾部而不实际弹出值

Answer 2

除了接受@TimPeters 的回答之外，我还想添加一些不适合评论格式的额外观察结果。

让我们只关注一个常见的用例，其中 deque用作简单的 FIFO 队列。

一旦队列达到其峰值大小，循环数组就不再需要从堆中分配内存。我认为这是一个优势，但事实证明，CPython 实现通过保留可重用内存块的列表实现了相同的效果。一个领带。

随着队列大小的增长，循环数组和 CPython 都需要堆中的内存。CPython 需要一个简单的malloc，而数组需要（可能要贵得多）realloc（除非原始内存块的右边缘恰好有额外的空间可用，否则它需要释放旧内存并复制数据）。CPython 的优势。

如果队列的峰值比其稳定大小大得多，CPython 和数组实现都会浪费未使用的内存（前者将其保存在可重用的块列表中，后者将未使用的空白空间留在数组中） . 一个领带。

正如@TimPeters 指出的那样，每个 FIFO 队列 put / get 的成本始终O(1)用于 CPython，但仅O(1)针对数组进行摊销。CPython 的优势。

请注意，在最后一种情况下（双端队列的峰值比其稳定大小大得多），双端队列实现“浪费”的空间受一个小常量的限制：内部块空闲列表最多包含`MAXFREEBLOCKS`双端队列块，即 16。如果列表中已经有那么多块，则随后释放的块将通过 `PyMem_Free()` 返回到“系统”。块空闲列表的真正目的是在推送对象的常见 FIFO 情况下提高效率并以大致相同的速度弹出。 (2认同)