Memoize with functools.cache

Batteries included is a blog series about the Python Standard Library. Each day, I share insights, ideas and examples for different parts of the library. Blaugust is an annual blogging festival in August where the goal is to write a blog post every day of the month.

A classic example of seemingly simple code that becomes very badly performing rather quickly is calculating factorials.

A factorial is a number that is the product of all positive integers that are smaller or equal to itself.

For example, factorial of 3 (marked as 3!) is 3 * 2 * 1 = 6. Factorial of 10 is already 3628800 which is to say that the result scales up real fast.

In Python, the factorial can be defined as

def factorial(n):
  if n == 0:
	  return 1
	else:
    return n * factorial(n-1)

We can improve its performance of multiple calls by memoizing or caching the previous results.

from functools import cache

@cache
def factorial(n):
  if n == 0:
	  return 1
	else:
    return n * factorial(n-1)
    
for n in range(10):
  print(factorial(n))

Now, for each call to factorial(n), the code will check if we already know the result for the current value of n and if we do, we don’t calculate it again but read it from cache.

This results to following executions to happen:

# n = 1
factorial(1) # = 1, let's store in cache
# n = 2
factorial(1) # found from cache, directly return 1
factorial(2) # = 2, let's store in cache
# n = 3
factorial(2) # found from cache, directly return 2
factorial(3) # = 6, let's store in cache

# and so on...

Now, when we reach the factorial(9), instead of calculating 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1, we calculate 9 * 40320 because 8! = 40320 and that’s already been calculated beforehand.

The arguments provided to the function must be hashable to be able to use cache. This means you cannot cache functions that take in lists or dictionaries for example.