Memoization Without functools

Learn how to implement memoization in Python without using functools. Speed up your recursive functions with custom caching for better performance.

Memoization in Python Without Using functools

Memoization is a powerful optimization technique that stores the results of expensive function calls and reuses them when the same inputs occur again. While Python’s functools.lru_cache provides a built-in way to do this, you can also implement memoization manually. This is especially useful when you need full control over the caching mechanism or want to avoid using external libraries.

What is Memoization?

Memoization reduces the time complexity of recursive functions by caching results of previous calls. For instance, in a naive recursive Fibonacci implementation, repeated calculations of the same subproblems slow down performance dramatically. Memoization stores these results so that subsequent calls are fast.

Manual Memoization Using a Dictionary

The simplest way to implement memoization manually in Python is by using a dictionary to store computed results. Here’s an example of a memoized Fibonacci function:

def fibonacci(n, cache=):
    if n in cache:
        return cache[n]
    if n <= 1:
        cache[n] = n
    else:
        cache[n] = fibonacci(n-1, cache) + fibonacci(n-2, cache)
    return cache[n]

This approach checks if a value is already in the cache before computing it. If not, it computes the value and stores it for later use.

Why Avoid functools?

You might prefer manual memoization when you need custom logic, such as limiting the size of your cache, persisting it across program runs, or controlling cache invalidation rules. Manual caching is also useful in environments where third-party modules are restricted.

Testing the Memoized Function

Let’s compute the 35th Fibonacci number. Without memoization, this would take a noticeable amount of time. With caching, it finishes instantly after the first computation:

print(fibonacci(35))  # 9227465

Conclusion

Manual memoization gives you flexibility and control over your caching strategy. For small projects or specific use cases, this approach avoids unnecessary dependencies and provides significant performance gains.

Subscribe to Our YouTube for More

Download as PDF

https://blog.arashtad.com/updates/memoization-without-functools/?feed_id=12699&_unique_id=688bc8d79e8ba