# What Is Memoization in Python

9K

The term memoization gets its name from the Latin word memorandum meaning — ‘to be remembered’. Donald Michie, a British researcher in AI, introduced the term in the year 1968. It may look like a misspelling of the word memorization, but it comprises recording a value to look upon the function later. Above all, it is often a crucial technique in solving problems using Dynamic Programming.

## Definition of Memoization

Memoization is an efficient software optimization technique used to speed up programs. It allows you to optimize a python function by catching its output based on the supplied input parameters. Memoization ensures that a method runs for the same input only once. Moreover, it keeps the output records for the given set of inputs in a hash map. That means, when you memorize a function, it will only compute the output once for every set of parameters called-with.

### Fibonacci sequence

A Fibonacci sequence is a series where each term is the sum of the preceding two terms. It plays a vital role in testing the memorization decorator recursively. We begin by defining the python function that calculates the nth Fibonacci number.

Program to find Fibonacci Series using recursive functions.

def fibonacci(n):
if (n < 2):
return 1
return (fibonacci(n - 1) + fibonacci(n - 2))
print(fibonacci(8)) 

Output:

34

Note: The Fibonacci series we got using a recursive function takes strenuous efforts plus consumes a lot of time. Calculating the nth Fibonacci number this way has an overall runtime of 0(2^n) – the code takes exponential time to execute. It seems expensive, right?

### Fibonacci with Memoization

To speed up the program, we will take advantage of memoize() function by defining it. Let us understand with the help of an example.

def memoize(k):
fast = {}
def partner(l):
if l not in fast:
fast[l] = k(l)
return fast[l]
return partner
def fibonacci(n):
if (n<2):
return 1
return (fibonacci(n-1) + fibonacci(n-2))
fibonacci = memoize(fibonacci)
print(fibonacci(25))  

Output:

121393

The memoize() takes a function as an argument and uses a dictionary to store results. In the code, you will find the partner function captures the variable “fast” and the function “k” – which gets returned as a reference by memoizing(). So, the call memoize(fibonacci) returns a reference to the partner() doing the same work as fibonacci() would do on its own, saving time.

### Memoization with Function Decorators

Python comes up with additional capabilities, helping programmers to add functionalities to a pre-existing code. It allows the implementation of the memoization algorithm seamlessly with no hassle. The above code can be written in a more sophisticated manner using decorator.

### Let’s Write a Memoization Decorator from Scratch

Let’s rewrite the above code by replacing fibonacci = memoize(Fibonacci) with a decorator. We have decorated our Fibonacci function using @memoize.

def memoize(f):
fast = {}
def partner(l):
if l not in fast:
fast[l] = f(l)
return fast[l]
return partner
@memoize
def fibonacci(n):
if (n < 2):
return 1
return (fibonacci(n - 1) + fibonacci(n - 2))
print(fibonacci(25))

Output:

121393

### Using a Callable Class for Memoization

Python also allows encapsulating the results using a callable class. Let’s have a look with an example:

class Memoize:
def __init__(self, gx):
self.gx = gx
self.fast = {}
def __call__(self, *args):
if args not in self.fast:
self.fast[args] = self.gx(*args)
return self.fast[args]
@Memoize
def fibonacci(n):
if (n < 2):
return 1
return (fibonacci(n - 1) + fibonacci(n - 2))
print(fibonacci(25)) 

Output:

121393

## Why and When Should You Use Memoization in Your Python Programs?

The idea behind memoization –

1. Implementation simplicity
2. Algorithm maturity
3. Very high performance

To solve a problem when the sub-problems have to be solved repeatedly – we use memoization. Try fibonacci(25), and you will find the execution time at snail speed. Perhaps you have to wait about ten seconds to get the final output. Usually, memoization is an operation you can apply to any function that computes something (expensive) and returns a value. The total time, therefore, is O(n^3). Memoization thus turns an O(n^2)-time algorithm into an O(n^3) time algorithm. Without memoization, the natural recursive algorithm runs in the exponential time since solved subproblems are repeatedly solved.

## The Memoization Algorithm Explained

A memoize recursive algorithm maintains an entry in a table for the solution to each subproblem. Each table entry initially contains a unique value to show that the entry has yet to be filled. When the subproblem encountered as the recursive algorithm unfolds, its solution is computed and then stored in the table. Each subsequent time we deal with this subproblem, we merely look up the value stored in the table and return it.

Steps involved in memoization algorithm: -

1. Identify a sub-problem.
2. Store the sub-problem in the data structure.
3. Create a cache data structure for the function results

Whenever you call a function, return the cached results. Start calling the function to compute the missing result and then update the cache before returning to the caller. Sufficient cache storage guarantees that the function resulting for a specific set of function arguments will compute more than once. Once you get a cached result, stop re-running the memorize function for the same set of inputs. Instead, fetch the cached result and return it, anyway.

## Memoization by hand: Misusing a default parameter

Cache, the keyword parameter gets evaluated in Python, when the function gets imported. Only if we have a mutable keyword parameter, it gets initialized, else it does notPython can assess the keyword parameters only once only when the functions come from other sources. That means the keyword parameter is changeable once assigned.

In case there are any changes in populating the cache, it doesn’t get wiped out by the cache = { } in the function definition because the expression is not re-evaluated.

Let us understand memoization by hand with the help of an example.

def fib_default_memoized(l, cache={}):
if l in cache:
catch = cache[l]
elif l <= 2:
catch = 1
cache[l] = catch
else:
catch = fib_default_memoized(l - 2) + fib_default_memoized(l - 1)
cache[l] = catch
return catch 

### Memoization by hand: objects

Memoization by hand is contrary to the Java programmers, who stand in favor of creating functions with the state as objects. Perhaps some say that changing the formal parameters is not a good option. When calling from Python objects, it is crucial to define them in the constructor. Its result purely depends on the server.

Let’s understand this with the help of an example:

class Fib():
cache = {}
def __call__(self, l):
if l in self.cache:
ans = self.cache[l]
if l <= 2:
catch = 1
self.cache[l] = catch
else:
catch = self(l - 2) + self(l - 1)
self.cache[l] = catch
return catch  

### Memorization by hand: using global

Annoyed with the hacky mutation of default parameters? The use of global keywords will help you to get rid of changes in the default parameters. Let’s understand this with the help of an example:

global_cache = {}
def fib_global_memoized(l):
global global_cache
if l in global_cache:
catch = global_cache[l]
elif l <= 2:
catch = 1
global_cache[l] = catch
else:
catch = fib_global_memoized(l - 2) + fib_global_memoized(l - 1)
global_cache[l] = catch
return catch 

### An aside: decorators

A decorator is designed in such a way that it can turn a conversation into a function. It can also turn it into another function. The initial conversation is returned with more functionality — a demerit to the initial function. The effects of the returned functionality are similar to a logging function.

def output_decorator(fun):
def f_(fun):
fun()
print('Ran f...')
return f_
Is the same as:
@output_decorator
def fun(): 

The side-effects of the returned functions are not pleasing at all. We can evade the side effects by deciding to argue the input function itself. In memoization, the defined-function gets added to the required cache in the argument.

### Functools.lru.cache

For memoizing functions, programmers must execute the functools.lru_cache because it clearly defines the initial functionality, which has an extra import and a decorator. During the execution of decorator, it assures you of six orders of magnitude speedup expected. The LRU included in the lru_cache is an excellent caching strategy that defines a clear policy to expel elements when the cache is fullallowing new elements to enter. In short, it discards the least recently used items first and makes room for new entries.

### Python memoization with functools.lru_cache

The Python sophisticated module functools is for higher order functions that return other functions. Once you master how to use anwhen to use lru_cacheyou can speed up your application by merely writing a few lines of codes.

Let us understand python memoization with functools.lru_cache with the help of an example.

import functools
@functools.lru_cache()
def fib_lru_cache(n):
if n < 2:
return n
else:
return fib_lru_cache(n - 2) + fib_lru_cache(n - 1) 

### Inspecting the Function Results Cache.

You can inspect the return values using the __closure__ attribute. It allows us to retrieve these results quickly from the cache instead of slowly re-computing them from scratch.

### Caching Caveats – What Can Be Memoized?

In Python, you can memoize() any deterministic function when the same inputs occur. Simply put, the output will return the same value based on the particular setoff inputs. For indeterministic functions, memoize() function is perhaps not an excellent choice.

Memoization in Python: Quick Summary

Memoization works like magic to solve problems where solutions to subproblems can be used again, especially if the function takes some time to execute. Of course, since the data has to be stored somewhere, memoization will take more memory. It is a trade-off between using CPU and using RAM. Perhaps it is an exchange of time for space.

### Abhresh Sugandhi

Author

Abhresh is specialized as a corporate trainer, He has a decade of experience in technical training blended with virtual webinars and instructor-led session created courses, tutorials, and articles for organizations. He is also the founder of Nikasio.com, which offers multiple services in technical training, project consulting, content development, etc.