Dict-based cache

Build a cache with a dictionary.

Dictionary-based cache

Memoization's cache is implemented as a dictionary. The key is the parameter, the value is the result.

A dictionary gives average O(1) access; this is why memoization is efficient.

A tuple parameter can be a dictionary key; this suits multi-dimensional subproblems.

First computation

On the first call the computation runs and the result is written to the dictionary. Later calls read directly.

This makes even complex recursions efficient.

The first computation's cost is paid once; later calls are cheap.

Exercise Memoized factorial

Write fact_memo(n, memo). Recursive factorial with memoization. Print 120 with print(fact_memo(5, {})).

Show example solution

def fact_memo(n, memo):
    # Memoized factorial
    if n in memo:
        return memo[n]
    if n <= 1:
        return 1
    memo[n] = n * fact_memo(n - 1, memo)
    return memo[n]
print(fact_memo(5, {}))

Test yourself

Dict-based cache: match the terms

dict

Dictionary
key

Parameter
value

Result
O(1)

Fast
What does the dictionary key represent?
- Subproblem parameter
- Result
- Time
- Memory
Show answer

Subproblem parameter — Subproblem parameter.
Dict write
```
memo[____] = result
```
Show answer
```
memo[n] = result
```

Next lesson: Summary - Memoization

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies