Dictionaries & Sets

▶Today's videos

Watch each video, then work the matching sections below. Watching alone will not do it.

1Key-value modelling

When position is the wrong way to find things.

A list answers "what is at position 3?". A dictionary answers "what is associated with this key?" — which is what you actually want far more often.

ages = {"Amin": 34, "Ada": 36, "Grace": 45}

print(ages["Amin"])
ages["Alan"] = 41            # add
ages["Amin"] = 35            # update — same syntax

print("Ada" in ages)
print(len(ages))
print(ages.get("Nobody", 0))  # a default instead of a crash

Iterating properly

for name in ages:                 # keys, by default
    print(name)

for name, age in ages.items():    # both — use this one
    print(f"{name} is {age}")

.items() gives you a tuple per entry, which you unpack exactly as you learned yesterday. Since Python 3.7 dictionaries keep insertion order, so iteration is predictable — but do not confuse that with being sorted.

2Counting and grouping

Two patterns that cover most real dictionary work.

counts.get(ch, 0) + 1 is the whole counting pattern. The .get supplies zero the first time a key is seen, so there is no special case for "first time".

Grouping

words = ["apple", "avocado", "banana", "blueberry", "cherry"]
by_letter = {}

for word in words:
    first = word[0]
    if first not in by_letter:
        by_letter[first] = []
    by_letter[first].append(word)

for letter, group in by_letter.items():
    print(letter, group)

3Hashing, intuitively

Why a dictionary does not slow down as it grows.

Finding a name in a list means checking items one at a time — a thousand items, up to a thousand comparisons. A dictionary does something different: it computes where the key should live.

A hash function turns a key into a number; the number picks a bucket. Lookup runs the same function and goes straight to that bucket — it does not scan. That is why a dictionary with a million entries is about as fast as one with ten.

Which explains the rules about keys

The cost, measured

x in some_list is the blue line — the work grows with the data. x in some_dict is the green line — flat. For a handful of items the difference is irrelevant. For fifty thousand it is the difference between instant and unusable. You will make this argument properly with Big-O on Day 11.

4Sets

A dictionary with the values thrown away — which is more useful than it sounds.

seen = {3, 1, 4, 1, 5, 9, 2, 6, 5}
print(seen)                      # duplicates gone, order not guaranteed

tags = set()                     # NOT {} — that is an empty dict
tags.add("python")
tags.add("python")               # no effect
print(len(tags))

a = {1, 2, 3, 4}
b = {3, 4, 5}
print(a & b)                     # in both
print(a | b)                     # in either
print(a - b)                     # in a only
print(a ^ b)                     # in exactly one

The three things sets are for

1. Deduplication — list(set(items)) removes duplicates in one step (and loses order).
2. Membership — if word in stopwords: where stopwords is a set, not a list.
3. Set arithmetic — "which users are in both groups?" is a & b, not a nested loop.

5Choosing the structure

The question you are asking picks the answer.

When a dict has outgrown itself

# this works, and it is a warning sign
book = {
    "title": "Think Python",
    "author": "Downey",
    "year": 2015,
    "tags": {"python", "beginner"},
}

# every access is a string you can typo, with no help from the editor
print(book["athor"])     # KeyError, at runtime, maybe in production

>_Python playground

A real Python interpreter running inside your browser. Nothing is installed, nothing is uploaded, nothing can break.

✓Exercise set

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.