I am wondering about the time complexity of the get operation of deque in Python.
I know that it is implemented as a doubly link in Python. Does that mean that its time complexity is O(n)?
1 Answer
deque are implemented a little smarter than just doubly-linked lists. They're a doubly-linked list of blocks of Python objects, where the left and right sides may be incomplete blocks.
The Big-O cost of accessing in the middle is still O(n), but it has a constant divisor (implementation dependent, CPython 3.5 allocates blocks that can store 64 objects). So if your deque has 1000 members, accessing in the middle still involves only around 7-8 "linked list-style" traversals, not 500-some. If the deque is smallish (65 to 128 elements, depending on how the empty slots align with the head and tail blocks), then lookup of any element is equal cost.
3 Comments
zhy
Really like these smart implementations ^_^
ShadowRanger
@zhy: Yeah; downside to this implementation is you can't do zero-copy transfers of nodes from between
deques (linked lists could), and insertion/removal in the middle is O(n) element moves, not just O(n) node traversals. C++ allows stuff like that with std::list, but C++'s iterator design makes such node transfers "natural" w/o adding on non-standard API. Python's iterator protocol doesn't include the features needed to enable that, so you'd have to hack on non-standard stuff to enable linked list features; if you can't use linked list features anyway, deque is strictly better.ShadowRanger
Specifically, the problem is that while C++'s iterator protocol lets you know both what the value is at the current position without advancing the iterator, and for most sequence iterators, allows you to move the iterator forward and backwards, Python's only offers one feature: Tell you the next value and advance the iterator (similar to doing
if (it != std::end(seq)) return *it++; in C++); iterators represent the iteration of values themselves, not true positions in the sequence.
deque, but there's no mention of time complexity.list.index. As the way it is documented, it strongly implies searching.