Python: iterating over list vs over dict items efficiency

by

It depends on which version of Python you’re using. In Python 2, some_dict.items() creates a new list, which takes up some additional time and uses up additional memory. On the other hand, once the list is created, it’s a list, and so should have identical performance characteristics after the overhead of list creation is complete.

In Python 3, some_dict.items() creates a view object instead of a list, and I anticipate that creating and iterating over items() would be faster than in Python 2, since nothing has to be copied. But I also anticipate that iterating over an already-created view would be a bit slower than iterating over an already-created list, because dictionary data is stored somewhat sparsely, and I believe there’s no good way for python to avoid iterating over every bin in the dictionary — even the empty ones.

In Python 2, some timings confirm my intuitions:

>>> some_dict = dict(zip(xrange(1000), reversed(xrange(1000))))
>>> some_list = zip(xrange(1000), xrange(1000))
>>> %timeit for t in some_list: t
10000 loops, best of 3: 25.6 us per loop
>>> %timeit for t in some_dict.items(): t
10000 loops, best of 3: 57.3 us per loop

Iterating over the items is roughly twice as slow. Using iteritems is a tad bit faster…

>>> %timeit for t in some_dict.iteritems(): t
10000 loops, best of 3: 41.3 us per loop

But iterating over the list itself is basically the same as iterating over any other list:

>>> some_dict_list = some_dict.items()
>>> %timeit for t in some_dict_list: t
10000 loops, best of 3: 26.1 us per loop

Python 3 can create and iterate over items faster than Python 2 can (compare to 57.3 us above):

>>> some_dict = dict(zip(range(1000), reversed(range(1000))))
>>> %timeit for t in some_dict.items(): t      
10000 loops, best of 3: 33.4 us per loop

But the time to create a view is negligable; it is actually slower to iterate over than a list. 

>>> some_list = list(zip(range(1000), reversed(range(1000))))
>>> some_dict_view = some_dict.items()
>>> %timeit for t in some_list: t
10000 loops, best of 3: 18.6 us per loop
>>> %timeit for t in some_dict_view: t
10000 loops, best of 3: 33.3 us per loop

This means that in Python 3, if you want to iterate many times over the items in a dictionary, and performance is critical, you can get a 30% speedup by caching the view as a list. 

>>> some_list = list(some_dict_view)
>>> %timeit for t in some_list: t
100000 loops, best of 3: 18.6 us per loop

More Related Contents:

  1. [] and {} vs list() and dict(), which is better?
  2. Python: get a dict from a list based on something inside the dict
  3. I don’t know how to display step 3 for this assignment
  4. How to make a dict from n’th indices of tuples in list
  5. Access a particular field in arbitrarily nested JSON data [duplicate]
  6. How to avoid “RuntimeError: dictionary changed size during iteration” error?
  7. Are tuples more efficient than lists in Python?
  8. Why is [] faster than list()?
  9. How can I convert a dictionary into a list of tuples?
  10. merging Python dictionaries
  11. How can I initialize a dictionary of distinct empty lists in Python?
  12. List of tuples to dictionary [duplicate]
  13. Converting Dictionary to List? [duplicate]
  14. How to find the min/max value of a common key in a list of dicts?
  15. Converting a list of tuples into a dict
  16. Appending a dictionary to a list in a loop
  17. One liner: creating a dictionary from list with indices as keys
  18. Group by multiple keys and summarize/average values of a list of dictionaries
  19. Complexity of list.index(x) in Python
  20. How do I sort this list in Python, if my date is in a String?
  21. Get difference between two lists with Unique Entries
  22. How expensive are Python dictionaries to handle?
  23. What are dict_keys, dict_items and dict_values?
  24. How do I send list of dictionary as Body parameter in FastAPI?
  25. Python The appended element in the list changes as its original variable changes
  26. Mapping dictionary value to list
  27. Which is the most efficient way to iterate through a list in python?
  28. How to sort a list of dictionaries by a value of the dictionary in Python?
  29. Length of longest word in a list
  30. How to create a nested dictionary from a list in Python?

Leave a Comment