Optimizing Python Code with LRU Cache: A Fibonacci Sequence Example

LRU Cache is a powerful feature in Python that can help optimize the performance of code that involves frequent function calls. LRU stands for “Least Recently Used”, and it is a type of cache that stores the results of recently called functions. It is particularly useful in situations where the same function is called repeatedly with the same arguments, as it can significantly reduce the number of function calls required.

One classic example of a problem that benefits from LRU caching is the Fibonacci sequence. The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding numbers, starting from 0 and 1. The sequence can be defined recursively as follows:

While this implementation is simple and easy to understand, it can quickly become inefficient as the size of n grows. This is because the function calls itself twice for every recursive call, resulting in an exponential increase in the number of function calls. For example, calling fib(6) would result in the following function calls:

As you can see, the function is called multiple times with the same arguments, resulting in redundant calculations. This is where LRU caching comes in handy.

Python’s functools module provides a built-in decorator lru_cache that can be used to cache the results of a function. Here’s how we can use it to optimize the Fibonacci sequence:

By adding the @lru_cache decorator to the function, we tell Python to cache the results of previous function calls. The maxsize argument sets the maximum number of function calls that can be stored in the cache. Setting it to None means that the cache can store an unlimited number of function calls.

Let’s now test our optimized implementation of the Fibonacci sequence by calling fib(6) again:

As you can see, the number of function calls has been significantly reduced, and the function only calculates each value once. This makes our implementation much more efficient and faster, especially for larger values of n.

In this post we learned that LRU caching is a powerful optimization technique that can significantly improve the performance of Python code that involves frequent function calls. By using the @lru_cache decorator, we can easily implement caching in our code and reduce the number of redundant function calls. The Fibonacci sequence is just one example of a problem that can benefit from LRU caching, but there are many other use cases where caching can make a big difference in performance.

Reference

[1] Fluent Python