Memoization in Python

Memoization in Python

  1. Memoization in Python
  2. Execute Expensive Function Call Without Using Memoization in Python
  3. Execute Expensive Function Call With Memoization in Python

We will introduce the concept of memoization in Python and the benefits of using memoization in Python.

Memoization in Python

Memoization is an optimization procedure used to speed up computer programs. It stores the results of expensive function calls and returns the cached result of the same expensive function call with the same input.

This function saves the time to execute the same expensive function calls with the same inputs and get the results from the cached results.

Execute Expensive Function Call Without Using Memoization in Python

Let’s go through an example of an expensive function call and check how much time it takes to execute without using memoization in Python.

First of all, we will import time to check the time taken to execute a certain expensive function call, and we will use it to sleep for 1 second after every expensive function call.

We will define a func_exp(num) that will take an input of a number and return multiple of itself.

# python
import time
def func_exp(num):
    print(f"Executing {num}")
    time.sleep(1)
    return num*num

We will store the starting time in a variable begin and ending time in a variable end by using time.time(). We will call func_exp with 3 and 12 twice to check how long it takes to execute them.

At the bottom, we will get the time taken by subtracting time from end to begin, as shown below.

# python
begin = time.time()

result = func_exp(3)
print(result)
result = func_exp(12)
print(result)
result = func_exp(3)
print(result)
result = func_exp(12)
print(result)

end = time.time()
print(f"Total runtime of the program is {end - begin}")

Now, let’s run it and check how it works.

Output:

memoization in python example without memoization

As shown from the above example that it took four seconds of runtime.

Execute Expensive Function Call With Memoization in Python

Now let’s test it with memoization and check if we can optimize it or not. First, we will create an object fe_cache.

Inside our function func_exp(), we will create an if loop. If the num exists in fe_cache, it will get the result from the fe_cache and return it; otherwise, it will store the result in a variable and store it inside fe_cache before returning it, as shown below.

# python
import time

fe_cache = {}

def func_exp(num):
    print(f"Executing {num}")
    if num in fe_cache:
        return fe_cache[num]
    result = num*num
    fe_cache[num] = result
    time.sleep(1)
    return result

begin = time.time()

result = func_exp(3)
print(result)
result = func_exp(12)
print(result)
result = func_exp(3)
print(result)
result = func_exp(12)
print(result)
end = time.time()
print(f"Total runtime of the program is {end - begin}")

Now let’s run it and check how it works.

Output:

memoization in python example with memoization

As shown from the above example, it took half time to execute both functions twice because it stored the result, and instead of calculating again, it just got the result from the cache and returned them.

So memoization is used to make our application optimized for some tasks that require the same calculations.

Rana Hasnain Khan avatar Rana Hasnain Khan avatar

Rana is a computer science graduate passionate about helping people to build and diagnose scalable web application problems and problems developers face across the full-stack.

LinkedIn

Related Article - Python Memoization

  • Memoization in Python