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 nth 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:
6765
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.