Is deque from the collections module really 100 times faster at prepending than list in Python?

Question

Is there something wrong with my code? I'm getting a 100 times speed up when timing a simple function using deque from the collections module as opposed to a regular list.

>>> from collections import deque as dl
>>> import cProfile
>>> 
>>> def l(i):
...     l = ['0','1','2','3','4','5','6']
...     while i:
...         l.insert(0,'9')
...         i -= 1
... 
>>> def d(i):
...     l = dl('0123456')
...     while i:
...         l.appendleft('9')
...         i -= 1
... 
>>> cProfile.run('l(100000)')
         100004 function calls in 4.480 seconds

[...]

>>> cProfile.run('d(100000)')
         100004 function calls in 0.031 seconds

If my code is fine, what's the point of using lists at all? Why not completely switch to deque?

Per the docs, lists *"are optimized for fast fixed-length operations"*; it's unfair to compare them to `deque`s for this one thing and conclude that they're pointless. — jonrsharpe, Oct 21 '15 at 13:38
Well there are three possible answers: 1. There are other operations you haven't thought of yet where lists are faster; 2. There are other benefits to using lists beyond speed of operations (e.g. have you compared memory footprints?); or 3. The developers just haven't realised they could have used deques all along. Honestly, that last one seems least likely! — jonrsharpe, Oct 21 '15 at 13:42
In short it's a fast item access. The situation when you have to insert something into a list multiple times are rare. When you do, it's time to switch to queue or deque. And even that not always so. Lists work just fine with appending and geting data, which is their most common needed use. — Dalen, Oct 21 '15 at 14:32
If Deque was a replacement for a list, don't you think that we would switch to using it for that by now??? — Dalen, Oct 21 '15 at 14:35

score 3 · Accepted Answer · edited May 23 '17 at 11:58

From Python docs:

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.

Deques support iteration, pickling, len(d), reversed(d), copy.copy(d), copy.deepcopy(d), membership testing with the in operator, and subscript references such as d[-1]. Indexed access is O(1) at both ends but slows to O(n) in the middle. For fast random access, use lists instead.

...

Now the difference is that the list is implemented with fixed size memory blocks (arrays), while deque is implemented as a double-linked list.

That means that lists have to realoacate memory and make copies of data depending on where you insert a new item, except when appending.

But random access (indexing) is very fast for them.

Deque doesn't have such problems because when inserting, only pointers should be corrected to insert a new node on the given position.

But finding data (the position for insert or random access - indexing) requires iteration over deque.

Deques are also thread safe, but unless you have to deal with endpoints i.e. use property of a queue lists are still your best friends.

Deques use a little bit more memory per item, because they store at least two more integers (pointers) with each item.

There is also matter of slicing a deque. It can be done manually by switching end-points of a deque using the rotate method. Getting the N items and then rotating back.

See from Python docs how del is implemented for only one item:

The rotate() method provides a way to implement deque slicing and deletion. For example, a pure Python implementation of del d[n] relies on the rotate() method to position elements to be popped:

def delete_nth(d, n):
    d.rotate(-n)
    d.popleft()
    d.rotate(n)

I think that is enough for you. BTW, your Q is nearly a duplicate of:

How are deques in Python implemented, and when are they worse than lists?

Woops, I forgot to really answer you: Your code is fine! :D :D So, yes, a contribution it is. — Dalen, Oct 21 '15 at 20:02

Is deque from the collections module really 100 times faster at prepending than list in Python?

1 Answers1