Memoization with Dicts
Concepts covered: functools
In a batch, the same calls repeat with the same arguments: the rate for "eur" on every euro payment, the region for store 118 on every sale from that store. When a function's result depends only on its arguments, the first answer stays the answer, and computing it again is wasted work. Memoization stores each answer in a dict keyed by the arguments and returns the stored value on every later call.
The pattern takes 3 lines inside the function. If the key is missing from the cache, compute the value and store it; either way, return what the cache holds. In the program below, slow_rate stands in for an expensive lookup and counts how often it runs.
calls = 0
def slow_rate(currency):
global calls
calls += 1
table = {"eur": 108, "gbp": 127, "usd": 100}
return table[currency]
rate_cache = {}
def cached_rate(currency):
if currency not in rate_cache:
rate_cache[currency] = slow_rate(currency)
return rate_cache[currency]
events = ["eur", "usd", "eur", "eur", "gbp", "usd", "eur", "usd"]
for currency in events:
cached_rate(currency)
print("slow lookups:", calls)
print("cache:", rate_cache)
slow lookups: 3
cache: {'eur': 108, 'usd': 100, 'gbp': 127}
slow_rate ran 3 times for 8 events, once per distinct currency. The cache lives at module level, outside both functions, so it outlasts every call. cached_rate changes the dict's contents without rebinding the name rate_cache, so it needs no global statement; slow_rate needs one because calls += 1 rebinds calls.
The key must hold every input
A cache is correct only when its key captures everything the result depends on. If a rate depends on the currency and the day, a cache keyed by currency alone hands back day 1's rate for every later day. A tuple of the arguments covers both, and tuples work as dict keys because they can't change after they're created. A list can't be a key: cache[["eur", 2]] raises TypeError: unhashable type: 'list'.
table = {("eur", 1): 108, ("eur", 2): 110}
bad_cache = {}
def rate_bad(currency, day):
if currency not in bad_cache:
bad_cache[currency] = table[(currency, day)]
return bad_cache[currency]
good_cache = {}
def rate_good(currency, day):
key = (currency, day)
if key not in good_cache:
good_cache[key] = table[key]
return good_cache[key]
print(rate_bad("eur", 1), rate_bad("eur", 2))
print(rate_good("eur", 1), rate_good("eur", 2))Output:
108 108 108 110
rate_bad("eur", 2) returns 108 because the key "eur" was already stored on day 1. rate_good stores ("eur", 1) and ("eur", 2) as separate keys and returns each day's own rate.
Before you add a cache
The pattern also handles failures correctly. If the expensive call raises, the line that stores into the cache never finishes, so nothing is stored and the next call with that key tries again. A lookup that failed on bad input is never remembered as an answer.
Where the dict is created decides whether the cache works at all. A cache = {} line inside the function runs on every call, so each call starts with an empty dict, the in check always fails, and no lookup is ever saved.
What does this program print?
calls = 0
def fetch_region(store_id):
global calls
cache = {}
if store_id not in cache:
calls += 1
cache[store_id] = "eu-west"
return cache[store_id]
for _ in range(4):
fetch_region(118)
print(calls)- 1: the region for store 118 is stored on the first call and reused
- 4: cache = {} runs on every call, so each call starts empty
- 0: calls inside the function is a separate local variable
- 4: a dict cannot use an integer like 118 as a key, so nothing is stored
About this lesson
This section is part of the Functions: Advanced lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.