What is memoization and how can I use it in Python?

python

memoization

caching

functools

byAnton Shumikhin·Aug 16, 2024

Memoization is an optimization technique to speed up programs by storing the results of expensive function calls and reusing them when the same inputs occur. Python supports this natively through a decorator that uses a dictionary to store function results. Here's an example with the Fibonacci sequence:

def memoize(func):
    cache = {} # Where we'll store our results
    def wrapper(n):
        if n not in cache:
            cache[n] = func(n)
        return cache[n]
    return wrapper

@memoize
def fib(n):
    # Can you imagine doing this without memoization? #spooky
    return n if n <= 1 else fib(n-1) + fib(n-2)

print(fib(10))  # Rapid computation, even for big 'n'!

With the @memoize decorator, we cut down the fib(n) function calls significantly, making it speedier, even for large values of 'n'.

Built-in memoization with functools

Utilizing Python's built-in decorators, such as @functools.cache and @functools.lru_cache, grants us basic and advanced caching tools without needing to reinvent the wheel. Yes, Python thinks of everything!

from functools import cache

@cache
def factorial(n):
    # Recursive call with style!
    return n * factorial(n-1) if n else 1 

print(factorial(5))  # First call fills the cache, further calls use it

Implementing memoization with a classy touch

Sometimes, going custom is the way to go. If you need more control over your memoization process, consider implementing it in a class:

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

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

@Memoize
def compute(*args):
    # compute something really expensive
    pass

Surviving in the wild with memoization

Dealing with mutable types

Fresh out in the wild, you may encounter mutable types when using memoization. Have no fear, functools.wraps is here! Use it to keep the metadata of your memoized functions intact:

from functools import wraps

def memoize(func):
    cache = {}
    @wraps(func)
    def wrapper(*args):
        key = tuple([str(arg) for arg in args])
        if key not in cache:
            cache[key] = func(*args)
        return cache[key]
    return wrapper

Concurrency and memoization

In the world of concurrency, memoization can be a bit tricky. Use thread-safe structures or locks to avoid race conditions. No one wants a memory tug-of-war!

from functools import lru_cache
import threading

lock = threading.Lock()

@lru_cache(maxsize=None)
def thread_safe_func(*args):
    with lock:  # "Locking the door while I work. No entry!"
        # Perform thread-safe actions
        pass

Persisting beyond runtime

Memoization isn't limited to runtime. You can use a file system or database to store results for future runs. Now, that's persistence!

import shelve

def persistent_memoize(func):
    with shelve.open('memoize.db') as db:  # Our "external memory" storage
        def wrapper(*args):
            if args in db:
                return db[args]
            result = func(*args)
            db[args] = result
            return result
    return wrapper