Memoization in Python

Memoization is a technique used in computer science to speed up the execution time of programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. This technique is particularly useful for functions that are computationally expensive and have a high likelihood of being called with the same inputs multiple times. In Python, memoization can be implemented using various techniques, including decorators, classes, and function attributes.

Implementing Memoization using Decorators

One of the simplest ways to implement memoization in Python is by using decorators. A decorator is a function that takes another function as input, modifies it, and returns the modified function. By using a decorator, we can wrap our original function in a caching mechanism that stores the results of previous calls and returns them when the same inputs occur again.

import functools

def memoize(func):
    cache = {}

    @functools.wraps(func)
    def memoized_func(*args):
        if args in cache:
            return cache[args]
        result = func(*args)
        cache[args] = result
        return result

    return memoized_func

@memoize
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10))  # 55

Implementing Memoization using Classes

Another way to implement memoization in Python is by using classes. In this approach, we create a memoization class that takes a function as input, stores the cache, and returns the cached result when the same inputs occur again.

class Memoize:
    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        if args in self.cache:
            return self.cache[args]
        result = self.func(*args)
        self.cache[args] = result
        return result

@Memoize
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10))  # 55

Conclusion

Memoization is a powerful technique for optimizing the execution time of programs by caching the results of expensive function calls. In Python, memoization can be implemented using various techniques, including decorators, classes, and function attributes. By using memoization, you can significantly speed up the execution time of your programs, particularly for functions that are computationally expensive and have a high likelihood of being called with the same inputs multiple times.