Menu
I want a Python object that I can use as a stack. Is it better to use a deque or a list and does it make a difference whether I have a small number of elements or a large number of elements?
715
For lists, it's always O(1). So, for accessing elements, lists are always a better choice, it's not at all what deques were designed for. Second, because deques are implemented as doubly-ended arrays, they have the advantage when appending or popping from both the right and the left side of a deque (measured as O(1)).
Deque is preferred over a list in the cases where we need quicker append and pop operations from both the ends of the container, as deque provides an O(1) time complexity for append and pop operations as compared to list which provides O(n) time complexity.
Deques are faster adding/removing elements to the end or beginning. Lists are faster adding/removing elements to any other 'middle' position. You can also use insert(index, value) on lists, while on deques you can only append left or right.
Deque is a doubly linked list while List is just an array. Randomly accessing an object at index i is O(n) for Deque but O(1) for List . Fast insertions and deletions at the beginning is the biggest advantage of Deque . Fast random reads is the advantage of List .
Your mileage may vary according to your application and precise use case, but in the general case, a list is well suited for a stack:
append is O(1)
pop() is O(1) - as long as you do not pop from an arbitrary position; pop() only from the end.
Deques are also O(1) for these operations, but require importing a module from the standard library, require 'O(n)' for random access. An argument could be made to prefer using vanilla lists though, unless for specific applicatins.
from this post by Raymond Hettinger, a principal author of the C code for both list and deque, it appears that deques may perform slightly better than lists: The pop() operation of deques seem to have the advantage.
In [1]: from collections import deque
In [2]: s = list(range(1000)) # range(1000) if python 2
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
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.
85
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
