Dict-based cache
- Algorithms course
- Advanced
- Lesson 3/56
- 4 min
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.
Practice Memoized factorial
Write fact_memo(n, memo). Recursive factorial with memoization. Print 120 with print(fact_memo(5, {})).
Starter code
def fact_memo(n, memo):
# Memoized factorialSample 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, {}))Expected output
120
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Dict-based cache: match the terms
| Term | Meaning |
|---|---|
dict |
Dictionary |
key |
Parameter |
value |
Result |
O(1) |
Fast |
2 What does the dictionary key represent?
- Subproblem parameter Correct answer
- Result
- Time
- Memory
Explanation: Subproblem parameter.
3 Dict write
memo[____] = resultmemo[n] = resultExplanation: n is right.