In python docs I can see that deque is a special collection highly optimized for poping/adding items from left or right sides. E.g. documentation says:
Deques are a generalization of stacks and queues (the name is
pronounced “deck” and is short for “double-ended queue”). Deques
support thread-safe, memory efficient appends and pops from either
side of the deque with approximately the same O(1) performance in
either direction.
Though list objects support similar operations, they are optimized for
fast fixed-length operations and incur O(n) memory movement costs for
pop(0) and insert(0, v) operations which change both the size and
position of the underlying data representation.
I decided to make some comparisons using ipython. Could anyone explain me what I did wrong here:
In [31]: %timeit range(1, 10000).pop(0)
10000 loops, best of 3: 114 us per loop
In [32]: %timeit deque(xrange(1, 10000)).pop()
10000 loops, best of 3: 181 us per loop
In [33]: %timeit deque(range(1, 10000)).pop()
1000 loops, best of 3: 243 us per loop
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 deque
In [2]: s = range(1000)
In [3]: d = deque(s)
In [4]: s_append, s_pop = s.append, s.pop
In [5]: d_append, d_pop = d.append, d.pop
In [6]: %timeit s_pop(); s_append(None)
10000000 loops, best of 3: 115 ns per loop
In [7]: %timeit d_pop(); d_append(None)
10000000 loops, best of 3: 70.5 ns per loop
That said, the real differences between deques and list in terms of performance are:
Deques have O(1) speed for appendleft() and popleft() while lists have O(n) performance for insert(0, value) and pop(0).
List append performance is hit and miss because it uses realloc() under the hood. As a result, it tends to have over-optimistic timings in simple code (because the realloc doesn't have to move data) and really slow timings in real code (because fragmentation forces realloc to move all the data). In contrast, deque append performance is consistent because it never reallocs and never moves data.
For what it is worth:
> python -mtimeit -s 'import collections' -s 'c = collections.deque(xrange(1, 100000000))' 'c.pop()'
10000000 loops, best of 3: 0.11 usec per loop
> python -mtimeit -s 'c = range(1, 100000000)' 'c.pop()'
10000000 loops, best of 3: 0.174 usec per loop
> python -mtimeit -s 'import collections' -s 'c = collections.deque()' 'c.appendleft(1)'
10000000 loops, best of 3: 0.116 usec per loop
> python -mtimeit -s 'c = []' 'c.insert(0, 1)'
100000 loops, best of 3: 36.4 usec per loop
As you can see, where it really shines is in appendleft vs insert.
I would recommend you to refer
https://wiki.python.org/moin/TimeComplexity
Python lists and deque have simlilar complexities for most operations(push,pop etc.)
I found my way to this question and thought I'd offer up an example with a little context.
A classic use-case for using a Deque might be rotating/shifting elements in a collection because (as others have mentioned), you get very good (O(1)) complexity for push/pop operations on both ends because these operations are just moving references around as opposed to a list which has to physically move objects around in memory.
So here are 2 very similar-looking implementations of a rotate-left function:
def rotate_with_list(items, n):
l = list(items)
for _ in range(n):
l.append(l.pop(0))
return l
from collections import deque
def rotate_with_deque(items, n):
d = deque(items)
for _ in range(n):
d.append(d.popleft())
return d
Note: This is such a common use of a deque that the deque has a built-in rotate method, but I'm doing it manually here for the sake of visual comparison.
Now let's %timeit.
In [1]: def rotate_with_list(items, n):
...: l = list(items)
...: for _ in range(n):
...: l.append(l.pop(0))
...: return l
...:
...: from collections import deque
...: def rotate_with_deque(items, n):
...: d = deque(items)
...: for _ in range(n):
...: d.append(d.popleft())
...: return d
...:
In [2]: items = range(100000)
In [3]: %timeit rotate_with_list(items, 800)
100 loops, best of 3: 17.8 ms per loop
In [4]: %timeit rotate_with_deque(items, 800)
The slowest run took 5.89 times longer than the fastest. This could mean that an intermediate result is being cached.
1000 loops, best of 3: 527 µs per loop
In [5]: %timeit rotate_with_list(items, 8000)
10 loops, best of 3: 174 ms per loop
In [6]: %timeit rotate_with_deque(items, 8000)
The slowest run took 8.99 times longer than the fastest. This could mean that an intermediate result is being cached.
1000 loops, best of 3: 1.1 ms per loop
In [7]: more_items = range(10000000)
In [8]: %timeit rotate_with_list(more_items, 800)
1 loop, best of 3: 4.59 s per loop
In [9]: %timeit rotate_with_deque(more_items, 800)
10 loops, best of 3: 109 ms per loop
Pretty interesting how both data structures expose an eerily similar interface but have drastically different performance :)
