Take an expensive function:
def fib(n):
if n in [1, 2]: return 1
return fib(n - 1) + fib(n - 2)
%%time
fib(30)
Time: 02 s, 564 ms
832040
This would run much faster if we did not recompute particular values of fib.
def memoize(f):
cache = {}
def newf(n):
if n not in cache:
cache[n] = f(n)
return cache[n]
return newf
@memoize
def fib(n):
if n in [1, 2]: return 1
return fib(n - 1) + fib(n - 2)
%%time
fib(30)
Time: 00 s, 05 ms
832040