deque.popleft() is faster than list.pop(0), because the deque has been optimized to do popleft() approximately in O(1), while list.pop(0) takes O(n) (see deque objects). Comments and code in _collectionsmodule.c for deque and listobject.c for list provide implementation insights to explain the performance differences. Namely that a deque object “is composed of a doubly-linked list”, which … Read more
I found this deque implementation from Wikipedia: Storing contents in multiple smaller arrays, allocating additional arrays at the beginning or end as needed. Indexing is implemented by keeping a dynamic array containing pointers to each of the smaller arrays. I guess it answers my question.
Queue.Queue and collections.deque serve different purposes. Queue.Queue is intended for allowing different threads to communicate using queued messages/data, whereas collections.deque is simply intended as a datastructure. That’s why Queue.Queue has methods like put_nowait(), get_nowait(), and join(), whereas collections.deque doesn’t. Queue.Queue isn’t intended to be used as a collection, which is why it lacks the likes … Read more
Linked structures are possibly the worst structure to iterate with a cache miss on each element. On top of it they consume way more memory. If you need add/remove of the both ends, ArrayDeque is significantly better than a linked list. Random access each element is also O(1) for a cyclic queue. The only better … Read more
Elements in a deque are not contiguous in memory; vector elements are guaranteed to be. So if you need to interact with a plain C library that needs contiguous arrays, or if you care (a lot) about spatial locality, then you might prefer vector. In addition, since there is some extra bookkeeping, other ops are … Read more
https://github.com/python/cpython/blob/v3.8.1/Modules/_collectionsmodule.c A dequeobject is composed of a doubly-linked list of block nodes. So yes, a deque is a (doubly-)linked list as another answer suggests. 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 … Read more
Could anyone explain me what I did wrong here Yes, your timing is dominated by the time to create the list or deque. The time to do the pop is insignificant in comparison. Instead you should isolate the thing you’re trying to test (the pop speed) from the setup time: In [1]: from collections import … Read more
For one thing, it’s more sensible in terms of inheritance. The fact that Stack extends Vector is really strange, in my view. Early in Java, inheritance was overused IMO – Properties being another example. For me, the crucial word in the docs you quoted is consistent. Deque exposes a set of operations which is all … Read more
A deque is somewhat recursively defined: internally it maintains a double-ended queue of chunks of fixed size. Each chunk is a vector, and the queue (“map” in the graphic below) of chunks itself is also a vector. There’s a great analysis of the performance characteristics and how it compares to the vector over at CodeProject. … Read more