Improving performance of very large dictionary in Python

by

If I know the number of keys and exactly what are those keys, is there
any way in python to make a dict (or a hashtable) work more
efficiently? I vaguely remember that if you know the keys, you can
design the hash function smartly (perfect hash?) and allocate the
space beforehand.

Python doesn’t expose a pre-sizing option to speed-up the “growth phase” of a dictionary, nor does it provide any direct controls over “placement” in the dictionary.

That said, if the keys are always known in advance, you can store them in a set and build your dictionaries from the set using dict.fromkeys(). That classmethod is optimized to pre-size the dictionary based on the set size and it can populate the dictionary without any new calls to __hash__():

>>> keys = {'red', 'green', 'blue', 'yellow', 'orange', 'pink', 'black'}
>>> d = dict.fromkeys(keys)  # dict is pre-sized to 32 empty slots

If reducing collisions is your goal, you can run experiments on the insertion order in the dictionary to minimize pile-ups. (Take a look at Brent’s variation on Algorithm D in Knuth’s TAOCP to get an idea of how this is done).

By instrumenting a pure Python model for dictionaries (such as this one), it is possible to count the weighted-average number of probes for an alternative insertion order. For example, inserting dict.fromkeys([11100, 22200, 44400, 33300]) averages 1.75 probes per lookup. That beats the 2.25 average probes per lookup for dict.fromkeys([33300, 22200, 11100, 44400]).

Another “trick” is to increase spareness in a fully populated dictionary by fooling it into increasing its size without adding new keys:

 d = dict.fromkeys(['red', 'green', 'blue', 'yellow', 'orange'])
 d.update(dict(d))     # This makes room for additional keys
                       # and makes the set collision-free.

Lastly, you can introduce your own custom __hash__() for your keys with the goal of eliminating all collisions (perhaps using a perfect hash generator such as gperf).

More Related Contents:

  1. Why is “1000000000000000 in range(1000000000000001)” so fast in Python 3?
  2. Are dictionaries ordered in Python 3.6+?
  3. Why is the order in dictionaries and sets arbitrary?
  4. Replace values in a pandas series via dictionary efficiently
  5. When is del useful in Python?
  6. Are tuples more efficient than lists in Python?
  7. What’s a correct and good way to implement __hash__()?
  8. Is a Python dictionary an example of a hash table?
  9. [] and {} vs list() and dict(), which is better?
  10. Is there anything faster than dict()?
  11. Accessing dictionary items by position in Python 3.6+ efficiently
  12. Python: get a dict from a list based on something inside the dict
  13. Why is variable1 += variable2 much faster than variable1 = variable1 + variable2?
  14. Why is a class __dict__ a mappingproxy?
  15. Dictionary vs Object – which is more efficient and why?
  16. How expensive are Python dictionaries to handle?
  17. Python: iterating over list vs over dict items efficiency
  18. Python: is “except KeyError” faster than “if key in dict”?
  19. Fast way to copy dictionary in Python
  20. differences between “d = dict()” and “d = {}”
  21. Is doing multiplication multiple times or assigning to a variable faster?
  22. “is” operator behaves unexpectedly with integers
  23. Make a dictionary with duplicate keys in Python
  24. Why do my Tkinter widgets get stored as None? [duplicate]
  25. How can you print a variable name in python? [duplicate]
  26. Speed comparison with Project Euler: C vs Python vs Erlang vs Haskell
  27. python tuple to dict
  28. Group by multiple keys and summarize/average values of a list of dictionaries
  29. python is operator behaviour with string [duplicate]
  30. Count() vs len() on a Django QuerySet

Leave a Comment