# How to Implement Memoization in Python

Vaibhhav Khetarpal Feb 02, 2024

`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
``````

Vaibhhav is an IT professional who has a strong-hold in Python programming and various projects under his belt. He has an eagerness to discover new things and is a quick learner.