Expensive Code: Ya, you read it right. In this article I’m going to brief on a way to speed up the Python programs and make expensive code cheaper with help of powerful caching technique called Memoization.

Memoization is the effective technique that is used to speed up the computer programs. It memorize or cache the returning results of the given input to the function. So, when the same input or parameter is passed to the given function, the cached results are returned instead of performing the whole computation again. Hence, it is simple and effective technique.

The Flow of the Memoization implementation

  • Create a data structure to store the cache results
  • Each time when the function is called, compute the results and return it to data structure for caching

Now, for the similar input we will return the cached results instead of re-computing it again. Here, I will write memoization technique from scratch with the help of decorator. The decorator is a function that take another function as the parameter and returns function as the output. If you are not familiar with the decorator then it might be little confusing at first, I would recommend to learn a bit about decorator.

 

def memoize(func):
	remember = {}
	
	def memoize_helper(*args):
		if args not in remember:
			result = func(*args)
		return remember[result]
	return memoize_helper

 

Here, I am using dict as the data structure for storing the cache results. Searching for the value in the dictionary is quick, hence it is effective for caching purpose. Here, when the decorated function is called, it will check for results in the cache for the given input. If found then it will return the cached results, else it will compute and store the results into the cache.

I will implement memoization on the Fibonacci series function. Let’s define the function that calculate the Fibonacci series.

 

def fibo(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fibo(n - 1) + fibo(n - 2)

 

Here, the computation Fibonacci will grow at the exponential rate. Hence, it is become pricey with growing results. Here, we will have execution time calculation with the help of timeit module in Python.

 

avoid writing expensive code in Python with Memoization

For computing the the 10th number in fibonacci, it took around 5 seconds on my machine. Now, let’s memoize this function and see the results. For the first run it would take a bit more but second run will have results as expected.

 

avoid writing expensive code in Python with Memoization

 

Let’s see how the results are stored in cache with the help of __closure__

 

avoid writing expensive code in Python with Memoization

 

WARNING: Here, we have the unbounded cache size which will keep eating your memory. And this is not the good idea, as it can raise out of memory bugs.

 

Inbuilt Function

In the above scenario we have written the decorator function from scratch. Now, lets implement the the memoization using the inbuilt function. And the inbuilt function will work far better then our manual function.

We will use the functools.lru_cache decorator for implementation of the memoization. lru_cache resides in the inbuilt functools package. Let’s try to implement our fibonacci function using functools.lru_cache. With this function we can also bound the cache memory with the help of maxsize parameter.

 

import functools
@functools.lru_cache(maxsize=128)
def fibo(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fibo(n - 1) + fibo(n - 2)

 

Let’s run and see the results. For the first time it will take a bit time because the cache is empty. In the second run we can see the expected results. And the results are self-explanatory.

avoid writing expensive code in Python with Memoization

First Run

avoid writing expensive code in Python with Memoization

Second Run

To check that how cache is stored by functools.lru_cache and how to clear the cache, fire below commands.

 

#Cache Info
fibo.cache_info()

#Clear Cache
fibo.cache_clear()

 

Hope, this will help to avoid writing expensive code. Keep sharing. Stay tuned to Tech Tunes for more.

 

Follow me in Twitter