为什么在 collections.deque 中间添加或删除比在那里查找慢? [英] Why is adding to or removing from the middle of a collections.deque slower than lookup there?

问题描述

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

This wiki.python.org page on algorithmic complexity of some data structures says the following for a collections.deque object:

双端队列(双端队列)在内部表示为双向链表.(好吧，数组的列表而不是对象的列表，以提高效率.)两端都可以访问，但即使查看中间也很慢，添加或从中间删除仍然更慢.

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 中没有看到任何这样做的方法.

1) Is adding to the middle of a deque even possible? I don't see any method to do so in the API.

2) 为什么在 deque 中间删除(或添加)会比查找慢?这是一个双向链表，因此一旦找到要添加的对象，添加/删除应该是一个恒定时间操作.

2) Why would removing (or adding) be slower than lookup in the middle of a deque? It's a doubly-linked list, so add/remove should be a constant time operation once you've found the object you want to add.

推荐答案

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

1. It's possible to delete items using the remove() method or the del keyword. It's not possible to insert items. (The only possible way to insert that wouldn't show up in the API documentation would be slice assignment, and that's invalid on a deque.)
2. Because, as the description says, it's actually a doubly-linked list of arrays. So inserting or removing things could require elements to be moved from one array to another. (I haven't looked at the implementation, but I know deque uses a stride technique when looking for elements and I assume the size of the arrays used is the same as the stride length, which is 62.) You'd have to shift a lot of memory around in a regular list when deleting items, too, but at least it's all in one chunk and it can be moved efficiently.

这篇关于为什么在 collections.deque 中间添加或删除比在那里查找慢?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！