DEV Community

Cover image for Memoization decorator in python

Memoization decorator in python

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 optimisation 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))

Enter fullscreen mode Exit fullscreen mode

Output

2432902008176640000
3628800
1307674368000
120
Enter fullscreen mode Exit fullscreen mode

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))

Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)