Skip to content
CodeMDD.io | Coding Tutorials

Effortlessly Implement LRU Cache in Python

[

Caching in Python Using the LRU Cache Strategy

There are many ways to achieve fast and responsive applications. Caching is one approach that, when used correctly, makes things much faster while decreasing the load on computing resources. Python’s functools module comes with the @lru_cache decorator, which gives you the ability to cache the result of your functions using the Least Recently Used (LRU) strategy. This is a simple yet powerful technique that you can use to leverage the power of caching in your code.

Caching and Its Uses

Caching is an optimization technique that you can use in your applications to keep recent or often-used data in memory locations that are faster or computationally cheaper to access than their source.

Imagine you’re building a newsreader application that fetches the latest news from different sources. As the user navigates through the list, your application downloads the articles and displays them on the screen.

What would happen if the user decided to move repeatedly back and forth between a couple of news articles? Unless you were caching the data, your application would have to fetch the same content every time! That would make your user’s system sluggish and put extra pressure on the server hosting the articles.

A better approach would be to store the content locally after fetching each article. Then, the next time the user decided to open an article, your application could open the content from a locally stored copy instead of going back to the source. In computer science, this technique is called caching.

Implementing a Cache Using a Python Dictionary

You can implement a caching solution in Python using a dictionary.

Staying with the newsreader example, instead of going directly to the server every time you need to download an article, you can check whether you have the content in your cache and go back to the server only if you don’t. You can use the article’s URL as the key in the dictionary and the content as the corresponding value.

Here’s a code snippet that demonstrates this concept:

article_cache = {}


def fetch_article(url):
    if url in article_cache:
        return article_cache[url]
    else:
        article = download_article(url)
        article_cache[url] = article
        return article

In this example, the fetch_article function checks if the requested URL is present in the cache dictionary. If it is, it returns the cached article; otherwise, it downloads the article from the server, caches it in the dictionary, and then returns it.

This simple caching mechanism can significantly improve the performance of your application by avoiding unnecessary network requests.

Caching Strategies

While using a dictionary-based cache can be effective for small-scale applications, it may not be the best solution for large or complex systems. In such cases, you need more sophisticated caching strategies that can manage the cache more efficiently.

One such strategy is the Least Recently Used (LRU) cache. The LRU cache keeps track of the order in which items are accessed and evicts the least recently used items when the cache reaches its maximum capacity.

Diving Into the Least Recently Used (LRU) Cache Strategy

The LRU cache strategy is based on the principle that items that have been accessed recently are more likely to be accessed again in the near future. By evicting the least recently used items from the cache, you make room for new items that are more likely to be accessed soon.

To implement an LRU cache, you can use the functools.lru_cache decorator provided by Python’s functools module. This decorator takes care of all the bookkeeping required for keeping track of the most recently used items and evicting the least recently used ones.

Here’s an example that demonstrates how to use the @lru_cache decorator:

from functools import lru_cache


@lru_cache(maxsize=128)
def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

In this example, the fibonacci function calculates the nth Fibonacci number recursively. By decorating it with @lru_cache(maxsize=128), we enable caching for this function. The maxsize parameter specifies the maximum number of values to be cached. Once the cache reaches this size, the least recently used items will be automatically evicted to make room for new ones.

Now, every time the fibonacci function is called with the same argument, the cached result will be returned instead of recomputing it.

Using @lru_cache to Implement an LRU Cache in Python

Now that we understand the LRU cache strategy, let’s see how we can use the @lru_cache decorator to implement an LRU cache in Python.

Playing With Stairs

Consider a scenario where you have a function that calculates the number of different ways to climb a staircase with a given number of steps. Each time, you can either climb one step or two steps. This is a typical problem that can be solved using dynamic programming.

Here’s the recursive implementation of the staircase climbing function:

@lru_cache(maxsize=None)
def climb_stairs(n):
    if n == 0 or n == 1:
        return 1
    else:
        return climb_stairs(n-1) + climb_stairs(n-2)

By decorating the climb_stairs function with @lru_cache(maxsize=None), we enable caching for this function with an unlimited cache size. Now, every time the climb_stairs function is called with the same argument, the cached result will be returned instead of recomputing it. This significantly improves the performance of the function.

Timing Your Code

To see the impact of caching on the performance of your code, let’s compare the execution time of the climb_stairs function with and without caching.

Here’s how you can time your code using the timeit module:

import timeit


# Without caching
normal_time = timeit.timeit(lambda: climb_stairs(30), number=1000)


# With caching
cached_time = timeit.timeit(lambda: climb_stairs(30), number=1000)


print(f"Without caching: {normal_time}")
print(f"With caching: {cached_time}")

By calling the timeit.timeit function with your code inside a lambda function, you can measure the execution time of the code. The number parameter specifies the number of times the code should be executed.

Using Memoization to Improve the Solution

Using memoization, you can further improve the solution for the staircase climbing problem. Memoization is a technique that involves storing the results of expensive function calls and returning the cached result when the same inputs occur again.

Here’s an updated version of the climb_stairs function with memoization:

@lru_cache(maxsize=None)
def climb_stairs(n):
    memo = {}


    def helper(n):
        if n == 0 or n == 1:
            return 1
        elif n in memo:
            return memo[n]
        else:
            memo[n] = helper(n-1) + helper(n-2)
            return memo[n]


    return helper(n)

In this version, we introduce a memo dictionary to store the results of function calls. If the desired result is already present in the memo dictionary, we can simply return it instead of recomputing it. Otherwise, we calculate the result recursively and store it in the memo dictionary for future use.

Using memoization not only improves the performance of the function but also reduces redundant calculations.

Unpacking the Functionality of @lru_cache

Now that you have a good understanding of how to use the @lru_cache decorator, let’s unpack its functionality and see what’s happening behind the scenes.

The @lru_cache decorator creates a cache object that is added to the function being decorated. This cache object has a cache_info method that provides information about the cache, such as the number of hits, misses, and the cache size.

Here’s an example that demonstrates how to use the cache_info method:

fibonacci.cache_info()

This will return a named tuple with the following attributes:

  • hits: The number of times a cached value was returned
  • misses: The number of times a value was computed and added to the cache
  • maxsize: The maximum number of values that the cache can store
  • currsize: The current number of values stored in the cache

By inspecting the information provided by the cache_info method, you can gain insights into the caching behavior of your code and make informed decisions on cache size and efficiency.

Adding Cache Expiration

In some cases, you may want to expire the entries in your cache after a certain period of time or when the cache reaches a certain size.

Evicting Cache Entries Based on Both Time and Space

You can use the functools.lru_cache decorator with the typed=True parameter to create a cache that evicts entries based on both time and space.

Here’s an example that demonstrates how to create a cache with expiration:

from functools import lru_cache


@lru_cache(maxsize=128, typed=True)
def expensive_function(arg1, arg2):
    return compute_expensive_result(arg1, arg2)

In this example, the cache will store up to 128 entries based on the argument values. The entries in the cache will be expired after a certain period of time or when the cache reaches its maximum size, whichever comes first.

Caching Articles With the New Decorator

Let’s consider a scenario where you have a function that fetches articles from a web server and caches them for a limited time to reduce the load on the server.

Here’s an example that demonstrates how to implement article caching with cache expiration:

from functools import lru_cache
import requests


@lru_cache(maxsize=128, typed=True)
def fetch_article(url):
    response = requests.get(url)
    article = response.text
    return article

In this example, the fetch_article function fetches the article from the web server using the provided URL. The @lru_cache decorator ensures that the fetched articles are cached, and the cache entries will expire after a certain period of time or when the cache reaches its maximum size.

By caching the articles, you can reduce the load on the web server and improve the responsiveness of your application.

Conclusion

Caching is a powerful technique that can significantly improve the performance of your Python applications. Python’s functools module provides the @lru_cache decorator, which allows you to easily implement caching with the LRU cache strategy.

In this tutorial, you learned about caching strategies, the LRU cache strategy, and how to implement an LRU cache in Python using the @lru_cache decorator. You also learned how to add cache expiration to your cache and how to use memoization to further optimize your code.

By leveraging caching in your applications, you can achieve faster and more efficient code execution, resulting in a better user experience and reduced resource consumption.

Remember to use caching judiciously and consider the specific needs of your application when deciding on cache size and expiration policies.