Reduce average dictionary lookup time by making the internal tables more sparse.
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | def sparsify(d):
"""Improve dictionary sparsity.
The dict.update() method makes space for non-overlapping keys.
Giving it a dictionary with 100% overlap will build the same
dictionary in the larger space. The resulting dictionary will
be no more that 1/3 full. As a result, lookups require less
than 1.5 probes on average.
Example:
>>> import __builtin__
>>> sparsify(__builtin__.__dict__)
"""
e = d.copy()
d.update(e)
|
Apply this function to any dictionary where lookup time is important to your script's performance. The improved lookup times come at a cost of greater memory consumption and slower iteration times. So, avoid this function for memory critical applications or where the main use of the dictionary is iterating over the keys, values, or items.
Because of cache effects, small dictionaries do not benefit as much.
Apply this function after your dictionary is built and stabilized (meaning no further adds, deletes, or updates). Afterwards, the dictionary will have better lookup performance. The function itself takes time to run, so save it for dictionaries where there are going to a lot of lookups.
