Sets

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.

"""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.

"""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.

"""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.