deque.popleft() and list.pop(0). Is there performance difference?

Question

deque.popleft() and list.pop(0) seem to return the same result. Is there any performance difference between them and why?

Solution 1

Is there performance difference?

Yes. deque.popleft() is O(1) -- a constant time operation. While list.pop(0) is O(n) -- linear time operation: the larger the list the longer it takes.

Why?

CPython list implementation is array-based. pop(0) removes the first item from the list and it requires to shift left len(lst) - 1 items to fill the gap.

deque() implementation uses a doubly linked list. No matter how large the deque, deque.popleft() requires a constant (limited above) number of operations.

Solution 2

Yes, and it's considerable if you have a long list or deque. All elements in a list are placed contiguously in memory, so if you remove any element, all subsequent elements must be shifted one position to the left - therefore, the time required to remove or insert an element at the start of a list is proportional to the length of the list. A deque, on the other hand, is specifically constructed to allow fast insertions or removal at either end (typically by allowing "empty" memory locations at the beginning of the deque, or to wrap around so that the end of the memory segment occupied by the deque can contain elements that are actually considered to be at the beginning of the deque).

Compare the performance of these two snippets:

d = deque([0] * 1000000)
while d:
    d.popleft()
    if len(d) % 100 == 0:
        print(len(d))

lst = [0] * 1000000
while lst:
    lst.pop(0)
    if len(lst) % 100 == 0:
        print(len(lst))

Comments

[Bin]

Thanks. So for list the subsequest elements must be shifted.

[Andrea Corbellini]

BTW, the same holds for deque.appendleft() vs list.insert(0)

[jfs]

@Bin: I've only mentioned CPython because I can't find the appropriate reference in the spec (it looks like a bug if Python reference doesn't specify the time complexity for Python list). Though in practice, all Python implementations (that I know of) respect the expected informal time complexity for list operations.

[Aasmund Eldhuset]

Bin: Yes. @AndreaCorbellini: Quite so.

[Admin]

docs.python.org/2/library/collections.html#collections.deque comments on the time complexity of list for pop(0) and insert(0, v).

[jfs]

@TrisNefzger: deque docs express "common knowledge" but specifying the list behavior in passing seems less binding then the language reference.

[Admin]

You are totally right. There should be an official, binding document of the performance characteristics of Python collection-like data structures similar to docs.scala-lang.org/overviews/collections/… for Scala.