Memoization (caching)

What is memoization?

Memoization is a way to optimize code by storing the return values of functions called with a specific set of arguments. Memoization is often used in combination with functional programming. Memoization is a specific type of caching.

When (not) to memoize?

Memoization is only valid for functions that are referentially transparent, that is, functions that always return the same result for the same set of arguments, and that do not affect the state of the program.

Therefore, you should not memoize a function that returns random numbers, because it will end up returning the same set of random numbers over and over again. And you should also not memoize a function that depends on the state of the program, for example because it relies on the command-line arguments that were passed to a script.

But you could memoize a function that performs some time consuming operation that is always done in exactly the same way, such as a function that performs time-consuming operations on a large dataset.

Examples

Basic memoization

Memoization is done with the memoize decorator that is part of datamatrix.functional. Let's take a time-consuming function that determines the highest prime number below a certain value, and measure the performance improvement that memoization gives us when we call the function twice with same argument.

import time
from itertools import dropwhile
from datamatrix import functional as fnc


@fnc.memoize
def prime_below(x):

    """Returns the highest prime that is lower than X."""

    print('Calculating the highest prime number below %d' % x)
    return next(
        dropwhile(
            lambda x: any(x//i == float(x)/i for i in range(x-1, 2, -1)),
            range(x-1, 0, -1)
            )
        )


t0 = time.time()
prime_below(10000)
t1 = time.time()
prime_below(10000)
t2 = time.time()

print('Fresh: %.2f ms' % (1000*(t1-t0)))
print('Memoized: %.2f ms' % (1000*(t2-t1)))

Output:

Calculating the highest prime number below 10000
Fresh: 59.58 ms
Memoized: 0.04 ms

Chaining memoized functions and lazy evaluation

When you call a function, Python automatically evaluates the function arguments. This happens even if a function has been memoized. In some cases, this is undesirable because evaluating the arguments may be time-consuming in itself, for example because one of the arguments is a call to another time-consuming function.

Ideally, evaluation of the arguments occurs only when the memoized function actually needs to be executed. To approximate this behavior in Python, the memoize decorator accepts the lazy keyword. When lazy=True is specified, all callable objects that are passed to the memoized function are evaluated automatically, but only when the memoized function is actually executed.

from itertools import dropwhile
from datamatrix import functional as fnc


@fnc.memoize(lazy=True)
def prime_below(x):

    print('Calculating the highest prime number below %d' % x)
    return next(
        dropwhile(
            lambda x: any(x//i == float(x)/i for i in range(x-1, 2, -1)),
            range(x-1, 0, -1)
            )
        )


def thousand():

    print('Returning a thousand!')
    return 1000


print(prime_below(thousand))
print(prime_below(thousand))

Output:

Returning a thousand!
Calculating the highest prime number below 1000
997
997

A slightly more complicated situation arises when you want to pass arguments to a function that is itself passed as argument, without evaluating the function. To accomplish this, you can first bind the argument to the function using functools.partial and then pass the resulting partial function as an argument. Like so:

from functools import partial
from itertools import dropwhile
from datamatrix import functional as fnc


@fnc.memoize(lazy=True)
def prime_below(x):

    print('Calculating the highest prime number below %d' % x)
    return next(
        dropwhile(
            lambda x: any(x//i == float(x)/i for i in range(x-1, 2, -1)),
            range(x-1, 0, -1)
            )
        )

print(prime_below(partial(prime_below, 1000)))
print(prime_below(partial(prime_below, 1000)))

Output:

Calculating the highest prime number below 1000
Calculating the highest prime number below 997
991
991

Persistent memoization, memoization keys, and cache clearing

If you pass persistent=True to the memoize decorator, the cache will be written to disk, in a subfolder .memoize of the current working directory. The filename will correspond to the memoization key, which by default is derived from the function name and the arguments.

You can also specify a custom memoization key through the key keyword. If you specify a custom key, memoize will no longer distinguish between different arguments (and thus no longer be real memoization).

To re-execute a memoized function, you can either specify ~[function_name] as a command-line argument, or pass memoclear=True to the memoized function (not to the decorator).

from itertools import dropwhile
from datamatrix import functional as fnc


@fnc.memoize(persistent=True, key='custom-key')
def prime_below(x):

    print('Calculating the highest prime number below %d' % x)
    return next(
        dropwhile(
            lambda x: any(x//i == float(x)/i for i in range(x-1, 2, -1)),
            range(x-1, 0, -1)
            )
        )


print(prime_below(1000))
print(prime_below(1000))
print(prime_below(1000, memoclear=True)) # Clear the cache

Output:

Calculating the highest prime number below 1000
997
997
Calculating the highest prime number below 1000
997