Memoization and Decorators with Python
Recursion offers programmers a convenient way to break larger problems into manageable pieces. Consider the iterative versus recursive solutions for a fibonacci sum.
# iterative
def fib_iterative(n):
if (n == 0):
return 0
elif (n == 1):
return 1
elif (n >1 ):
fn = 0
fn1 = 1
fn2 = 2
for i in range(3, n):
fn = fn1+fn2
fn1 = fn2
fn2 = fn
return fn# recursive
def fib(n):
if n == 0:return 0
if n == 1:return 1
else: return fib(n-1) + fib(n-2)
Recursive solutions are often easier to read and write for branching problems. Tree traversals, graph traversals, and mathematical series are (often) dealt with more intuitively using recursion.
Though it affords convenience, the computational time cost of recursion on branching problems grows exponentially with larger values of n.
Lets take a look at the call stack for fib(6)
We do roughly twice as many operations at each successive level of the tree. Giving us a time complexity O(2^n).
If we take a closer look at our tree, you’ll notice that we’re repeating work. fib(2) is calculated five times, fib(3) is calculated three times and so on. Though this isn’t a problem for small values of n, imagine the amount of repeated work in calculating fib(1000). Once we revise our recursive solution, try running the same problem (say fib of 20) for both versions and notice the remarkable difference in the time to completion.
Surely there’s a good way to prevent repeated work, and keep our elegant solution?
Memoization: You can have your Cake and Eat it Too!
With memoization, we can “memoize” (remember, store) the result of problems that we’ve dealt with before, and return a stored result instead of repeating calculations.
For example, once fib(2) is calculated, we can store the result and use it the next four times fib(2) is encountered.
This reduces our run-time from O(2^n) to O(n) because we’re calculating each of fib(0)…fib(n) only once.
One way to accomplish this is using a dictionary.
__fib_cache = {}def fib_memo(n):
if n in __fib_cache:
return __fib_cache[n]
else:
__fib_cache[n] = n if n < 2 else fib_memo(n-2) + fib_memo(n-1)
return __fib_cache[n]
And voila! We’ve successfully memoized a recursive function!
However we can take things one step further and abstract memoization for any recursive function!
Decorators : Functions using functions to perform other Functions
Decorators are known as “Higher order functions” : functions that take other functions as parameters. Here we will use a decorator to generalize memoization.
Here is a decorated solution:
def memoize(func):
cache = func.cache = {} @functools.wraps(func)
def memoized_func(*args, **kwargs):
key = str(args) + str(kwargs)
if key not in cache:
cache[key] = func(*args, **kwargs)
return cache[key] return memoized_func@memoize
def fibonacci(n):
if n == 0:return 0
if n == 1:return 1
else: return fib(n-1) + fib(n-2)
Lets break it down line by line.
Our decorator is a function that takes another function as an argument, we declare it as such on line 1.
Next we declare a dictionary func.cache = {}, which is declared as a property offunc. Here we will store each unique call made by func.
We’ll come back to @functools.wraps.
def memoized_func(*args, **kwargs): — Inside the decorator we define a new, memoized function based on the func we passed in, and it takes in the same parameters are func. We call this new version memoized_func.
*args is a keyword indicating that memoizer takes an arbitrary number of arguments e.g.def memoize(one two three) or def memoize(just_one) are both valid. Similarly *kwargs represents an arbitrary number of keyword arguments (parameters defined at the function call) e.g. def memoize(one = 1, two = 2, three = 3) . Note : You can use these specialized parameters in any function.
The following line declares a key for our func.cache based on the parameters given. If we have seen this combination of parameters before, we pull the result from func.cache , otherwise create a new key using the original func as it was defined (e.g. using fib), and assign it’s value to the result e.g. ( store the result of fib(2)).
The last line inside memoized_func() returns the result of a single call to func with the given parameters.
The final line returns memoized_func(), which represents a modified version of our original function with added (decorated) features, that is, storing the result of each new call.
Finally we mark our original function with @memoize . The ‘@’ notation tells the compiler to pass the function immediately below it into a higher order function called memoized_func — which in our case returns a memoized version of fibonacci(). This version of the function will immediately return results we’ve calculated before, otherwise it will call the original fib() function to determine what that number should be.
What is @functools.wraps?
@functools.wraps is yet another decorator that is built into python. It allows decoratormemoize to store information related the memorized function’s docstring, or function name so that information can be accessed later. If we were to ask python fib.__name__ or fib.__doc__ (these are built in properties to functions), without @functools.wraps we it would return the name and docstring for memoized_fib and not fib itself. For debugging purposes, it’s helpful to have access to the name and docstring of the original function being called, not the decorating function, as the same decorator could be applied to a multitude of functions.
Try it yourself!
Next time you come across a recursive function, think about whether you can improve its performance with memoization, and then abstract that memoization to other functions by adding a decorator!
