Optimizing with Caching and Memoization

Caching and Memoization: The Core Idea

Before we dive into the code, let's clarify the concepts.

Caching is a general optimization technique where you store the results of an operation in a faster-to-access location (the "cache"). A web browser caching a webpage is a classic example; the next time you visit, the page loads from your local disk instead of being re-downloaded.

Memoization is a specific form of caching applied to functions. When you memoize a function, you store the results of its calls. If you call the function again with the same arguments, you get the stored result instantly instead of re-computing it.

To get a clear overview of these concepts, watch the first part of the following video.

When to Use Memoization: The Three Critical Rules

Memoization is not a magic bullet; applying it to the wrong function can have no effect or, worse, introduce bugs. A function is a good candidate for memoization if and only if it meets these three criteria:

1. Pure / Deterministic: The function must be a pure function. This means for the same set of inputs, it always returns the same output and has no side effects (like modifying a global variable, writing to a file, or calling print).

   • Good candidate: factorial(n)
   • Bad candidate: get_current_time() or a function that returns a random number.

2. Expensive: The function's computation must be costly enough that the overhead of checking the cache and storing the result is negligible in comparison. Memoizing a function that just adds two numbers is pointless.

   • Good candidate: A recursive Fibonacci function, a complex regex compilation, or a call to a slow network service.
   • Bad candidate: is_even(n)

3. Called Repeatedly with the Same Arguments: The function must be likely to be called multiple times with the same inputs. There's no benefit in caching a result that you'll never need again.

This next segment of the video you just watched explains these three properties perfectly.

Implementing Memoization with functools.lru_cache

While you could implement memoization manually using a dictionary, this approach is error-prone (especially with the mutable default argument bug). Python's "batteries included" philosophy provides a robust, production-ready solution: the @lru_cache decorator.

LRU stands for "Least Recently Used". It's a caching strategy that discards the least recently used items first when the cache is full.

Let's see it in action with the classic example: a recursive Fibonacci function. This function is a perfect candidate for memoization because it is pure, expensive (O(2ⁿ)), and involves many overlapping subproblems (repeated calls).

# fibonacci_slow.py
import timeit

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




# This will take a noticeable amount of time
print("Calculating fibonacci(35)...")
time_taken = timeit.timeit("fibonacci(35)", globals=globals(), number=1)
print(f"Result: {fibonacci(35)}")
print(f"Time taken: {time_taken:.4f} seconds")

Now, let's apply @lru_cache.

# fibonacci_fast.py
import timeit
from functools import lru_cache

@lru_cache(maxsize=None) # maxsize=None means the cache can grow without bound
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print("Calculating fibonacci(35) with cache...")
time_taken = timeit.timeit("fibonacci(35)", globals=globals(), number=1)
print(f"Result: {fibonacci(35)}")
print(f"Time taken: {time_taken:.4f} seconds")

Running these two scripts demonstrates a staggering performance improvement, from several seconds to microseconds. The decorator transparently intercepts calls to fibonacci, stores the result for each n, and on subsequent calls for the same n, returns the stored value instead of descending into recursion.

This next video uses the same Fibonacci example to showcase the "massive power" of lru_cache.

Fine-Tuning and Inspecting the Cache

@lru_cache is more than just a simple on/off switch. You can control its behavior and inspect its state, which is vital for production systems.

• maxsize: This argument controls the cache size. The default is 128. If the cache exceeds this size, the least recently used item is discarded. Set maxsize=None for an unlimited cache, but be mindful of memory consumption. In Python 3.9+, you can use the simpler @functools.cache, which is equivalent to @lru_cache(maxsize=None).
• typed: If set to True, arguments of different types will be cached separately. For example, f(3) and f(3.0) would be treated as two distinct calls. The default is False.
• .cache_info(): A method on the decorated function that returns a named tuple with cache statistics: hits, misses, maxsize, and currsize. This is invaluable for understanding if your cache is effective.
• .cache_clear(): Clears the cache entirely. This is useful in tests or when you know the underlying data has changed.

This video segment will walk you through these practical features.

Common Pitfalls and Best Practices

To use memoization safely and effectively, you must be aware of its limitations. Given your goal of writing robust, production-ready code, these points are critical.

Let's summarize the most crucial pitfall: function arguments must be hashable.

The @lru_cache decorator uses the function's arguments to create a key for its internal dictionary cache. Dictionary keys must be hashable. This means you cannot pass mutable objects like lists, dictionaries, or sets directly to a cached function.

from functools import lru_cache

@lru_cache(maxsize=None)
def process_data(data_list): # This will fail!
    print("Processing...")
    return sum(data_list)




# ❌ This will raise a TypeError: unhashable type: 'list'
# process_data([1, 2, 3])




# ✅ The solution is to convert mutable arguments to their immutable counterparts.
@lru_cache(maxsize=None)
def process_data_fixed(data_tuple):
    print("Processing...")
    return sum(data_tuple)




# This works because tuples are hashable.
process_data_fixed(tuple([1, 2, 3])) # First call, prints "Processing..."
process_data_fixed(tuple([1, 2, 3])) # Second call, returns from cache instantly.

Exercise: Apply and Measure Memoization

You are given a function that simulates a slow, external API call to fetch weather data for a city. The function has an artificial delay to represent network latency. Your script repeatedly asks for forecasts for a few cities.

Your task is to optimize this script using memoization.

Starter Script:

# weather_optimizer.py
import time
import timeit

def fetch_weather_data(city: str) -> dict:
    """
    Simulates a slow API call to fetch weather data.
    This function is PURE and EXPENSIVE.
    """
    print(f"--- Fetching weather data for {city} from the API... ---")



    # Artificial delay to simulate network latency
    time.sleep(1)
    if city == "New York":
        return {"city": "New York", "temperature": "15°C", "condition": "Cloudy"}
    elif city == "London":
        return {"city": "London", "temperature": "12°C", "condition": "Rainy"}
    elif city == "Tokyo":
        return {"city": "Tokyo", "temperature": "22°C", "condition": "Sunny"}
    else:
        return {"city": city, "error": "City not found"}

def run_forecasts():
    """Simulates a user requesting forecasts for a list of cities."""
    cities = ["New York", "London", "Tokyo", "New York", "London", "London"]
    for city in cities:
        data = fetch_weather_data(city)
        print(f"Forecast for {data['city']}: {data.get('condition', 'N/A')}")

if __name__ == "__main__":



    # Measure the unoptimized version
    time_taken = timeit.timeit("run_forecasts()", globals=globals(), number=1)
    print(f"\nTotal time taken (uncached): {time_taken:.4f} seconds")




    # Your task is to create and measure an optimized version below.

Your Tasks:

1. Copy the code into a new Python file.
2. Apply @lru_cache: Import lru_cache from functools and apply it as a decorator to the fetch_weather_data function. Since we are dealing with a small number of cities, an unbounded cache (maxsize=None) is fine.
3. Run and Observe: Run the script. Notice that even though run_forecasts calls fetch_weather_data six times, the "Fetching..." message only appears three times. The subsequent calls for "New York" and "London" are served from the cache. The total time taken should drop from ~6 seconds to ~3 seconds.
4. Inspect the Cache (Bonus): After the run_forecasts call, add a line to print the cache info: print(fetch_weather_data.cache_info()). Analyze the output. You should see hits=3, misses=3, and currsize=3.

Conclusion

You have now added memoization, a powerful optimization technique, to your toolkit. It is the perfect solution when you identify a performance bottleneck in a function that is pure, expensive, and frequently called with the same arguments.

Key Takeaways:

• Memoization is a form of caching that stores function call results to avoid re-computation, trading memory for speed.
• functools.lru_cache is the idiomatic Python tool for memoization.
• Only memoize functions that are pure (deterministic), computationally expensive, and called repeatedly with the same inputs.
• Be aware of the pitfalls: function arguments must be hashable, and memoizing functions with side effects leads to bugs.
• Use .cache_info() to inspect and validate the effectiveness of your cache.

What's Next?

We've focused on optimizing CPU-bound tasks, either by improving algorithms or by caching their results. However, performance is not just about CPU speed; it's also about memory. In our next lesson, we will shift our focus to memory considerations. You will learn how to write memory-efficient code by replacing in-memory lists with generator-based streaming pipelines, a crucial skill for processing large datasets without running out of memory.