Memoization in Python - A Brief Introduction

In this tutorial, we are going to discuss one of the very popular optimization techniques – Memoization in Python – primarily used to speed up computer programs. So, let’s get started!

What is memoization in Python?

In the world of computer programming, Memoisation or Memoization in Python is a special kind of optimization technique that is primarily used to speed up our computer program. It effectively reduces the runtime of the computer program by storing the results of the expensive (in terms of runtime) function calls into the memory and using it whenever any stored or cached value is required.

It ensures that a particular function or method does need not run more than once for the same set of inputs as the results are already available as cached /stored data.

It is similar to caching. It involves caching the return values of the function based on its input parameters.

In Python, we can implement the memoization technique in our programs using function and class-based decorators. And we will be using a recursive Python program to calculate the n^th Fibonacci number in our whole discussion because for greater inputs this program will become very very slow because the number of function calls for the same input values increase with the input size.

Memoization in Python using function based decorators

It is the best and the complex way of implementing the memoization technique in Python, for those who want to understand how this optimization technique actually works. In this method of implementation of memoization technique, we define our own decorator function in Python to cache/store the return values of the function calls. Let’s see how to write Python code to implement this.

# Memoization using function-based decorators

def memoize(f):
    cache = {}
    def foo(x):
        if x not in cache:
            cache[x] = f(x)
        return cache[x]
    return foo

@memoize
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

# Driver code
fibonacci(20)

Output:

Memoization using class based decorators

It is the second-best and the complex way of implementing the memoization technique in Python, for beginners who want to understand how this optimization technique actually works. In this method of implementation of memoization technique, we define our own decorator class in Python to cache/store the return values of the function calls. Let’s write Python code to implement this.

# Memoization using class-based decorators

class classMemoize:
    def __init__(self, f):
        self.f = f
        self.cache = {}
    def __call__(self, *x):
        if x not in self.cache:
            self.cache[x] = self.f(*x)
        return self.cache[x]

@classMemoize
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

# Driver code
fibonacci(50)

Output

12586269025

Memoization using built-in decorator functions

It is one of the simple and the easiest way to implement the memoization technique in Python.

In this method of implementation of memoization technique, we do not define our own decorator function or class but we make use of the built-in functions like lru_cache() and cache() to cache/store the intermediate results of a function call.

These lru_cache() and cache() functions are defined in the funtools library which is a standard Python library and it comes with the normal Python installation.

The lru_cache(maxsize=None, typed=False) function offers some customization features through its parameters like maxsize and typed. The parameter maxsize decides if the LRU features will be enabled or not by setting its value either None or an integer value. And the parameter typed decides if the different types of data are to be cached separately or not.

An integer Value will limit the size of the cache maintained during the execution of the Python program and the None value will disable the LRU features and then the cache can grow without any bound.

The cache() function is available from the Python 3.9 release onwards and it is equivalent to the lru_cache(maxsize=None) function in the funtools library.

# Memoization using built-in function

import functools

@functools.cache
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

# Driver code
fibonacci(100)

Output:

354224848179261915075

Conclusion

In this tutorial, we have learned how to use the memoization technique in Python using function and class-based decorators. I hope you have well understood the things discussed above and are ready to use/implement this memoization technique in your Python program to boost its speed.