Autocomplete: Trade-Offs and Wrap-Up
Autocomplete trade-offs are the choices this design made and what each choice costs. This lesson wraps up the design by weighing each choice against the ask from the first lesson.
Fresh versus stored
The stored answer and a live answer are built from different counts for the same prefix. The printout shows the two lists side by side, and they do not match.
stored = ["photo", "photos", "photo editor", "photo print", "photography"]
counts = {"photo": 7, "photos": 4, "photo booth": 6, "photo editor": 2, "photo print": 1, "photography": 1, "pizza": 3}
matches = [term for term in counts if term.startswith("ph")]
matches.sort(key=lambda term: (-counts[term], term))
live = matches[:5]
print("stored answer:", stored)
print("live answer:", live)
print("answers match:", stored == live)Work paid once or per keystroke
Three lookups are served both ways and the work is counted each way. The printout shows 18 term checks the live way against 3 stored reads the precomputed way.
counts = {"photo": 6, "photos": 3, "photo editor": 2, "photo print": 1, "photography": 1, "pizza": 3}
store = {"ph": ["photo", "photos", "photo editor", "photo print", "photography"], "pi": ["pizza"]}
lookups = ["ph", "pi", "ph"]
live_checks = 0
stored_reads = 0
for typed in lookups:
live_checks = live_checks + len(counts)
stored_reads = stored_reads + 1
print("term counts checked the live way:", live_checks)
print("stored lists read the precomputed way:", stored_reads)The hot spot cost
Search counts are totalled per shard for a fixed set of terms. The printout shows one shard taking most of the searches while the others stay quiet.
searches = {"sun": 40, "sand": 30, "sea": 20, "apple": 10, "avocado": 5, "plum": 8}
ranges = [("a-i", "a", "i"), ("j-r", "j", "r"), ("s-z", "s", "z")]
def shard_for(letter):
for name, low, high in ranges:
if low <= letter <= high:
return name
totals = {"a-i": 0, "j-r": 0, "s-z": 0}
for term in searches:
totals[shard_for(term[0])] = totals[shard_for(term[0])] + searches[term]
for name in ["a-i", "j-r", "s-z"]:
print(name, "takes", totals[name], "searches")Example
log = ["photo", "photos", "photo", "pizza", "photo editor", "photo", "photos", "photo print", "pizza", "photo", "photography", "photo", "photos", "pizza", "photo editor", "photo"]
def count_terms(entries):
counts = {}
for term in entries:
counts[term] = counts.get(term, 0) + 1
return counts
def build_store(counts):
store = {}
for prefix in ["ph", "pi"]:
matches = [term for term in counts if term.startswith(prefix)]
matches.sort(key=lambda term: (-counts[term], term))
store[prefix] = matches[:5]
return store
ranges = [("a-i", "a", "i"), ("j-r", "j", "r"), ("s-z", "s", "z")]
def shard_for(letter):
for name, low, high in ranges:
if low <= letter <= high:
return name
counts = count_terms(log)
store = build_store(counts)
typed = "ph"
print("typed:", typed)
print("shard visited:", shard_for(typed[0]))
print("answer:", store[typed])
print("stored lists built:", len(store))Key points
- Precompute or compute live: precomputing makes each answer one stored read, but the answer is only as fresh as the last rebuild.
- Cycle length: an hourly rebuild runs 24 times a day and stays fresher than a daily one, at more rebuilding work.
- Shard by first letter: lookups stay on one machine, but busy first letters make hot spots.
- Top 5 only: a short list keeps every answer small and fast, and it hides each term ranked below the fifth.
In this example, the whole design runs end to end: a log is counted, stored lists are built, and a typed prefix is routed to its shard for the answer. Each printed line is one stage of the design the earlier lessons built.
Note
every choice trades speed, freshness or storage against the others, and the ask decides which side wins.
Try it Yourself
Edit the code, then press Run.
Running is simulated
Exercise
Which choice makes answers fast but possibly stale?