How to Implement Memoization in Python

1. Use a Simple Dictionary to Implement Memoization in Python
2. Use a Memoization Class to Implement Memoization in Python
3. Use a Decorator to Implement Memoization in Python
4. Use the functools.lru_cache Decorator to Implement Memoization in Python
5. Use the functools.cache Decorator to Implement Memoization in Python

Memoization is a technique used to speed up calculations by remembering the calculations done in the past.

It stores a certain number of past calculations to make it easy for future calculations.

Memoization is utilized to calculate factorials and the Fibonacci series problems.

Use a Simple Dictionary to Implement Memoization in Python

A dictionary is one of Python’s four fundamental data types to store data. It works when dealing with function calls and retrieving and storing the data.

memo1 = {}


def fact1(x):
    if x < 2:
        return 1
    if x not in memo1:
        memo1[x] = x * fact1(x - 1)
    return memo1[x]


for i in range(1, 10):
    print(fact1(i))

Output:

1
2
6
24
120
720
5040
40320
362880

Code Explanation:

• First, a dictionary memo1 is initialized that stores the values in the memoization process.
• Secondly, we create and blend the function for factorial and the dictionary that stores the values.
• The function can then be called to display the desired results.

As the dictionary stores more and more terms, the speed of this method gets affected and decreases by a high margin.

Making it obsolete in the cases where a large amount of data needs to be stored with the help of Memoization.

Use a Memoization Class to Implement Memoization in Python

This method encapsulates the whole memoization process into a class and separates it from the main factorial function.

class Memoize:
    def __init__(self, x):
        self.x = x
        self.memo = {}

    def __call__(self, *args):
        if not args in self.memo:
            self.memo[args] = self.x(*args)
        return self.memo[args]


def fact1(a):
    if a < 2:
        return 1
    return a * fact1(a - 1)


fact1 = Memoize(fact1)
for i in range(1, 10):
    print(fact1(i))

Output:

1
2
6
24
120
720
5040
40320
362880

Code Explanation:

• First, a Memoize class is defined and the __init__ function and the __call__ function are defined under it.
• Then, the user-defined fact1 function is defined to calculate the factorial with the help of recursion.
• The output is then displayed with the help of the print command.

The only drawback to this method is that it increases the length of the code and makes it a bit more complex.

Use a Decorator to Implement Memoization in Python

A decorator can be defined as a function that can take in another function as its sole parameter. Two decorators can be utilized to implement Memoization in Python.

Use the functools.lru_cache Decorator to Implement Memoization in Python

The functools.lru_cache is available to use in the versions Python 3.2+ and is utilized to cache the function calls. It is capable of storing a maximum of 128 recently used calls.

A simple tweak can set the cache to not expire during the code’s runtime. The functools library needs to be imported to the python code to implement this method without any errors.

import functools


@functools.lru_cache(maxsize=None)
def fact1(x):
    if x < 2:
        return 1
    return x * fact1(x - 1)


for i in range(1, 10):
    print(fact1(i))

Output:

1
2
6
24
120
720
5040
40320
362880

Use the functools.cache Decorator to Implement Memoization in Python

The functools.cache decorator was made available in Python 3.9 and applied only on the relatively newer versions of Python to date.

The function stores or caches the value returned when a function is called with a specified set of arguments.

The functools library needs to be imported to the python code to implement this method without any errors.

import functools


@functools.cache
def fact1(x):
    if x < 2:
        return 1
    return x * fact1(x - 1)


for i in range(1, 10):
    print(fact1(i))

Output:

1
2
6
24
120
720
5040
40320
362880