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

by

deque.popleft() is faster than list.pop(0), because the deque has been optimized to do popleft() approximately in O(1), while list.pop(0) takes O(n) (see deque objects).

Comments and code in _collectionsmodule.c for deque and listobject.c for list provide implementation insights to explain the performance differences. Namely that a deque object “is composed of a doubly-linked list”, which effectively optimizes appends and pops at both ends, while list objects are not even singly-linked lists but C arrays (of pointers to elements (see Python 2.7 listobject.h#l22 and Python 3.5 listobject.h#l23), which makes them good for fast random access of elements but requires O(n) time to reposition all elements after removal of the first.

For Python 2.7 and 3.5, the URLs of these source code files are:

  1. https://hg.python.org/cpython/file/2.7/Modules/_collectionsmodule.c

  2. https://hg.python.org/cpython/file/2.7/Objects/listobject.c

  3. https://hg.python.org/cpython/file/3.5/Modules/_collectionsmodule.c

  4. https://hg.python.org/cpython/file/3.5/Objects/listobject.c

Using %timeit, the performance difference between deque.popleft() and list.pop(0) is about a factor of 4 when both the deque and the list have the same 52 elements and grows to over a factor of 1000 when their lengths are 10**8. Test results are given below. 

import string
from collections import deque

%timeit d = deque(string.letters); d.popleft()
1000000 loops, best of 3: 1.46 µs per loop

%timeit d = deque(string.letters)
1000000 loops, best of 3: 1.4 µs per loop

%timeit l = list(string.letters); l.pop(0)
1000000 loops, best of 3: 1.47 µs per loop

%timeit l = list(string.letters);
1000000 loops, best of 3: 1.22 µs per loop

d = deque(range(100000000))

%timeit d.popleft()
10000000 loops, best of 3: 90.5 ns per loop

l = range(100000000)

%timeit l.pop(0)
10 loops, best of 3: 93.4 ms per loop

More Related Contents:

  1. Fastest way to check if a value exists in a list
  2. Get difference between two lists
  3. Why does Python code run faster in a function?
  4. Python Sets vs Lists
  5. Are tuples more efficient than lists in Python?
  6. Replace values in list using Python [duplicate]
  7. Why is [] faster than list()?
  8. list() uses slightly more memory than list comprehension
  9. What is the time complexity of popping elements from list in Python?
  10. Python – How to check list monotonicity
  11. [] and {} vs list() and dict(), which is better?
  12. Why is tuple faster than list in Python?
  13. python: deque vs list performance comparison
  14. Complexity of list.index(x) in Python
  15. Python: get a dict from a list based on something inside the dict
  16. Most efficient way for a lookup/search in a huge list (python)
  17. Create random list of integers in Python
  18. Creating an empty list in Python
  19. Get difference between two lists with Unique Entries
  20. Is there a way to circumvent Python list.append() becoming progressively slower in a loop as the list grows?
  21. sum each value in a list of tuples
  22. Python List Indexing Efficiency
  23. Python: iterating over list vs over dict items efficiency
  24. First items in inner list efficiently as possible [duplicate]
  25. Why shouldn’t I use PyPy over CPython if PyPy is 6.3 times faster?
  26. Which is the most efficient way to iterate through a list in python?
  27. Length of longest word in a list
  28. Simple Python Challenge: Fastest Bitwise XOR on Data Buffers
  29. Select 50 items from list at random
  30. Head and tail in one line

Leave a Comment