Memoize

A dictionary is often a cache. With a key we retrieve a stored value. We can use a dictionary, or functools, to perform caching.

Memoize, details

In a method call, we can turn the method parameters into a key, and store and retrieve values in a dictionary. This is called memoization.

`Dictionary` example

This program introduces compute(). This method receives one number and returns another. Compute() could be called many times with identical arguments.

And Each time, compute() must do its slow computations to calculate its result.

However If we add a dictionary cache, and memoize compute(), we must only do these computations once per key.

Info The first 10 calls to compute lead to stores within the dictionary. These calls are slower than a non-memoized compute method.

But In the last 5 calls, we use cached, memoized values. We avoid recomputing our values. We just do a dictionary lookup.

def compute(n):
    # Check the cache.
    if n in cache:
        return cache[n]

    # Do a computation.
    if n > 10:
        n = 10
    v = n ** n
    if v > 1000:
        v /= 2

    # Store the result.
    cache[n] = v
    return v

# Cache is a dictionary.
cache = {}

# Test.
print(compute(1))
print(compute(2))
print(compute(3))
print(compute(4))
print(compute(5))
print(compute(6))
print(compute(7))
print(compute(8))
print(compute(9))
print(compute(10))

# These use the cache.
print(compute(1))
print(compute(2))
print(compute(3))
print(compute(4))
print(compute(5))1
4
27
256
1562.5
23328.0
411771.5
8388608.0
193710244.5
5000000000.0
1
4
27
256
1562.5

`Lru_cache`

We can use functools to implement caching (memoization) in a more compact and easy-to-maintain way. We can specify the max number of cache entries with maxsize.

import functools

@functools.lru_cache(maxsize=12)
def compute(n):
    # We can test the cache with a print statement.
    if n > 10:
        n = 10
    v = n ** n
    if v > 1000:
        v /= 2
    return v

# Fill up the cache.
print(compute(1))
print(compute(2))
print(compute(3))
print(compute(4))
print(compute(5))

# Cache is hit now.
print(compute(1))
print(compute(2))
print(compute(3))
print(compute(4))
print(compute(5))1
4
27
256
1562.5
1
4
27
256
1562.5

Notes, memoization

Methods that are computationally intensive, use few different arguments and many identical calls, often become faster with memoization.

However Methods that receive a wide variety of arguments, or are called few times, become slower and receive no benefit.

Info Math methods can be memoized effectively if they are called with relatively few arguments in a program, and are slow to invoke.

A summary

Memoization is sometimes a useful optimization. And other times, it lends itself to excess memory use and slower execution times.