Understand Memoization - A Caching Technique with Python

Memoization is a technique used in computer programming to reduce the execution time of programs. The term memoization is based on a Latin word memorandum which means "to be remembered". This technique is frequently used in dynamic programming.

In the memoization, the result of a function call is saved in memory after it is invoked the first time with a certain set of input arguments. The next time you invoke the same function with the same input arguments, you can use the result from memory.

Consider the below pseudo-code examples:

# example -1 
function expensive_f(x):
  # Heavy computations code here
  -----
  -----

  return result

Equivalent pseudo-code with memoization technique:

# Example -2
memo = {}  # hash/dictionary/Associative-array
function expensive_f(x):
  if x in memo:

    return memo[x]
  else:
    # Heavy computations code here
    ------
    ------
   memo[x] = result 

    return result

In the example-1, function expensive_f() is performing (assumed) some heavy computations and returns the result. If this function gets invoked multiple times with the same x argument value, then each time it will repeat the computations and will return the result. Calling the function expensive_f(5) 100’s times will do the same computations again and again, and return the same result. Recursion is one of the most common examples where such repetitive function calls are made in a program

In the second example (example-2), the memoization concept is implemented by defining a memo variable (a hash or dictionary). Apparently, during each function call, expensive_f() checks if there is any previous result stored in the memo for an input argument,  if it exists then returns the result from the memo itself. Otherwise, it performs computations and stores the result in the memo.

 

Recursion with Memoization

You may already know that - "When a function calls itself, it is known as recursion, and such function calls repeat itself till a termination condition is met.

def rec_f(n):
	if n >= 1:
		rec_f(n)
		print(n)

In the above example, you can see that the function rec_f() is getting called by itself. This is an example of recursion, and rec_f() is a recursive function.

There are many places where recursion technique is used, for example - calculation of Fibonacci series, factorial, etc.  Let's see an example of Python function to find the Fibonacci of a given number using memoization and without using memoization concepts.

# no_memoize.py : Example-1 
# Recursive function recursive_fibo()
def recursive_fibo(n):
   if n <= 1:

       return n
   else:

       return(recursive_fibo(n-1) + recursive_fibo(n-2))

print(recursive_fibo(30))

In the above example, function recursive_fibo() uses a very common logic to calculate the Fibonacci series of a number. Executing this program with the cProfile module shows that it took 0.889 seconds to complete and made a total of 2692541 function calls (see below).

╰─ python -m cProfile no_memoize.py

832040
         2692541 function calls (5 primitive calls) in 0.889 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.889    0.889 no_memoize.py:1(<module>)
2692537/1    0.889    0.000    0.889    0.889 no_memoize.py:1(recursive_fibo)
        1    0.000    0.000    0.889    0.889 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.print}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

The below function recursive_fibo() is a new version of the same function defined in example-1 with additional memoization logic included.

# memoize.py : Example-2 
# Recursive function recursive_fibo() with Memoization
memo ={}
def recursive_fibo(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    else:
        result = recursive_fibo(n-1) + recursive_fibo(n-2)
        memo[n] = result
    
    return result

print(recursive_fibo(30))

Here is profiled output of the program :

╰─ python -m cProfile memoize.py
832040
         63 function calls (5 primitive calls) in 0.000 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 memoize.py:1(<module>)
     59/1    0.000    0.000    0.000    0.000 memoize.py:2(recursive_fibo)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.print}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

Apparently, cProfile shows that this time the program took 0.000 seconds (perhaps only a few microseconds) and made only 63 function calls during entire execution of the program. This drastic change in execution time and function calls are possible because of memoization techniques.

 

Memoization with Python Function Decorator

Python provides mechanisms to automatically memoize functions and decorator is an amazing feature that is very useful for easy implementation of memoization techniques. Decorators can change how the function behaves, without needing to actually change the original code. Common use cases of decorators are - adding logging, caching, authentication, etc.

A decorator is just a callable that takes a function (mostly) or a class as an argument and returns a function/class object. Decorators enhance the readability and maintainability of a program. This post is not about Python decorators so I am not going deep into what they are and their types or how they get invoked.

# Recursive function recursive_fibo() with Memoization using decorator

def memoize(f):
    memo = {}
    
    def wrapper(x):
        if x not in memo:            
            memo[x] = f(x)
            print('New result for recursive_fibo({})'.format(x))
        else:
            print('Result from cache : recursive_fibo({})'.format(x))
        
        return memo[x]
    
    return wrapper

@memoize
def recursive_fibo(n):  
    if n <= 1:
        return n
    else:
        return recursive_fibo(n-1) + recursive_fibo(n-2)

print(recursive_fibo(8))

Output:

New result for recursive_fibo(1)
New result for recursive_fibo(0)
New result for recursive_fibo(2)
Result from cache : recursive_fibo(1)
New result for recursive_fibo(3)
Result from cache : recursive_fibo(2)
New result for recursive_fibo(4)
Result from cache : recursive_fibo(3)
New result for recursive_fibo(5)
Result from cache : recursive_fibo(4)
New result for recursive_fibo(6)
Result from cache : recursive_fibo(5)
New result for recursive_fibo(7)
Result from cache : recursive_fibo(6)
New result for recursive_fibo(8)
21

In the above example, use of the @memoize decorator has made it easy to separate the actual logic of the function recursive_fibo from its memorization implementation.

 

Conclusion

• Memoization is a great technique that can make the code execute faster when you have repetitive/recursive function calls with the same set of arguments.

• A prerequisite for a function to be memoized is that it must be pure, which means it must always return the same value whenever it gets called with the same set of arguments.