Memoization decorator in python

Subscribe to my newsletter and never miss my upcoming articles

In the previous articles on the Python decorator series, we have learnt decorators, how they work and to implement a simple function based decorator and a class based decorator and decorator that supports parameters. In this article, we will create a simple memoization decorator function that caches result.

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

Factorial of a number

Let's create a function that calculates factorial of a number in a recursive way.


def factorial(n):
    if n == 1:
        return n
    else:
        return n * factorial(n - 1)


if __name__ == '__main__':
    print(factorial(20))
    print(factorial(10))
    print(factorial(15))
    print(factorial(5))

Output

2432902008176640000
3628800
1307674368000
120

Since factorial of a given number is always same(idempotent), We can optimize this function by caching results for the given value. Let's create the decorator function,

from functools import wraps


def memoize(func):
    cache = {}

    @wraps(func)
    def wrapper(*args, **kwargs):
        if args not in cache:
            print(f"Calling for {func.__name__}({args})")
            cache[args] = func(*args, **kwargs)
        else:
            print(f"Using cached result for {func.__name__}({args})")
        return cache[args]

    return wrapper


@memoize
def factorial(n):
    if n == 1:
        return n
    else:
        return n * factorial(n - 1)


if __name__ == '__main__':
    print(factorial(20))
    print(factorial(10))
    print(factorial(15))
    print(factorial(5))

Output

Calling for factorial((20,))
Calling for factorial((19,))
Calling for factorial((18,))
Calling for factorial((17,))
Calling for factorial((16,))
Calling for factorial((15,))
Calling for factorial((14,))
Calling for factorial((13,))
Calling for factorial((12,))
Calling for factorial((11,))
Calling for factorial((10,))
Calling for factorial((9,))
Calling for factorial((8,))
Calling for factorial((7,))
Calling for factorial((6,))
Calling for factorial((5,))
Calling for factorial((4,))
Calling for factorial((3,))
Calling for factorial((2,))
Calling for factorial((1,))
2432902008176640000
Using cached result for factorial((10,))
3628800
Using cached result for factorial((15,))
1307674368000
Using cached result for factorial((5,))
120

From the output, we can see that for computing the factorial of 10, 15 and 5, we used cached result.

In the next article, we will implement various kinds decorator recipes. Stay tuned for upcoming articles. Subscribe to the newsletter and Connect with me on twitter to get my future articles.

Interested in reading more such articles from Suresh Kumar?

Support the author by donating an amount of your choice.

No Comments Yet