12

C++ deque:

Random access - constant O(1)

Python deque:

Indexed access is O(1) at both ends but slows to O(n) in the middle.

If I'm not missing anything, everything else is equally fast for deques in python and in C++, at least complexity-wise. Is there anything that makes python's deque better for some cases? If not, why don't they just switch to what C++ has?

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
Typical User
  • 153
  • 8
  • 1
    Implementation details. In both cases. – Ignacio Vazquez-Abrams Sep 04 '17 at 18:20
  • @IgnacioVazquez-Abrams Isn't that a tautology? – Sneftel Sep 04 '17 at 18:21
  • @Sneftel What do you mean exactly by "tautology"? That everything is an inmplementation detail? – Right leg Sep 04 '17 at 18:24
  • @Sneftel: No, because both of OP's sources are specifications, not implementations. And it is entirely possible that further specifications make it impossible to formulate an improved implementation. – Ignacio Vazquez-Abrams Sep 04 '17 at 18:26
  • 3
    Random access isn't the central concern of deques. Rather it's a side-effect of the method chosen to get fast push/pop on both ends. Python uses a linked list and C++ STLs tend to use a vector-of-chunks. Consequently, Python inserts are very nearly guaranteed constant time: memory allocation for a new list node plus value initialization. Unfortunately access to arbitrary elements of a linked list is O(n). The vector-of-chunks allows quick random access, but can require O(n) time to reorganize the map vector for any given insert (though n inserts require O(n) time). – Gene Sep 04 '17 at 19:49
  • @IgnacioVazquez-Abrams I don't understand why this matters, my question is about the specifications, not any specific implementations. – Typical User Sep 04 '17 at 20:07
  • 3
    Related question https://stackoverflow.com/questions/45134139/why-is-deque-implemented-as-a-linked-list-instead-of-a-circular-array – Jeff Sep 05 '17 at 15:41

2 Answers2

7

Disclaimer: this answer is largely inspired from Jeff's comment and the answer already posted at Why is a deque implemented as a linked list instead of a circular array ?

Your question is different in nature but the title above is an answer in itself: in Python, the module collections.deque has a linear time complexity when accessing items in the middle because it is implemented using a linked list.

From the pydoc:

A list-like sequence optimized for data accesses near its endpoints.

Now if you're wondering why this implementation was chosen, the answer is already available in the post pointed out by Jeff.

Flynsee
  • 596
  • 4
  • 17
-1

Because Deque is a data structed supposed to be used in a specific way, being accessed by the first or last element, But python sometimes do weird things with its data structures and add more functions to them, or use composed data structures

In this case python has the function 

remove(value)
#Remove the first occurrence of value. If not found, raises a ValueError.

this allow you to access the data structure elements on the middle of the deque it isn't a "core" operation of this data structure,

causing the "but slows to O(n) in the middle. "

Because in this case it behaves like an array (checking values one by one)

zero
  • 172
  • 1
  • 6