🎓 A1Learner
🔍
0 of 42 lessons completed

Precomputed Suggestions

Precomputation is working out an answer before anyone asks, then storing it ready to serve. This lesson designs the data model: past searches are counted, and the top 5 suggestions for each popular prefix are stored ahead of time.

Counting past searches

The demo counts a fixed log of past searches into a table. Each term appears once in the printout, with its total count beside it.

log = ["photo", "photos", "photo", "pizza", "photo editor", "photo", "photos", "photo print", "pizza", "photo", "photography", "photo", "photos", "pizza", "photo editor", "photo"]
counts = {}
for term in log:
    counts[term] = counts.get(term, 0) + 1
for term in sorted(counts):
    print(term, counts[term])
print("searches counted:", len(log))

Storing the top 5 per prefix

For each popular prefix, the counted terms that start with it are sorted by count. The printout shows the stored list for each prefix, highest count first.

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

counts = count_terms(log)
store = build_store(counts)
for prefix in sorted(store):
    print(prefix, "->", store[prefix])

One stored list per lookup

A lookup reads a single stored list instead of checking all 6 counted terms. The printout shows the answer, the lists touched and the terms a live scan would check.

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

counts = count_terms(log)
store = build_store(counts)
typed = "ph"
touched = 0
answer = store[typed]
touched = touched + 1
print("answer for " + typed + ":", answer)
print("stored lists touched:", touched)
print("counted terms a live scan would check:", len(counts))

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

counts = count_terms(log)
store = {}
for term in counts:
    for i in range(1, len(term) + 1):
        prefix = term[:i]
        matches = [t for t in counts if t.startswith(prefix)]
        matches.sort(key=lambda t: (-counts[t], t))
        store[prefix] = matches[:5]
print("stored lists:", len(store))
print("pho ->", store["pho"])
print("p ->", store["p"])

Key points

  • Precomputation: working out an answer before it is asked and storing it ready.
  • Search log: the record of finished searches that the counts are built from.
  • Count table: the number of past searches for each term, counted from the log.
  • Stored list: the top 5 terms for one prefix, kept as a single ready answer.
  • Lookup: serving reads the one stored list for the typed prefix and checks nothing else.

In this example, the log is counted first, then the top 5 terms are stored for every prefix of every counted term. The build makes 28 stored lists, and each typed prefix after that reads exactly one list.

Note

the counting and sorting work happens once per build, not once per keystroke.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

Why does the service precompute the suggestion lists?