{"id":19,"date":"2020-06-25T16:13:11","date_gmt":"2020-06-25T16:13:11","guid":{"rendered":"https:\/\/algocademy.com\/blog\/?p=19"},"modified":"2025-03-07T18:32:54","modified_gmt":"2025-03-07T18:32:54","slug":"how-to-apply-memoization-in-python-using-functools","status":"publish","type":"post","link":"https:\/\/algocademy.com\/blog\/how-to-apply-memoization-in-python-using-functools\/","title":{"rendered":"How to apply memoization in Python using functools"},"content":{"rendered":"

Memoization is a powerful optimization technique that can transform slow recursive functions into efficient algorithms by caching previously computed results. In this article, we’ll explore how to implement memoization in Python, focusing on the built-in tools from the functools<\/code> module.<\/p>\n

What is Memoization?<\/h2>\n

Memoization is an optimization technique where you store the results of expensive function calls and return the cached result when the same inputs occur again. This is particularly useful for recursive functions or functions with repeated calculations.<\/p>\n

The core concept behind memoization is simple:<\/p>\n

    \n
  1. Before executing a function, check if the result for the current input is already cached<\/li>\n
  2. If it is, return the cached result<\/li>\n
  3. If not, compute the result, store it in the cache, and then return it<\/li>\n<\/ol>\n

    This approach can drastically improve performance for functions with overlapping subproblems, reducing time complexity from exponential to polynomial or even linear in many cases.<\/p>\n

    The Classic Example: Fibonacci Sequence<\/h2>\n

    The Fibonacci sequence is the perfect example to demonstrate the power of memoization. Let’s start with the naive recursive implementation:<\/p>\n

    def fibonacci(n):\n    if n < 2:\n        return n\n    return fibonacci(n - 1) + fibonacci(n - 2)<\/code><\/pre>\n
    This implementation has a time complexity of O(2^n), making it extremely inefficient for larger values of n. The reason is that it recalculates the same values multiple times.<\/p>\n
    For example, calculating fibonacci(5)<\/code> involves:<\/p>\n
      \n
    • fibonacci(4) + fibonacci(3)<\/code><\/li>\n
    • fibonacci(3) + fibonacci(2) + fibonacci(2) + fibonacci(1)<\/code><\/li>\n
    • And so on…<\/li>\n<\/ul>\n
      Notice how fibonacci(3)<\/code> and fibonacci(2)<\/code> are calculated multiple times. This redundancy grows exponentially as n increases.<\/p>\n
      Manual Memoization Implementation<\/h2>\n
      Before diving into functools<\/code>, let’s implement memoization manually to understand the concept better:<\/p>\n
      def fibonacci_with_memo(n, cache={}):\n    if n < 2:\n        return n\n    \n    if n in cache:\n        return cache[n]\n        \n    cache[n] = fibonacci_with_memo(n - 1, cache) + fibonacci_with_memo(n - 2, cache)\n    return cache[n]<\/code><\/pre>\n
      With this implementation, we’ve reduced the time complexity to O(n) by storing each computed Fibonacci number in a dictionary and retrieving it when needed instead of recalculating.<\/p>\n
      However, there’s a potential issue with this implementation: using a mutable default argument (cache={}<\/code>) can lead to unexpected behavior if you’re not careful. The cache dictionary is created only once when the function is defined, not each time the function is called.<\/p>\n
      A safer implementation would be:<\/p>\n
      def fibonacci_with_memo(n, cache=None):\n    if cache is None:\n        cache = {}\n    \n    if n < 2:\n        return n\n    \n    if n in cache:\n        return cache[n]\n        \n    cache[n] = fibonacci_with_memo(n - 1, cache) + fibonacci_with_memo(n - 2, cache)\n    return cache[n]<\/code><\/pre>\n
      Using functools.lru_cache for Memoization<\/h2>\n
      While manual memoization works, Python’s functools<\/code> module provides a cleaner and more efficient solution with the lru_cache<\/code> decorator.<\/p>\n
      LRU stands for “Least Recently Used,” and lru_cache<\/code> is a decorator that wraps a function with a memoizing callable that saves up to the maxsize<\/code> most recent calls. It provides a perfect tool for memoization without having to manage the cache manually.<\/p>\n
      from functools import lru_cache\n\n@lru_cache(maxsize=None)\ndef fibonacci(n):\n    if n < 2:\n        return n\n    return fibonacci(n - 1) + fibonacci(n - 2)<\/code><\/pre>\n
      The maxsize=None<\/code> parameter means the cache can grow without bound. For most practical purposes, this is fine, but if you’re concerned about memory usage, you can set a specific maximum size.<\/p>\n
      Benefits of Using lru_cache<\/h3>\n
        \n
      1. Cleaner Code<\/strong>: No need to manually handle the cache<\/li>\n
      2. Thread Safety<\/strong>: The cache is thread-safe, making it suitable for multithreaded applications<\/li>\n
      3. Performance<\/strong>: Implemented in C, making it faster than a pure Python implementation<\/li>\n
      4. Cache Statistics<\/strong>: Provides statistics about cache performance<\/li>\n<\/ol>\n
        Checking Cache Statistics<\/h3>\n
        You can access cache statistics using the cache_info()<\/code> method:<\/p>\n
        fibonacci(30)\nprint(fibonacci.cache_info())<\/code><\/pre>\n
        This will output something like:<\/p>\n
        CacheInfo(hits=28, misses=31, maxsize=None, currsize=31)<\/code><\/pre>\n
        Here:<\/p>\n
          \n
        • hits<\/code> represents the number of times the cache was successfully used<\/li>\n
        • misses<\/code> is the number of times the cache was not used<\/li>\n
        • maxsize<\/code> is the maximum size of the cache<\/li>\n
        • currsize<\/code> is the current size of the cache<\/li>\n<\/ul>\n
          Clearing the Cache<\/h3>\n
          If you need to clear the cache, you can use the cache_clear()<\/code> method:<\/p>\n
          fibonacci.cache_clear()<\/code><\/pre>\n
          When to Use Memoization<\/h2>\n
          Memoization is particularly effective in the following scenarios:<\/p>\n
            \n
          1. Recursive Functions<\/strong>: When a recursive function repeatedly calculates the same values<\/li>\n
          2. Deterministic Functions<\/strong>: When the function output depends solely on its inputs<\/li>\n
          3. Pure Functions<\/strong>: Functions without side effects<\/li>\n
          4. Expensive Computations<\/strong>: When the function performs complex calculations<\/li>\n<\/ol>\n
            Practical Examples Beyond Fibonacci<\/h2>\n
            Let’s explore some other practical examples where memoization can be beneficial.<\/p>\n
            Example 1: Calculating Factorial<\/h3>\n
            from functools import lru_cache\n\n@lru_cache(maxsize=None)\ndef factorial(n):\n    if n == 0 or n == 1:\n        return 1\n    return n * factorial(n - 1)\n\n# Test with a large number\nprint(factorial(100))<\/code><\/pre>\n
            Example 2: Dynamic Programming – Coin Change Problem<\/h3>\n
            from functools import lru_cache\n\ndef coin_change(coins, amount):\n    @lru_cache(maxsize=None)\n    def dp(remaining):\n        if remaining == 0:\n            return 0\n        if remaining < 0:\n            return float('inf')\n            \n        min_coins = float('inf')\n        for coin in coins:\n            min_coins = min(min_coins, dp(remaining - coin) + 1)\n            \n        return min_coins\n    \n    result = dp(amount)\n    return result if result != float('inf') else -1\n\n# Example usage\ncoins = [1, 2, 5]\namount = 11\nprint(f\"Minimum coins needed: {coin_change(coins, amount)}\")<\/code><\/pre>\n
            Example 3: Memoizing a Function that Computes Prime Factors<\/h3>\n
            from functools import lru_cache\nimport math\n\n@lru_cache(maxsize=None)\ndef prime_factors(n):\n    factors = []\n    \n    # Check for division by 2\n    while n % 2 == 0:\n        factors.append(2)\n        n \/\/= 2\n    \n    # Check for division by odd numbers\n    for i in range(3, int(math.sqrt(n)) + 1, 2):\n        while n % i == 0:\n            factors.append(i)\n            n \/\/= i\n    \n    # If n is a prime number greater than 2\n    if n > 2:\n        factors.append(n)\n    \n    return tuple(factors)  # Using tuple because lists are not hashable\n\n# Test with several numbers\nfor num in [12, 15, 36, 49, 12, 15]:\n    print(f\"Prime factors of {num}: {prime_factors(num)}\")\n    \nprint(prime_factors.cache_info())<\/code><\/pre>\n
            Advanced Uses of lru_cache<\/h2>\n
            Setting a Maximum Cache Size<\/h3>\n
            If memory usage is a concern, you can limit the cache size:<\/p>\n
            @lru_cache(maxsize=128)\ndef expensive_function(param):\n    # Some expensive computation\n    return result<\/code><\/pre>\n
            When the cache reaches its maximum size, the least recently used entries are discarded to make room for new ones.<\/p>\n
            Typed Parameter Caching<\/h3>\n
            By default, lru_cache<\/code> considers function calls with the same arguments as cache hits, regardless of their types. If you want to treat calls with different types as distinct, you can use the typed<\/code> parameter:<\/p>\n
            @lru_cache(maxsize=None, typed=True)\ndef add(x, y):\n    return x + y\n\n# These will be cached separately\nadd(1, 2)      # int + int\nadd(1.0, 2.0)  # float + float\nadd(\"1\", \"2\")  # str + str<\/code><\/pre>\n
            Memoizing Methods in Classes<\/h3>\n
            When using lru_cache<\/code> with class methods, you need to be careful because self<\/code> is passed as an argument, and it might not be hashable. One solution is to use it with @staticmethod<\/code>:<\/p>\n
            class MathUtils:\n    @staticmethod\n    @lru_cache(maxsize=None)\n    def fibonacci(n):\n        if n < 2:\n            return n\n        return MathUtils.fibonacci(n - 1) + MathUtils.fibonacci(n - 2)<\/code><\/pre>\n
            For instance methods, you can use functools.cached_property<\/code> in Python 3.8+ or create a custom solution.<\/p>\n
            Alternatives to lru_cache in functools<\/h2>\n
            functools.cache (Python 3.9+)<\/h3>\n
            Python 3.9 introduced functools.cache<\/code>, which is a simpler version of lru_cache<\/code> with unlimited size:<\/p>\n
            from functools import cache\n\n@cache\ndef fibonacci(n):\n    if n < 2:\n        return n\n    return fibonacci(n - 1) + fibonacci(n - 2)<\/code><\/pre>\n
            This is equivalent to @lru_cache(maxsize=None)<\/code> but with a more straightforward name.<\/p>\n
            functools.cached_property (Python 3.8+)<\/h3>\n
            cached_property<\/code> is a decorator that transforms a method of a class into a property whose value is computed once and then cached as a normal attribute:<\/p>\n
            from functools import cached_property\n\nclass Circle:\n    def __init__(self, radius):\n        self.radius = radius\n        \n    @cached_property\n    def area(self):\n        print(\"Computing area...\")\n        return 3.14159 * self.radius * self.radius\n        \n# Usage\ncircle = Circle(5)\nprint(circle.area)  # Computes and caches\nprint(circle.area)  # Uses cached value<\/code><\/pre>\n
            Performance Comparison<\/h2>\n
            Let’s compare the performance of different implementations of the Fibonacci function:<\/p>\n
            import time\nimport functools\n\n# Naive recursive implementation\ndef fib_naive(n):\n    if n < 2:\n        return n\n    return fib_naive(n - 1) + fib_naive(n - 2)\n\n# Manual memoization\ndef fib_manual_memo(n, cache=None):\n    if cache is None:\n        cache = {}\n    if n < 2:\n        return n\n    if n in cache:\n        return cache[n]\n    cache[n] = fib_manual_memo(n - 1, cache) + fib_manual_memo(n - 2, cache)\n    return cache[n]\n\n# Using lru_cache\n@functools.lru_cache(maxsize=None)\ndef fib_lru_cache(n):\n    if n < 2:\n        return n\n    return fib_lru_cache(n - 1) + fib_lru_cache(n - 2)\n\n# Iterative solution (for comparison)\ndef fib_iterative(n):\n    if n < 2:\n        return n\n    a, b = 0, 1\n    for _ in range(2, n + 1):\n        a, b = b, a + b\n    return b\n\n# Test function\ndef test_performance(func, n, name):\n    start = time.time()\n    result = func(n)\n    end = time.time()\n    print(f\"{name} result for n={n}: {result}\")\n    print(f\"{name} time: {end - start:.6f} seconds\\n\")\n\n# Test with n=35\nn = 35\n\n# Clear cache before testing\nif hasattr(fib_lru_cache, \"cache_clear\"):\n    fib_lru_cache.cache_clear()\n\n# Run tests\ntest_performance(fib_lru_cache, n, \"lru_cache\")\ntest_performance(lambda x: fib_manual_memo(x), n, \"Manual memoization\")\ntest_performance(fib_iterative, n, \"Iterative\")\n\n# Naive is too slow for n=35, so test with smaller n\nsmaller_n = 20\ntest_performance(fib_naive, smaller_n, f\"Naive (n={smaller_n})\")<\/code><\/pre>\n
            The results will clearly show that both memoization approaches (manual and lru_cache<\/code>) perform significantly better than the naive recursive approach, with the iterative solution being the fastest but less intuitive for many recursive problems.<\/p>\n
            Common Pitfalls and How to Avoid Them<\/h2>\n
            1. Mutable Arguments<\/h3>\n
            lru_cache<\/code> requires function arguments to be hashable. This means you can’t use mutable types like lists or dictionaries as arguments:<\/p>\n
            @lru_cache(maxsize=None)\ndef process_list(lst):  # This will raise TypeError\n    return sum(lst)\n\n# Solution: Use immutable types like tuples\n@lru_cache(maxsize=None)\ndef process_list(lst_tuple):\n    return sum(lst_tuple)\n\n# Usage\nresult = process_list(tuple([1, 2, 3]))<\/code><\/pre>\n
            2. Functions with Side Effects<\/h3>\n
            Memoization assumes that a function always returns the same output for the same input. Functions with side effects or that depend on external state might not work correctly with memoization:<\/p>\n
            counter = 0\n\n@lru_cache(maxsize=None)\ndef increment_counter():\n    global counter\n    counter += 1\n    return counter\n\n# This will always return 1 after the first call!\nprint(increment_counter())  # 1\nprint(increment_counter())  # Still 1 due to caching<\/code><\/pre>\n
            3. Memory Usage<\/h3>\n
            With maxsize=None<\/code>, the cache can grow indefinitely. For functions called with many different arguments, this could lead to excessive memory usage:<\/p>\n
            # Limit cache size for functions with many potential inputs\n@lru_cache(maxsize=1024)\ndef expensive_function(n):\n    # Computation\n    return result<\/code><\/pre>\n
            4. Instance Methods<\/h3>\n
            When applying lru_cache<\/code> to instance methods, remember that self<\/code> is included in the cache key. If self<\/code> is not hashable, you’ll get an error:<\/p>\n
            class MyClass:\n    def __init__(self, value):\n        self.value = value\n    \n    # This might not work if MyClass is not hashable\n    @lru_cache(maxsize=None)\n    def compute(self, x):\n        return self.value * x<\/code><\/pre>\n
            Solution options:<\/p>\n
              \n
            • Make the class hashable by implementing __hash__<\/code> and __eq__<\/code><\/li>\n
            • Use cached_property<\/code> for properties<\/li>\n
            • Use staticmethod<\/code> if possible<\/li>\n<\/ul>\n
              Real-world Applications<\/h2>\n
              Web Development<\/h3>\n
              In web applications, memoization can be used to cache expensive database queries or API calls:<\/p>\n
              @lru_cache(maxsize=100)\ndef get_user_data(user_id):\n    # Simulate database query\n    print(f\"Fetching data for user {user_id} from database\")\n    return {\"id\": user_id, \"name\": f\"User {user_id}\"}\n\n# First call fetches from database\nprint(get_user_data(123))\n\n# Second call uses cached result\nprint(get_user_data(123))<\/code><\/pre>\n
              Data Analysis<\/h3>\n
              In data analysis pipelines, memoization can speed up repeated calculations:<\/p>\n
              import numpy as np\nfrom functools import lru_cache\n\n@lru_cache(maxsize=None)\ndef compute_statistics(data_tuple):\n    data = np.array(data_tuple)\n    print(\"Computing statistics...\")\n    return {\n        \"mean\": np.mean(data),\n        \"median\": np.median(data),\n        \"std\": np.std(data)\n    }\n\n# Convert list to tuple for hashability\ndata = tuple([1, 2, 3, 4, 5])\n\n# First call computes\nstats = compute_statistics(data)\nprint(stats)\n\n# Second call uses cache\nstats = compute_statistics(data)\nprint(stats)<\/code><\/pre>\n
              Machine Learning<\/h3>\n
              In machine learning, feature engineering often involves repetitive calculations that can benefit from memoization:<\/p>\n
              from functools import lru_cache\n\n@lru_cache(maxsize=1000)\ndef feature_transform(value):\n    # Expensive feature transformation\n    print(f\"Transforming {value}\")\n    return value ** 2 + 3 * value + 1\n\n# Process a dataset with potential duplicates\ndataset = [1, 2, 3, 1, 2, 4, 5, 1]\ntransformed = [feature_transform(x) for x in dataset]\nprint(transformed)\nprint(feature_transform.cache_info())<\/code><\/pre>\n
              Conclusion<\/h2>\n
              Memoization is a powerful technique that can significantly improve the performance of recursive functions and other computations with overlapping subproblems. Python’s functools<\/code> module provides elegant tools like lru_cache<\/code> that make implementing memoization simple and efficient.<\/p>\n
              Key takeaways:<\/p>\n
                \n
              • Use @lru_cache(maxsize=None)<\/code> for unlimited caching or specify a maximum size to limit memory usage<\/li>\n
              • Ensure function arguments are hashable<\/li>\n
              • Apply memoization to pure functions without side effects<\/li>\n
              • Consider performance vs. memory tradeoffs for your specific use case<\/li>\n
              • Explore newer alternatives like functools.cache<\/code> and functools.cached_property<\/code> in Python 3.9+ and 3.8+ respectively<\/li>\n<\/ul>\n
                By understanding and applying memoization effectively, you can write more efficient Python code that scales well with complex problems.<\/p>\n","protected":false},"excerpt":{"rendered":"
                Memoization is a powerful optimization technique that can transform slow recursive functions into efficient algorithms by caching previously computed results….<\/p>\n","protected":false},"author":1,"featured_media":1405,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[10,11,8,9,12,7],"class_list":["post-19","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-code","tag-algorithms","tag-dynamic-programming","tag-functools","tag-lru_cache","tag-memoization","tag-python"],"_links":{"self":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/19"}],"collection":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/comments?post=19"}],"version-history":[{"count":11,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/19\/revisions"}],"predecessor-version":[{"id":7766,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/19\/revisions\/7766"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media\/1405"}],"wp:attachment":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media?parent=19"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/categories?post=19"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/tags?post=19"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}