How expensive are Python dictionaries to handle?

by

dicts (just like sets when you don’t need to associate a value to each key but simply record if a key is present or absent) are pretty heavily optimized. Creating a dict from N keys or key/value pairs is O(N), fetching is O(1), putting is amortized O(1), and so forth. Can’t really do anything substantially better for any non-tiny container!

For tiny containers, you can easily check the boundaries with timeit-based benchmarks. For example:

$ python -mtimeit -s'empty=()' '23 in empty'
10000000 loops, best of 3: 0.0709 usec per loop
$ python -mtimeit -s'empty=set()' '23 in empty'
10000000 loops, best of 3: 0.101 usec per loop
$ python -mtimeit -s'empty=[]' '23 in empty'
10000000 loops, best of 3: 0.0716 usec per loop
$ python -mtimeit -s'empty=dict()' '23 in empty'
10000000 loops, best of 3: 0.0926 usec per loop

this shows that checking membership in empty lists or tuples is faster, by a whopping 20-30 nanoseconds, than checking membership in empty sets or dicts; when every nanosecond matters, this info might be relevant to you. Moving up a bit…:

$ python -mtimeit -s'empty=range(7)' '23 in empty'
1000000 loops, best of 3: 0.318 usec per loop
$ python -mtimeit -s'empty=tuple(range(7))' '23 in empty'
1000000 loops, best of 3: 0.311 usec per loop
$ python -mtimeit -s'empty=set(range(7))' '23 in empty'
10000000 loops, best of 3: 0.109 usec per loop
$ python -mtimeit -s'empty=dict.fromkeys(range(7))' '23 in empty'
10000000 loops, best of 3: 0.0933 usec per loop

you see that for 7-items containers (not including the one of interest) the balance of performance has shifted, and now dicts and sets have the advantages by HUNDREDS of nanoseconds. When the item of interest IS present:

$ python -mtimeit -s'empty=range(7)' '5 in empty'
1000000 loops, best of 3: 0.246 usec per loop
$ python -mtimeit -s'empty=tuple(range(7))' '5 in empty'
1000000 loops, best of 3: 0.25 usec per loop
$ python -mtimeit -s'empty=dict.fromkeys(range(7))' '5 in empty'
10000000 loops, best of 3: 0.0921 usec per loop
$ python -mtimeit -s'empty=set(range(7))' '5 in empty'
10000000 loops, best of 3: 0.112 usec per loop

dicts and sets don’t gain much, but tuples and list do, even though dicts and set remain vastly faster.

And so on, and so forth — timeit makes it trivially easy to run micro-benchmarks (strictly speaking, warranted only for those exceedingly rare situations where nanoseconds DO matter, but, easy enough to do, that it’s no big hardship to check for OTHER cases;-).

More Related Contents:

  1. How do I sort a list of dictionaries by a value of the dictionary?
  2. What is the best way to implement nested dictionaries?
  3. How are Python’s Built In Dictionaries Implemented?
  4. Replace values in a pandas series via dictionary efficiently
  5. Python Sets vs Lists
  6. What would a “frozen dict” be?
  7. In Python, when to use a Dictionary, List or Set?
  8. merging Python dictionaries
  9. [] and {} vs list() and dict(), which is better?
  10. List of all unique characters in a string?
  11. What is the purpose of collections.ChainMap?
  12. Key-ordered dict in Python
  13. Python: get a dict from a list based on something inside the dict
  14. Creating a tree/deeply nested dict from an indented text file in python
  15. Using a Python Dictionary as a Key (Non-nested)
  16. Recursive diff of two dictionaries (keys and values)?
  17. How to make a dictionary that returns key for keys missing from the dictionary instead of raising KeyError?
  18. Dictionary vs Object – which is more efficient and why?
  19. Adding counters deletes keys
  20. Python: iterating over list vs over dict items efficiency
  21. Python: is “except KeyError” faster than “if key in dict”?
  22. Fast way to copy dictionary in Python
  23. Improving performance of very large dictionary in Python
  24. differences between “d = dict()” and “d = {}”
  25. How to sort a list of dictionaries by a value of the dictionary in Python?
  26. Convert array dictionary to a dictionary python
  27. Roll rows of a matrix independently
  28. How to sort objects by multiple keys?
  29. Why is pow(a, d, n) so much faster than a**d % n?
  30. Accessing value inside nested dictionaries [duplicate]

Leave a Comment