Sets: unique items and fast lookups

A collection with no repeats

A set holds items with no duplicates and no order. You write one with curly braces, or build one from any collection with set(). Adding something that's already there changes nothing:

gear = {"tent", "stove", "lantern"}
print(gear, len(gear))

gear.add("stove")   # already there: nothing happens
gear.add("rope")
print(gear, len(gear))

signups = ["ana@ex.org", "bo@ex.org", "ana@ex.org", "cy@ex.org", "bo@ex.org"]
print(len(signups), "sign-ups from", len(set(signups)), "people")

Run it a few times, and look at the order the gear prints in. A set doesn't keep the order you added things in, so you can't ask for "item 0": gear[0] is an error. If you need order, sort it on the way out, with sorted(gear), which gives you a list.

One trap catches everyone once: {} is an empty dictionary, not an empty set, because dictionaries had the braces first. An empty set is set().

letters = set("banana")
print(len(letters), sorted(letters))

Adding, removing and asking

• s.add(x) adds one item, and s.update(other) adds everything from another collection.
• s.discard(x) removes an item if it's there and does nothing if it isn't. s.remove(x) raises a KeyError when it's missing, which is what you want when a missing item means a bug.
• x in s asks whether an item is there.

That last one is where sets earn their keep. To answer x in some_list, Python checks the items one by one until it finds a match, so a list of a million items can take a million checks. A set works out where the item would be stored from the item itself (a number called its hash) and looks only there. That takes about the same time for ten items as for ten million:

import time

ids = list(range(1_000_000))
id_set = set(ids)

start = time.perf_counter()
for _ in range(20):
    999_999 in ids
list_time = time.perf_counter() - start

start = time.perf_counter()
for _ in range(20):
    999_999 in id_set
set_time = time.perf_counter() - start

print(f"list: {list_time:.3f}s   set: {set_time:.6f}s")

The price of that speed is a rule about what a set can hold: only hashable items, ones that can't change. Numbers, strings and tuples are fine. A list isn't, because changing it would change its hash and lose it inside the set. {[1, 2]} raises TypeError: unhashable type: 'list'; use a tuple, {(1, 2)}, instead.

Comparing collections

The trail club runs two trips this weekend. Sets answer every "who's on what" question with one operator:

saturday = {"Ana", "Bo", "Cy", "Dee"}
sunday = {"Cy", "Dee", "Eli"}

print("both days:", sorted(saturday & sunday))       # intersection
print("either day:", sorted(saturday | sunday))      # union
print("Saturday only:", sorted(saturday - sunday))   # difference
print("just one day:", sorted(saturday ^ sunday))    # symmetric difference

print({"Cy", "Dee"} <= saturday)        # subset: is every one of them on Saturday?
print(saturday.isdisjoint({"Fay"}))    # no one in common

Read the operators as questions: & is "in both", | is "in either", - is "in the first but not the second" (so a - b and b - a differ), and ^ is "in exactly one". Each also has a method name that reads like English and takes any collection, not only a set: saturday.intersection(names_list).

A set comprehension builds a set the way a list comprehension builds a list, with braces instead of brackets. It's the tidy way to clean and dedupe in one go: {e.strip().lower() for e in emails}.

def in_common(a, b):
    result = []
    return result


print(in_common(["tent", "stove", "rope", "stove"], ["rope", "map", "stove"]))

Reconciling two lists

Here's a job you'll meet at work: yesterday's export and today's, and someone wants to know what changed. Real exports are messy, so clean first, with a set comprehension, then let the set operators do the rest:

yesterday = ["TE-101", "ST-114", "la-102 ", "BO-120"]
today = ["TE-101", "LA-102", "PA-111", "ST-114", "TE-101"]

def clean(skus):
    return {s.strip().upper() for s in skus}

before, after = clean(yesterday), clean(today)
print("added:", sorted(after - before))
print("removed:", sorted(before - after))
print("kept:", sorted(before & after))

Without the cleaning step, "la-102 " and "LA-102" would look like two different products, one removed and one added. That's the usual bug in this kind of report, and it's worth a test.

Two more things you'll reach for. When you need to dedupe and keep the original order, a set can't do it alone, but a dictionary keeps insertion order: list(dict.fromkeys(items)) keeps the first of each. And when you need a set inside a set, or a set as a dictionary key, use a frozenset, a set that can't change after it's made, which makes it hashable.

def first_repeat(items):
    return None


print(first_repeat(["b", "a", "c", "a", "b"]))

def pair_for(prices, budget):
    seen = set()
    for p in prices:
        if budget - p in seen:
            return (budget - p, p)
        seen.add(p)
    return None

prices = [45, 170, 12, 39, 88, 61]
print(pair_for(prices, 100))   # 39 + 61
print(pair_for(prices, 1000))  # no pair

a = {1, 2, 3, 4}
b = {3, 4, 5}
print(sorted(a - b), sorted(b - a), len(a ^ b))

Where sets turn up next

Once you know sets, you'll spot them all over the rest of the course and in real code:

• Not doing work twice. A web crawler keeps a set of the pages it has visited, and a route planner keeps a set of the places it has explored, so neither goes round in circles. You'll build both later.
• Permissions. A user's roles are a set, and so are the roles a page needs. "Can this person see it?" is required <= roles: is every required role among theirs?
• Cleaning data. "Which of these customer IDs aren't in our system?" is a difference, and "which records appear in both exports?" is an intersection, long before you reach for pandas.
• Language models. A tokenizer's vocabulary is, in effect, a set of the pieces of text it knows, and checking whether a word is in it is exactly the fast lookup from earlier.

A good rule of thumb: if you catch yourself writing if x not in some_list inside a loop, ask whether some_list should be a set.