Building a Universal Memoization Decorator with Python Dictionary Caching

Last update on April 10 2025 12:54:30 (UTC/GMT +8 hours)

82. Dictionary-based Memoization

Write a Python program to implement a memoization decorator that caches function results based on arguments. The decorator should handle any function with any number of positional and keyword arguments. Ensure that your implementation correctly handles unhashable arguments (like lists or dictionaries).

Solution:

Python Code:

# Define a decorator function to implement memoization for caching function results.
def memoize(func):
    """
    A decorator that caches function results based on arguments.
    Handles any function with any number of positional and keyword arguments.
    Converts unhashable arguments to hashable forms.
    
    Args:
        func: The function to memoize
        
    Returns:
        Wrapped function with memoization
    """
    # Initialize a dictionary to store cached results.
    cache = {}
    
    # Define a helper function to convert unhashable arguments into hashable forms.
    def make_hashable(arg):
        """Convert unhashable types to hashable representations."""
        # If the argument is a list or set, convert it to a tuple recursively.
        if isinstance(arg, (list, set)):
            return tuple(make_hashable(item) for item in arg)
        # If the argument is a dictionary, convert it to a sorted tuple of key-value pairs.
        elif isinstance(arg, dict):
            return tuple(sorted((k, make_hashable(v)) for k, v in arg.items()))
        # For all other types (e.g., integers, strings), return the argument as-is.
        else:
            return arg
    
    # Define the wrapper function that replaces the original function.
    def wrapper(*args, **kwargs):
        # Convert positional arguments into a hashable form using the `make_hashable` function.
        hashable_args = tuple(make_hashable(arg) for arg in args)
        # Convert keyword arguments into a sorted tuple of hashable key-value pairs.
        hashable_kwargs = tuple(sorted((k, make_hashable(v)) for k, v in kwargs.items()))
        # Combine hashable positional and keyword arguments into a single key.
        key = (hashable_args, hashable_kwargs)
        
        # Check if the result for the current arguments is already in the cache.
        if key not in cache:
            # If not cached, call the original function and store the result in the cache.
            cache[key] = func(*args, **kwargs)
        
        # Return the cached result.
        return cache[key]
    
    # Return the wrapper function, replacing the original function with the memoized version.
    return wrapper

 
# Example function to memoize - Fibonacci sequence calculation.
def fibonacci(n):
    # Base case: return n if n is 0 or 1.
    if n <= 1:
        return n
    # Recursive case: calculate Fibonacci(n-1) + Fibonacci(n-2).
    return fibonacci(n-1) + fibonacci(n-2)

# Example usage with memoization applied to the Fibonacci function.
@memoize
def fibonacci_memo(n):
    # Base case: return n if n is 0 or 1.
    if n <= 1:
        return n
    # Recursive case: calculate Fibonacci(n-1) + Fibonacci(n-2) with memoization.
    return fibonacci_memo(n-1) + fibonacci_memo(n-2)

# Test the performance of the Fibonacci function with and without memoization.
import time

# Without memoization (slow for larger values of n).
start = time.time()  # Record the start time.
result = fibonacci(30)  # Calculate Fibonacci(30) without memoization.
end = time.time()  # Record the end time.
# Print the result and the time taken.
print(f"Without memoization: {result}, Time: {end - start:.6f} seconds")

# With memoization (much faster due to caching).
start = time.time()  # Record the start time.
result = fibonacci_memo(30)  # Calculate Fibonacci(30) with memoization.
end = time.time()  # Record the end time.
# Print the result and the time taken.
print(f"With memoization: {result}, Time: {end - start:.6f} seconds")

Output:

Without memoization: 832040, Time: 0.164806 seconds
With memoization: 832040, Time: 0.000000 seconds

Explanation of Each Line:

Memoization Decorator : The memoize function is defined as a decorator to cache function results based on their arguments.
Cache Initialization : A dictionary cache is initialized to store previously computed results.
Hashable Conversion Helper : The make_hashable function converts unhashable types (like lists, sets, and dictionaries) into hashable forms (like tuples).
Wrapper Function : The wrapper function replaces the original function and handles caching logic.
Hashable Arguments : Converts positional arguments (args) into a hashable form using make_hashable.
Hashable Keyword Arguments : Converts keyword arguments (kwargs) into a sorted tuple of hashable key-value pairs.
Key Creation : Combines hashable positional and keyword arguments into a single key for the cache.
Cache Lookup : Checks if the result for the current arguments is already in the cache.
Cache Update : If the result is not cached, the original function is called, and the result is stored in the cache.
Return Cached Result : Returns the cached result for the given arguments.
Return Wrapper : The wrapper function replaces the original function with the memoized version.
Fibonacci Function : Defines a recursive Fibonacci function without memoization.
Memoized Fibonacci : Applies the memoize decorator to the Fibonacci function for caching.
Performance Testing : Tests the performance of the Fibonacci function with and without memoization using the time module.
Print Results : Prints the Fibonacci result and execution time for both cases to demonstrate the speed improvement with memoization.

Explanation - Dictionary-based Memoization

Concept: Implement a memoization decorator that caches function results based on input arguments.
Challenge: Handle any function signature and convert unhashable arguments to hashable forms.
Key Skills:

Decorator pattern implementation
Function argument handling
Type conversion for hashability
Dictionary-based caching

Applications:

Optimizing recursive functions (e.g., Fibonacci, factorial)
Speeding up expensive calculations
Implementing dynamic programming solutions
Caching API calls or database queries

Benefits:

Dramatically improves performance for repeated function calls
Reduces redundant calculations
Preserves function behavior while adding optimization

For more Practice: Solve these Related Problems:

Write a Python decorator that memoizes function calls but limits the cache to the last N results.
Write a Python function that memoizes results but automatically invalidates cache entries when a dependent file changes.
Write a Python memoization decorator that saves cache data to a file between executions.
Write a Python function that implements memoization while tracking how often each cached value is used.

Python Code Editor:

Previous: Nested Dictionary Manipulation.
Next: Custom Dictionary with Default Factory.