python: deque vs list performance comparison

by

Could anyone explain me what I did wrong here

Yes, your timing is dominated by the time to create the list or deque. The time to do the pop is insignificant in comparison.

Instead you should isolate the thing you’re trying to test (the pop speed) from the setup time:

In [1]: from collections import deque

In [2]: s = list(range(1000))

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

That said, 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.

More Related Contents:

  1. Why does Python code run faster in a function?
  2. What is the most efficient way of finding all the factors of a number in Python?
  3. How can I make a for-loop pyramid more concise in Python? [duplicate]
  4. Why is looping over range() in Python faster than using a while loop?
  5. Implement MATLAB’s im2col ‘sliding’ in Python
  6. Numpy: Fix array with rows of different lengths by filling the empty elements with zeros
  7. Python Requests vs PyCurl Performance
  8. Python Slice Assignment Memory Usage
  9. sum each value in a list of tuples
  10. Python Numpy Data Types Performance
  11. What are the differences between bool() and operator.truth()?
  12. Is there a reason Python 3 enumerates slower than Python 2?
  13. What is the best approach in python: multiple OR or IN in if statement?
  14. deque.popleft() and list.pop(0). Is there performance difference?
  15. Fastest way to check if a value exists in a list
  16. Running an Excel macro via Python?
  17. What is the right way to debug in iPython notebook?
  18. How to get current time in python and break up into year, month, day, hour, minute?
  19. why isn’t numpy.mean multithreaded?
  20. Why is Collections.counter so slow?
  21. Any way to speed up Python and Pygame?
  22. How to convert integer into date object python?
  23. Trying to use open(filename, ‘w’ ) gives IOError: [Errno 2] No such file or directory if directory doesn’t exist
  24. matplotlib savefig performance, saving multiple pngs within loop
  25. Sound generation / synthesis with python?
  26. how to open chrome in incognito mode from Python
  27. Matplotlib just giving error messages
  28. improving python code in Monte Carlo simulation
  29. How can I read pdf in python? [duplicate]
  30. Searching in Google with Python

Leave a Comment