Example of Memozing a Function

Take an expensive function:

In [1]:
def fib(n):
    if n in [1, 2]: return 1
    return fib(n - 1) + fib(n - 2)
In [3]:
%%time

fib(30)
Time: 02 s, 564 ms
Out[3]:
832040

This would run much faster if we did not recompute particular values of fib.

In [4]:
def memoize(f):
    cache = {}
    def newf(n):
        if n not in cache:
            cache[n] = f(n)
        return cache[n]
    return newf
In [5]:
@memoize
def fib(n):
    if n in [1, 2]: return 1
    return fib(n - 1) + fib(n - 2)
In [6]:
%%time

fib(30)
Time: 00 s, 05 ms
Out[6]:
832040
In [ ]: