Python 中的双端队列是如何实现的，它们什么时候比列表更糟糕? [英] How are deques in Python implemented, and when are they worse than lists?

问题描述

我最近开始研究如何在 Python 中实现各种数据结构，以提高我的代码效率.在研究列表和双端队列的工作原理时，我发现当我想移动和取消移动时，我可以得到好处，将时间从列表中的 O(n) 减少到双端队列中的 O(1)(列表被实现为具有固定长度的数组)每次在前面插入东西时都被完全复制，等等......).我似乎找不到双端队列是如何实现的细节，以及它的缺点和缺点的细节.列表.有人可以就这两个问题启发我吗?

I've recently gotten into investigating how various data structures are implemented in Python in order to make my code more efficient. In investigating how lists and deques work, I found that I can get benefits when I want to shift and unshift reducing the time from O(n) in lists to O(1) in deques (lists being implemented as fixed-length arrays that have to be copied completely each time something is inserted at the front, etc...). What I can't seem to find are the specifics of how a deque is implemented, and the specifics of its downsides v.s. lists. Can someone enlighten me on these two questions?

推荐答案

https://github.com/python/cpython/blob/v3.8.1/Modules/_collectionsmodule.c

一个dequeobject由一个block节点的双向链表组成.

A dequeobject is composed of a doubly-linked list of block nodes.

是的，正如另一个答案所暗示的那样，deque 是一个(双)链表.

So yes, a deque is a (doubly-)linked list as another answer suggests.

详细说明:这意味着 Python 列表更适用于随机访问和固定长度的操作，包括切片，而双端队列在使用索引(但不是切片，有趣的是)是可能的，但比列表慢.

Elaborating: What this means is that Python lists are much better for random-access and fixed-length operations, including slicing, while deques are much more useful for pushing and popping things off the ends, with indexing (but not slicing, interestingly) being possible but slower than with lists.

这篇关于Python 中的双端队列是如何实现的，它们什么时候比列表更糟糕?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！