--- title: Sets source: 'https://academia.sh/en/courses/python-data-structures/sets' course: 'Data Structures and Functional Tools' language: en updated: '2026-08-17T18:10:25+00:00' license: 'CC BY-SA 4.0' --- # Sets Deduplicating three hundred items does 15050 comparisons scanned by hand, 200 handed to a set, and all three give the same hundred items; all six set operations create 0 new items, and four build a new container while two mutate the existing one. In the previous lesson's measurement, the set stood quietly beside the dict and gave the same numbers: **1** comparison for a found item, **0** for one not found. What it does on its own was never asked. A **set** is a container that holds only membership — no value, no order, no duplicates. These three absences are the result of the same mechanism, and they're what directly makes this lesson's job possible: **dropping duplicates** from a pile of data. The question again gets a numeric answer. How many comparisons does hand-picking duplicates cost against handing them to a set, and are the items coming back out new or old? ## What a Set Asks A set does not ask "at what position" when holding an item; it only asks "is this already here." It finds the answer the same way the dict found a key in the previous lesson: it computes which bucket the item's **hash value** falls into and looks there. This is why a set's items also have to be hashable — the same condition measured in the tuples lesson applies here to items. The mechanism itself — hash table, collision, load factor — was built in the **Data Structures** course and is not repeated. What's measured here is how many concrete comparisons two spellings of the same job cost; not a growth-class claim, a count made with specific data. The item itself counts the comparisons. The hand-written spelling of deduplication is direct and readable: a result list is kept, each item is checked against "is this already in the list," and added if not. This spelling's hidden cost is that "is it there" is asked of **a list** every time — and the previous lesson measured what a membership question asked of a list costs. - **CO40** — The raw data is three hundred items carrying **a hundred distinct values**; each value appears exactly three times. The expected result is therefore known in advance, and the setup is its own oracle. - **CO41** — All three methods work on the **same raw list**; items are created once, and none of the methods builds a new item. - **CO42** — The counter resets right before each method; building the raw data does not enter the measurement. - **CO43** — The "new items" column is found by searching each result item in the raw data with `is`; zero means the result is shared. - **CO44** — The order column is filled only for methods that **guarantee order**; the order a set gives its items in is not measured and is not relied on. ```python """Deduplication: three methods, same result, different comparison counts.""" class Counting: """A value that counts equality comparisons.""" counter = {"comparisons": 0} def __init__(self, value): self.value = value def __eq__(self, other): Counting.counter["comparisons"] += 1 return isinstance(other, Counting) and self.value == other.value def __hash__(self): return hash(self.value) UNIQUE = 100 RAW = [Counting(i % UNIQUE) for i in range(3 * UNIQUE)] def manual(raw): result = [] for x in raw: if x not in result: result.append(x) return result def to_set(raw): return set(raw) def to_dict_keys(raw): return dict.fromkeys(raw) print(f"{'method':<22s}{'comparisons':>13s}{'unique':>9s}" f"{'new items':>12s}{'order kept':>14s}") FIRST = None for label, method, ordered in (("manual scan", manual, True), ("set(raw)", to_set, False), ("dict.fromkeys(raw)", to_dict_keys, True)): Counting.counter["comparisons"] = 0 result = method(RAW) count = Counting.counter["comparisons"] new_count = sum(1 for x in result if not any(x is y for y in RAW)) if FIRST is None: FIRST = list(result) same_order = list(result) == FIRST print(f"{label:<22s}{count:>13d}{len(result):>9d}{new_count:>12d}" f"{str(same_order) if ordered else 'no guarantee':>14s}") print() print(f"raw data {len(RAW)} items | duplicates {len(RAW) - UNIQUE} | " f"unique {UNIQUE}") print(f"are the items in the manual scan's result from the raw data: " f"{all(any(x is y for y in RAW) for x in manual(RAW))}") ``` ``` method comparisons unique new items order kept manual scan 15050 100 0 True set(raw) 200 100 0 no guarantee dict.fromkeys(raw) 200 100 0 True raw data 300 items | duplicates 200 | unique 100 are the items in the manual scan's result from the raw data: True ``` ## Same Hundred Items, Three Different Bills The "unique" column is the same in all three rows: **100**. All three methods give the correct result, and all three create **0** new items — every object in the result is one of the raw data's own. The difference is entirely in the left column. The manual scan does **15050** comparisons. This number comes from two parts. The first hundred items are always new, so each is compared against the entire result accumulated so far; that comes to **4950**. The remaining two hundred are duplicates, and each stops as soon as it finds its match; that is **10100**. The total grows not by **how many times** a list gets asked a membership question, but by how many **slots** each question crosses. Handing it to a set finishes the same job in **200** comparisons — about a seventy-fifth as many. The gap between the two does not come from a different spelling, it comes from a different **way of asking**: the manual scan walks the whole result every time, the set looks at a single bucket every time. And the number 200 itself is meaningful: the raw data has exactly **200** duplicates. A set makes one comparison per duplicate, none for a unique item. If an item is new, its bucket is empty and there is nothing to compare against. The third row gives both the price a set exacts and a way to avoid paying it. A set has no order; what order it gives its items is not measured in this lesson and is not relied on. But a mapping that keeps keys in insertion order does the same deduplication with the **same 200 comparisons** and keeps order too. If the result needs order, the right tool is not a set, it is a mapping used with its keys. ## Set Operations A set's second job is arithmetic between sets: union, intersection, difference, symmetric difference. These four operations come from set theory, and their meaning is beyond dispute. What's measured is not their meaning but **what they cost**: how many items they create, whether the result is a new container, and where the objects inside it come from. - **CO45** — All six forms start from a **freshly built** copy of the same three-item set; items are created once before the measurement. - **CO46** — The two sets **intersect on one item**, so the intersection and difference counts are known in advance and confirm the table. - **CO47** — The "items from pool" column is found by searching each result item in the pool, before measurement, with `is`. - **CO48** — Hashability is tested directly, and the raised exception's **class name** is written; the hash value is never printed. ```python """Set operations: each builds a new container, none creates a new item.""" COUNTER = {"created": 0} class Item: def __init__(self, value): COUNTER["created"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["created"] = 0 def created(): return COUNTER["created"] POOL = [Item(i) for i in range(5)] LEFT = {POOL[0], POOL[1], POOL[2]} RIGHT = {POOL[2], POOL[3], POOL[4]} def union_op(a): return a | RIGHT def intersect_op(a): return a & RIGHT def difference_op(a): return a - RIGHT def symmetric_diff_op(a): return a ^ RIGHT def inplace_union(a): a |= RIGHT return a def inplace_intersect(a): a &= RIGHT return a FORMS = (("a | b", union_op), ("a & b", intersect_op), ("a - b", difference_op), ("a ^ b", symmetric_diff_op), ("a |= b", inplace_union), ("a &= b", inplace_intersect)) print(f"{'operation':<10s}{'new items':>9s}{'same container':>16s}{'items':>7s}" f"{'items from pool':>17s}") for label, op in FORMS: a = set(LEFT) before = a reset() result = op(a) from_pool = all(any(x is y for y in POOL) for x in result) print(f"{label:<10s}{created():>9d}{str(result is before):>16s}{len(result):>7d}" f"{str(from_pool):>17s}") print() print(f"{'test':<34s}{'result'}") print(f"{'LEFT <= LEFT | RIGHT':<34s}{LEFT <= (LEFT | RIGHT)}") print(f"{'LEFT < LEFT':<34s}{LEFT < LEFT}") print(f"{'LEFT.isdisjoint(RIGHT)':<34s}{LEFT.isdisjoint(RIGHT)}") print(f"{'(LEFT - RIGHT).isdisjoint(RIGHT)':<34s}{(LEFT - RIGHT).isdisjoint(RIGHT)}") print() FROZEN = frozenset({POOL[0], POOL[1]}) print(f"frozen set can be a set's item -> {FROZEN in {FROZEN}}") for candidate in (LEFT, FROZEN): try: {candidate: 0} result = "yes" except TypeError as e: result = type(e).__name__ print(f"{type(candidate).__name__:<12s} can be a key -> {result}") try: {[1, 2]} except TypeError as e: print(f"list can be a set item -> {type(e).__name__}") ``` ``` operation new items same container items items from pool a | b 0 False 5 True a & b 0 False 1 True a - b 0 False 2 True a ^ b 0 False 4 True a |= b 0 True 5 True a &= b 0 True 1 True test result LEFT <= LEFT | RIGHT True LEFT < LEFT False LEFT.isdisjoint(RIGHT) False (LEFT - RIGHT).isdisjoint(RIGHT) True frozen set can be a set's item -> True set can be a key -> TypeError frozenset can be a key -> yes list can be a set item -> TypeError ``` ## Four Computations, Zero Items Six rows' "new items" column is entirely **0**, and "items from pool" is entirely **True**. Set operations compute, they do not produce: every object visible in the result is one created before the measurement. This is the third repeat of the pattern measured in lists and dicts — Python's built-in containers do not carry items, they arrange links to them. The item counts confirm the setup: two three-item sets intersecting on one item give a union of **5**, an intersection of **1**, a difference of **2**, a symmetric difference of **4**. The totals adding up is the measurement's own internal check. The distinction is again in the "same container" column, and it is familiar by now: the operator form builds a **new container**, the assignment form mutates the **existing** one. This is the fourth time in this course the same distinction shows up in the same place — `+` versus `+=` in a list, the same pair's forced rebuild in a tuple, `|` versus `|=` in a dict, `|` versus `|=` in a set. The rule is not specific to the container, it is specific to the language: **the operator gives a new object, the assignment operator tries to mutate the existing one.** The subset tests in the lower block give a set's comparison meaning. `<=` asks about a subset, and a set is a subset of itself; `<` asks about a **proper** subset and gives **False** for itself. These two are about a set's containment, not numbers, and shouldn't be confused with a number comparison. The last block carries the immutability measurement over to sets. A set is itself **mutable**, so it cannot be hashed and cannot be a key; it fails with `TypeError`. A **frozen set** holds the same items in an immutable container, and it can be both a key and another set's item. A list can be neither. The rule built in the tuples lesson holds here exactly the same: the condition for a container to be **placeable inside** another container is the promise it makes that its own contents will stay fixed. ## Doing the Same Computation with a List Every set operation can be written with lists too; none of them requires a capability specific to a set. Intersection means "those on the left also found on the right," difference means "those on the left not found on the right," and both are written as a one-line filter. These spellings' result is correct. What's measured is not correctness, it is **price**. - **CO49** — The two collections are **two hundred items each** and **overlap on a hundred**; that the intersection and difference results are a hundred items is known from the setup and confirms the table. - **CO50** — The list and set forms are built from the **same objects**; the counter resets right before each row, and building the containers does not enter the measurement. - **CO51** — The last block does not measure a number; it separates the question a set **can** answer from the one it **cannot**. ```python """Taking an intersection by hand versus handing it to a set; and the information deduplication drops.""" class Counting: counter = {"comparisons": 0} def __init__(self, value): self.value = value def __eq__(self, other): Counting.counter["comparisons"] += 1 return isinstance(other, Counting) and self.value == other.value def __hash__(self): return hash(self.value) LEFT_LIST = [Counting(i) for i in range(200)] RIGHT_LIST = [Counting(i) for i in range(100, 300)] LEFT_SET, RIGHT_SET = set(LEFT_LIST), set(RIGHT_LIST) def manual_intersect(): return [x for x in LEFT_LIST if x in RIGHT_LIST] def set_intersect(): return LEFT_SET & RIGHT_SET def manual_difference(): return [x for x in LEFT_LIST if x not in RIGHT_LIST] def set_difference(): return LEFT_SET - RIGHT_SET print(f"{'operation':<28s}{'comparisons':>14s}{'result items':>13s}") for label, op in (("intersection, two lists", manual_intersect), ("intersection, two sets", set_intersect), ("difference, two lists", manual_difference), ("difference, two sets", set_difference)): Counting.counter["comparisons"] = 0 result = op() print(f"{label:<28s}{Counting.counter['comparisons']:>14d}{len(result):>13d}") print() RAW = [Counting(i % 100) for i in range(300)] DEDUPED = set(RAW) print(f"raw data {len(RAW)} items -> set {len(DEDUPED)} items") print(f"question a set can answer: 'is it there' -> {Counting(7) in DEDUPED}") print("question a set cannot answer: 'how many times'") ``` ``` operation comparisons result items intersection, two lists 25050 100 intersection, two sets 100 100 difference, two lists 25050 100 difference, two sets 100 100 raw data 300 items -> set 100 items question a set can answer: 'is it there' -> True question a set cannot answer: 'how many times' ``` The four rows' "result items" column settles correctness: all four give **100** items. The list spelling is not wrong, only expensive. Taking the intersection with lists does **25050** comparisons, with sets **100** — a two-hundred-fifty-fold difference, on the same data, with the same result. The difference rows give the same number, and that is not a coincidence. In the list spelling, the right list is scanned for every item; whether the scan ends in "found" or "not found" does not determine how many slots got crossed. The same symmetry holds for sets: the intersection makes one comparison per matching item, so does the difference. Changing the access method changes the **shape** of the cost, not just its size. The last block draws a set's boundary, and it is this lesson's closing word. Three hundred items handed to a set come down to **100**. What's lost is not two hundred objects — the objects are still there, the raw list still holds them. What's lost is **information**: which value appeared how many times. A set answers "is it there" with one comparison, but it can never answer "how many times," because it never keeps that number at all. Deduplication is cheap; the source of that cheapness is the assumption that the discarded information will never be asked for again. ## Summary - On three hundred items, deduplication does **15050** comparisons scanned by hand, **200** handed to a set; all three methods give the same **100** unique items and **0** new items. - A set's **200** equals the raw data's duplicate count exactly: every duplicate costs one comparison, a unique item costs none. - A set has no order; if order needs keeping, a mapping is used that does the same **200** comparisons while also keeping insertion order. - All six set operations create **0** items, and every object in the result is old; the operator form builds a new container, the assignment form mutates the existing one. - A set cannot be a key because it is mutable; a frozen set can be both a key and a set item — the condition is the promise a container makes that its own contents stay fixed. - Taking the same intersection with lists does **25050** comparisons, with sets **100**; both give the same **100** items, but deduplication drops the "how many times" information. ## Next Step This lesson's last line wrote the question a set cannot answer: **how many times.** Anyone wanting to keep that answer writes the same pattern by hand — open a dict, increment if the key exists, start at one if not. There are other patterns written the same way by hand too: taking items from both ends of a list, preparing an empty container for a key that does not exist. The next lesson looks at the standard library's ready-made counterparts for these patterns and puts each one side by side with its hand-written equivalent. Two numbers get measured: how many lines, and how many objects.