Kiru Lab / Foundations: Python as an Instrument / Python From First Principles
The Four Data Structures That Matter
Lists, dicts, sets, and tuples — chosen by access pattern, not by habit.
Concept · about 25 minutes
Choosing a data structure is choosing which operations will be cheap. That is the entire decision. A list makes ordered iteration and indexing cheap and membership testing expensive. A dict makes lookup by key cheap. A set makes membership and deduplication cheap and ordering nonexistent. A tuple makes a fixed-size record that can safely be used as a dict key.
tokens = ["the", "model", "the", "weights", "the"]
# O(n) per lookup — fine for five items, disastrous for five million
unique_slow = []
for t in tokens:
if t not in unique_slow:
unique_slow.append(t)
# O(1) average per lookup
unique_fast = set(tokens)
# Counting, which is what a tokenizer actually needs
from collections import Counter
counts = Counter(tokens) # {"the": 3, "model": 1, "weights": 1}Comprehensions
A comprehension is a loop that builds a collection, written as a single expression. Used well it is clearer than the loop; used badly it is a puzzle. The rule of thumb: if you would need a comment to explain it, write the loop.
squares = [x * x for x in range(10)]
long_tokens = [t for t in tokens if len(t) > 3]
lookup = {token: index for index, token in enumerate(sorted(set(tokens)))}That last line is a vocabulary — a mapping from token string to integer id. You will build exactly this in the language-models track, at a scale of fifty thousand entries instead of three.
Hold on to
- Pick a structure by which operation you need to be cheap
- Membership testing in a list is linear; in a set it is constant
- A token-to-id vocabulary is just a dict comprehension at scale
Work through
Try each one before opening the solution. Getting it wrong first is most of where the learning happens.
-
Time list-membership versus set-membership on 100,000 items. Report the ratio.
Hint
Use `time.perf_counter()` around each lookup loop.
Solution
The set is typically hundreds to thousands of times faster, and the gap widens with size because list membership is O(n) while set membership is O(1) on average. The absolute numbers vary by machine; the scaling behavior does not.
import time n = 100_000 items_list = list(range(n)) items_set = set(items_list) targets = [n - 1, n // 2, -1] for name, container in (("list", items_list), ("set", items_set)): start = time.perf_counter() for t in targets * 100: t in container print(name, f"{time.perf_counter() - start:.4f}s") -
Build a token vocabulary from a paragraph of text, then write the inverse mapping (id back to token) and verify a round trip.
Hint
Build the forward mapping with a dict comprehension, then invert it.
Solution
Sort the unique tokens before assigning ids so the vocabulary is deterministic — iterating a set directly gives an order that can vary between runs, which quietly breaks reproducibility. That is the seeds lesson arriving early.
text = "the model learns the map the data implies" tokens = text.split() vocab = {token: i for i, token in enumerate(sorted(set(tokens)))} inverse = {i: token for token, i in vocab.items()} ids = [vocab[t] for t in tokens] recovered = [inverse[i] for i in ids]Check your work
Paste this after your own code. If it runs without raising, you have it.
assert recovered == tokens assert len(vocab) == len(inverse) print("ok")
Sign in to track your progress through the lab.