# 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.07 ms
Memoized: 0.07 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
```