108

I've recently gotten into investigating how various data structures are implemented in Python in order to make my code more efficient. In investigating how lists and deques work, I found that I can get benefits when I want to shift and unshift reducing the time from O(n) in lists to O(1) in deques (lists being implemented as fixed-length arrays that have to be copied completely each time something is inserted at the front, etc...). What I can't seem to find are the specifics of how a deque is implemented, and the specifics of its downsides v.s. lists. Can someone enlighten me on these two questions?

wim
  • 338,267
  • 99
  • 616
  • 750
Eli
  • 36,793
  • 40
  • 144
  • 207

4 Answers4

104

https://github.com/python/cpython/blob/v3.8.1/Modules/_collectionsmodule.c

A dequeobject is composed of a doubly-linked list of block nodes.

So yes, a deque is a (doubly-)linked list as another answer suggests.

Elaborating: What this means is that Python lists are much better for random-access and fixed-length operations, including slicing, while deques are much more useful for pushing and popping things off the ends, with indexing (but not slicing, interestingly) being possible but slower than with lists.

Alagappan Ramu
  • 2,270
  • 7
  • 27
  • 37
JAB
  • 20,783
  • 6
  • 71
  • 80
  • 5
    Note that if you just need to append and pop at one end (stack), lists should perform better as `.append()` and `.pop()` are amortized O(1) (reallocation and copying happens, but very rarely and only until you reach the max. size the stack will ever have). –  Jun 06 '11 at 20:09
  • @delnan: But if you want a queue, then something like `deque` is definitely the right way to go. – JAB Jun 06 '11 at 20:30
  • @delnan: How do you figure? .append() and .pop() are amortized O(1) on lists, but aren't they actual O(1) on deques and copies are *never* necessary. – Eli Jun 07 '11 at 03:02
  • 1
    @Eli: Lists don't deal with thread-safety (well, it's not wired into their internals) and have been tuned by many smart people for a long time. –  Jun 07 '11 at 14:05
  • 3
    @delnan: Actually, `deque`s in CPython don't really handle thread safety either; they just benefit from the GIL making their operations atomic (and in fact, `append` and `pop` from the end of a `list` has the same protections). In practice, if you're just using a stack, both `list` and `deque` have effectively identical performance in CPython; the block allocations are more frequent with `deque` (but not plain linked list frequent; you'd only end up allocating/freeing every time you crossed a 64 member boundary in CPython implementation), but the lack of huge intermittent copies compensates. – ShadowRanger Dec 02 '15 at 02:13
  • 2
    For a pure Python implementation in check out [PyPy](https://github.com/reingart/pypy/blob/master/lib_pypy/_collections.py)'s code. Interestingly it is a doubly-linked list of small array blocks. – Matt Eding May 08 '19 at 04:12
  • @MattEding: Well, small `list` blocks. But yeah, it's basically (ab?)using the built-in `list` type (like C++ `std::vector`) to represent both 30 elements and the forward and backwards pointers to the neighboring blocks. The `list`s are exactly len `32` (30 elements; the last two indices are the interblock pointers); [CPython instead uses a `struct` that begins with the backwards pointer, then a len 64 array of data, then the forwards pointer](https://github.com/python/cpython/blob/3.10/Modules/_collectionsmodule.c#L31), but fundamentally it's the same design (PyPy just uses smaller blocks). – ShadowRanger Dec 03 '21 at 18:41
59

Check out collections.deque. From the docs:

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.

Just as it says, using pop(0) or insert(0, v) incur large penalties with list objects. You can't use slice/index operations on a deque, but you can use popleft/appendleft, which are operations deque is optimized for. Here is a simple benchmark to demonstrate this:

import time
from collections import deque

num = 100000

def append(c):
    for i in range(num):
        c.append(i)

def appendleft(c):
    if isinstance(c, deque):
        for i in range(num):
            c.appendleft(i)
    else:
        for i in range(num):
            c.insert(0, i)
def pop(c):
    for i in range(num):
        c.pop()

def popleft(c):
    if isinstance(c, deque):
        for i in range(num):
            c.popleft()
    else:
        for i in range(num):
            c.pop(0)

for container in [deque, list]:
    for operation in [append, appendleft, pop, popleft]:
        c = container(range(num))
        start = time.time()
        operation(c)
        elapsed = time.time() - start
        print "Completed %s/%s in %.2f seconds: %.1f ops/sec" % (container.__name__, operation.__name__, elapsed, num / elapsed)

Results on my machine:

Completed deque/append in 0.02 seconds: 5582877.2 ops/sec
Completed deque/appendleft in 0.02 seconds: 6406549.7 ops/sec
Completed deque/pop in 0.01 seconds: 7146417.7 ops/sec
Completed deque/popleft in 0.01 seconds: 7271174.0 ops/sec
Completed list/append in 0.01 seconds: 6761407.6 ops/sec
Completed list/appendleft in 16.55 seconds: 6042.7 ops/sec
Completed list/pop in 0.02 seconds: 4394057.9 ops/sec
Completed list/popleft in 3.23 seconds: 30983.3 ops/sec
Zach Kelling
  • 52,505
  • 13
  • 109
  • 108
  • Thanks for this, but I was hoping for something a bit more concrete. Exactly how much better are fixed-length operations in lists v.s. deques? And how exactly are deques implemented in Python? What's the underlying storage, structure, etc...? – Eli Jun 06 '11 at 19:40
  • @Eli More concrete? How about some benchmarks? Hopefully illustrates the use case for `deque`. It's fairly specialized, and not a drop-in replacement for lists by any means. – Zach Kelling Jun 06 '11 at 20:31
  • 4
    Huh, just noticed that you can't do slicing with deques even though you can do indexing. Interesting. – JAB Jun 06 '11 at 20:33
  • You can't use slice notation or the `index` method. – Zach Kelling Jun 06 '11 at 20:43
  • 1
    +1 for the timings -- interesting that `list` appends are slightly faster than `deque` appends. – senderle Jun 06 '11 at 20:48
  • 1
    @zeekay: That's quite odd, considering that searching for the index of a specific item would normally require iterating over the items of the collection anyway, and that you can index into a `deque` just as you would a `list`. – JAB Jun 07 '11 at 14:29
  • 1
    @senderle: Of course, the `list` `pop`s were slower than `deque`'s (likely due to `list`'s higher cost of intermittently resizing as it shrinks, where `deque` is just freeing blocks back to free list or small object pool), so when selecting a data structure for a stack (aka LIFO queue), the empty-to-full-to-empty performance looks slightly better for `deque` (averages 6365K ops/sec for `append`/`pop`, vs. `list`'s 5578K ops/sec). I suspect `deque` would do slightly better in the real world, as `deque`'s freelist means growing for the first time is more expensive than growing after shrinking. – ShadowRanger Jan 10 '19 at 20:22
  • 1
    To clarify my freelist reference: CPython's `deque` will not actually `free` up to 16 blocks (module-wide, not per `deque`), instead putting them in a cheap array of available blocks for reuse. So when growing a `deque` for the first time, it always has to pull new blocks from `malloc` (making `append` more expensive), but if it's constantly expanding for a bit, then shrinking for a bit, and back and forth, it will usually not involve `malloc`/`free` at all so long as the length stays roughly within a range of 1024 elements (16 blocks on the free list, 64 slots per block). – ShadowRanger Jan 10 '19 at 20:26
  • Where did you get the source code? When I cmd+click on `deque` in PyCharm, it takes me to an abstract class in module `_collections.py`. – Abhijit Sarkar Dec 28 '19 at 02:50
  • @AbhijitSarkar: PyCharm and the like can only show you Python-level source code; much of the `collections` module is implemented in C, and you only have the compiled extension module for it, no source code. But CPython is open source; the source code is on GitHub, with most of the built-in extension modules in the `Modules` directory. The names aren't always intuitive since C source files don't have to correspond to the Python module name; in this case, [it's in `Modules\_collectionsmodule.c`](https://github.com/python/cpython/blob/master/Modules/_collectionsmodule.c). – ShadowRanger Oct 07 '20 at 17:03
20

The documentation entry for deque objects spells out most of what you need to know, I suspect. Notable quotes:

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.

But...

Indexed access is O(1) at both ends but slows to O(n) in the middle. For fast random access, use lists instead.

I'd have to take a look at the source to tell whether the implementation is a linked list or something else, but it sounds to me as though a deque has roughly the same characteristics as a doubly-linked list.

senderle
  • 145,869
  • 36
  • 209
  • 233
11

In addition to all the other helpful answers, here is some more information comparing the time complexity (Big-Oh) of various operations on Python lists, deques, sets, and dictionaries. This should help in selecting the right data structure for a particular problem.

PythonJin
  • 4,034
  • 4
  • 32
  • 40