How to speed up your python program with memoization

Hi guys

In this tutorial, you're going to learn how to write faster python apps using memoization, you learn how to build your own cache function together with utilizing builtin methods.

what is memoization?

Memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

Memoization can be explicitly programmed by the programmer, but some programming languages like Python provide mechanisms to automatically memoize functions.

Building our own memoizer

Let's say for example you have a recursive function to find Fibonacci  numbers of a given position .

Let's measure time taken to compute Fibonnaci number before and after memoization .

Below is a basic function for finding Fibonacci of given position

before memoization

I use time module to measure the total time taken to compute a Fibonacci number .

import time

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

beginning = time.time()
result = fibonacci(35)
Time_taken = time.time() - beginning
print(result)
print('Total time taken ', Time_taken, ' seconds')

output

kalebu@kalebu-PC:~$ python3 app.py 
9227465 
Total time taken  3.740154504776001  seconds

Now Let's implement our memoizer and measure again our speed after adding memoizer to our function

after memoization

I have built a simple function called memoize to memorize computed result so that next time when you call , it does not compute again but returning the memorized value

import time 

def memoize(f):
    memory = {}
    def memorized(x):
        if x not in memory:
            memory[x] = f(x)
            return memory[x]
        return memory[x]
    return memorized
    
@memoize
def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

beginning = time.time()
result = fibonacci(35)
Time_taken = time.time() - beginning
print(result)
print('Total time taken ', Time_taken, ' seconds')

Output

kalebu@kalebu-PC:~$ python3 app.py 
9227465 
Total time taken  2.2172927856445312e-05  seconds

As we can see the time for computations have been released to thousands of time .

Implementing memoizer while maintaining building your program can be quite challenging , thus why python has  builtin memoizer for you.

Python builtin memoizer is available in functools module , below a simple example on how you can use it .

Example of Usage :

import functools
import time

functools.lru_cache(maxsize=128)
def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

beginning = time.time()
result = fibonacci(35)
Time_taken = time.time() - beginning
print(result)
print('Total time taken ', Time_taken, ' seconds')

Output

kalebu@kalebu-PC:~$ python3 app.py 
9227465 
Total time taken  2.2411346435546875e-05  seconds

Hope you find this post interesting, don’t forget to subscribe to get more tutorials like this.

In case of any suggestion or comment, drop it in the comment box and I will reply to you immediately.