Welcome, guest | Sign In | My Account | Store | Cart

Reduce average dictionary lookup time by making the internal tables more sparse.

Python, 17 lines
 1
 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.

Created by Raymond Hettinger on Sun, 4 May 2003 (PSF)
Python recipes (4591)
Raymond Hettinger's recipes (97)

Required Modules

  • (none specified)

Other Information and Tasks