Sets and fast membership testing

A set holds unique items, unordered. No duplicates, no positions. That sounds limiting until you meet the two problems sets solve better than anything else: removing duplicates, and asking "is this in there?" quickly.

Making one

Curly brackets, like a dictionary but without the colons:

colours = {"red", "green", "blue"}
numbers = {1, 2, 3}

The empty set needs the constructor, because {} is an empty dictionary:

empty = set()           # correct
not_a_set = {}          # this is a dict

That is a genuine wart in the syntax, and the only way through it is to know.

Duplicates vanish on creation:

print({1, 2, 2, 3, 3, 3})

{1, 2, 3}

No error, no warning. A set simply cannot hold the same value twice.

Removing duplicates

The most common use, and a one-liner:

names = ["priya", "arjun", "priya", "sneha", "arjun"]
unique = list(set(names))
print(unique)

['sneha', 'priya', 'arjun']

Note the order. Sets have no order, and the order you get back is not the order you put things in, nor sorted, nor stable between runs in every case. If order matters:

print(sorted(set(names)))

Or, to keep the original order, use a dictionary — keys are unique and do keep insertion order:

print(list(dict.fromkeys(names)))

['priya', 'arjun', 'sneha']

That is a neat trick worth remembering: dict.fromkeys deduplicates while preserving order.

Fast membership

print("red" in colours)     # True

That looks identical to in on a list, and the difference is speed.

Checking a list means comparing against each item until a match is found. On a million items that is up to a million comparisons. A set jumps more or less straight to the answer, and does so no matter how big it gets.

For a handful of items you will never notice. For anything large, inside a loop, it is the difference between a program finishing and a program appearing to hang:

# slow if banned is a large list
banned = ["...thousands of words..."]
for word in text.split():
    if word in banned:
        ...

# fast
banned = set(banned)

One line, and the loop stops scanning thousands of entries every iteration.

Rule of thumb: if you are repeatedly asking "is this in that collection?" and the collection is large, make it a set.

Adding and removing

colours = {"red", "green"}

colours.add("blue")           # add one
colours.update(["a", "b"])    # add several

colours.remove("red")         # KeyError if absent
colours.discard("purple")     # no error if absent
value = colours.pop()         # removes an arbitrary item
colours.clear()

discard() is the forgiving version of remove(). Use it when absence is fine.

pop() removes an item, not a predictable one — there is no last item in an unordered collection.

The set operations

This is where sets earn their name, and they replace a lot of loops.

a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

print(a | b)    # {1, 2, 3, 4, 5, 6}  union — in either
print(a & b)    # {3, 4}              intersection — in both
print(a - b)    # {1, 2}              difference — in a, not b
print(a ^ b)    # {1, 2, 5, 6}        symmetric difference — in one, not both

Each has a named method too, and the names read better in code somebody else will maintain:

print(a.union(b))
print(a.intersection(b))
print(a.difference(b))

These are genuinely practical. Which users signed up this month and last?

returning = last_month & this_month
new = this_month - last_month
lapsed = last_month - this_month

Three lines that would otherwise be three loops, and they are quick as well as short.

Comparisons:

print({1, 2} <= {1, 2, 3})       # True — subset
print({1, 2, 3} >= {1, 2})       # True — superset
print({1, 2}.isdisjoint({3, 4})) # True — nothing in common

What can go in a set

The same rule as dictionary keys: items must be immutable.

valid = {1, "a", (2, 3)}

invalid = {[1, 2]}

TypeError: unhashable type: 'list'

Sets and dictionary keys share the same machinery, which is why the restriction and the error message are identical.

What you give up

Be clear about the trade:

• No order. You cannot ask for the first item, slice it, or rely on the order of a loop.
• No duplicates. If you need to know a value appeared three times, a set has already thrown that away — use a dictionary count.
• No indexing. colours[0] is a TypeError.

A set is the right tool when you care whether something is present and nothing else about it.

Choosing quickly

• Order matters, duplicates allowed → list
• Fixed shape, must not change → tuple
• Looking things up by name → dictionary
• Unique items, fast membership → set

The last lesson of this module goes through this properly with worked examples.

Practice

1. Make a set from [1, 2, 2, 3, 3, 3] and print it. Then print its length.
2. Deduplicate ["b", "a", "c", "a", "b"] three ways: with set (order lost), with sorted(set(...)), and with dict.fromkeys (order kept). Compare.
3. Given two sets of student names — one for maths, one for science — find who takes both, only maths, and either subject.
4. Take a paragraph of text, split it into words, and find how many unique words it contains.
5. Write a loop checking each of 10,000 numbers against a collection of 10,000 numbers, once with a list and once with a set. Time both using time.perf_counter(). The difference should be obvious.
6. Try {[1, 2]} and read the error. Then make it work.
7. Explain in one sentence why {} creates a dictionary and not a set.

Next: nesting these structures inside each other, which is what real data actually looks like.