PHASE 4Beginner ~25 min· topic 6 of 11

Topic 4.6

Sets: Unique Items and Fast Membership

In one line

A set is a collection of unique items with no duplicates and no guaranteed order, built on the same hashing as dictionaries. Sets answer "is this in the collection?" very fast and support union, intersection and difference like in school maths.

Think of it like this

The list of students who attended a class. Writing a name twice makes no difference: either you attended or you didn't. And the order of the names does not matter. Better still, you can ask questions like "who was in both Monday's class and Tuesday's class?". A Python set is exactly that: a bag of distinct items.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Set: A collection of unique, hashable items with no guaranteed order.
Union: All items that are in either set. Written a | b.
Intersection: The items that are in both sets. Written a & b.
Difference: The items in the first set but not the second. Written a - b.
Symmetric difference: Items in exactly one of the two sets. Written a ^ b.
Subset: A set whose items are all inside another set. Written a <= b.
Frozenset: An immutable set. It can be a dictionary key or a member of another set.
Deduplicate: Remove repeated items so each appears once.

Step by step

01Create a set and drop duplicates

Duplicates vanish on their own. len counts the distinct items. Notice that {} is a dictionary; an empty set must be written set().

main.pywhole filepython

colors = {"red", "green", "blue", "red"}
print(len(colors))          # 3
print(sorted(colors))       # a stable order for printing

print(type({}).__name__)         # dict
print(type(set()).__name__)      # set

02Add, remove and test membership

add of an existing item changes nothing. discard is the forgiving removal, remove the strict one. in is the fast part.

main.pywhole filepython

colors = {"red", "green"}
colors.add("blue")
colors.add("red")            # already there: no change
colors.discard("pink")       # missing: no error
colors.remove("green")       # present: removed
print("blue" in colors)      # True

03Deduplicate a list

set(numbers) removes repeats but loses order. If you need to keep the first-seen order, a dictionary does it, because dictionaries keep insertion order: list(dict.fromkeys(numbers)) (fromkeys builds a dictionary whose keys are the items).

main.pywhole filepython

numbers = [3, 1, 3, 2, 1]
print(sorted(set(numbers)))             # [1, 2, 3]
print(list(dict.fromkeys(numbers)))     # [3, 1, 2]  first-seen order

04Set operations

These match the Venn diagrams from school. Because the result is again a set, print it with sorted(...) to get a stable order for strings.

main.pywhole filepython

monday = {"Asha", "Ravi", "Meena"}
tuesday = {"Ravi", "Tom", "Meena", "Zoya"}
print(sorted(monday | tuesday))   # either day
print(sorted(monday & tuesday))   # both days
print(sorted(monday - tuesday))   # Monday only
print(sorted(monday ^ tuesday))   # exactly one day

Set operationsdiagram

Rendering diagram…

05Subsets and disjoint sets

A subset test is a single operator. isdisjoint asks "do these two have anything in common?" and stops at the first shared item.

main.pywhole filepython

small = {1, 2}
big = {1, 2, 3}
print(small <= big)              # True
print(big >= small)              # True
print(small.isdisjoint({7, 8}))  # True

06frozenset: a set that can be a key

A normal set can't be a key because it can change. A frozenset can't change, so it is hashable. Two frozensets with the same items are equal and hash equally, whatever order you wrote them in.

main.pywhole filepython

team = frozenset(["Asha", "Ravi"])
scores = {team: 90}
print(scores[frozenset(["Ravi", "Asha"])])   # 90

Try it yourself

1
Who is missing?
In the second example, add "Kabir" to tuesday. Before running, predict how each of the five set lines changes.
2
Count the vocabulary
Replace the sentence in words with any sentence of your own (all lowercase, no punctuation). How many words does it have and how many of them are different?

Code & diagrams

Create, change and test a set New tab

Sets are printed with sorted(...) here so the order is the same on every run. `type(x).__name__` gives the name of x's type as text.

Expected output

distinct colours: 3 ['blue', 'green', 'red']
after changes: ['blue', 'pink', 'red']
blue in colors: True
green in colors: False
unique, sorted: [1, 2, 3]
unique, first-seen order: [3, 1, 2]
{} is a dict | set() is a set

Union, intersection, difference and friends New tab

Expected output

either day (|): ['Asha', 'Meena', 'Ravi', 'Tom', 'Zoya']
both days (&): ['Ravi', 'Tom']
only Monday (-): ['Asha', 'Meena']
only Tuesday (-): ['Zoya']
exactly one day (^): ['Asha', 'Meena', 'Zoya']
{1, 2} <= {1, 2, 3}: True
disjoint: True
frozenset key found: 90
words: 8 | unique words: 5
vocabulary: ['and', 'bat', 'cat', 'hat', 'the']

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Index into a set

Read the first item of a set by index.

main.pywhole filepython

s = {10, 20, 30}
print(s[0])

terminal

$ python main.py

── what you'll see ──

Traceback (most recent call last):

File "main.py", line 2, in <module>

print(s[0])

~^^^

TypeError: 'set' object is not subscriptable

Break #2

Remove an item that is not there

Call remove on a missing item.

main.pywhole filepython

s = {1, 2, 3}
s.remove(9)

terminal

$ python main.py

── what you'll see ──

Traceback (most recent call last):

File "main.py", line 2, in <module>

s.remove(9)

~~~~~~~~^^^

KeyError: 9

Myth vs fact

Myth

{} makes an empty set.

Fact

{} is an empty dictionary. An empty set is set().

Myth

Sets keep the order I added items in.

Fact

They give no such promise. Use a list or a dict (insertion order) if order matters, and sorted(s) to print a set.

Myth

Sets are just lists without duplicates.

Fact

Their real value is speed of in and the set maths. A list of unique items is a different thing: it keeps order and allows indexing.

Myth

A set can hold anything.

Fact

Members must be hashable. Lists, dictionaries and sets are not allowed; tuples and frozensets are.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
A set is a hash table without values, built from the same machinery as a dict (Topic 4.5). Membership is O(1) on average; union costs O(len(a) + len(b)), and intersection costs about O(min(len(a), len(b))) because it loops over the smaller set.
▸
Converting a list to a set to test membership many times is the single most common speed-up in beginner code: if x in big_list inside a loop is O(n*m); with big_set = set(big_list) it becomes O(n + m) in total. Converting costs O(m) once, so it is worth it only when you test more than a few times.
▸
Set elements need __hash__ and __eq__ consistent with each other (Topic 4.5). Floats such as nan break intuition: nan != nan, yet a set holds the same nan object once (membership checks identity first), while two separate float("nan") objects count as two members. Avoid floats as set members when exact equality is unreliable (Topic 1.3).
▸
The operators |, &, -, ^ need both sides to be sets (or frozensets), while the named methods accept any iterable: {1, 2}.union([2, 3]) works but {1, 2} | [2, 3] raises TypeError. The result of a mixed operation takes the type of the left operand, so frozenset | set is a frozenset. A set is also unordered in a precise sense: its iteration order depends on the hashes and on the insertion history, so two equal sets can iterate in different orders.
▸
When you need a sorted set or ordered operations such as "the smallest item greater than x", a plain set is the wrong tool. Keep a sorted list with bisect (Topic 4.2), use heapq, or an external library such as sortedcontainers.

Remember this

1
You write a set with curly brackets and no colons: colors = {"red", "green", "blue"}. Duplicates are dropped at once, so {1, 2, 2, 3} has three items. **An empty set is set()**, not {}, because {} is an empty dictionary. set(some_list) turns any collection into a set, which is the shortest way to remove duplicates.
2
Sets have no order and no index. colors[0] raises TypeError, and the order a set prints in is not something to depend on (for strings it even changes between runs, Topic 4.5). When you need to print or compare in a stable way, use sorted(colors), which gives a list.
3
add(x) inserts an item (nothing happens if it is already there). remove(x) deletes it and raises KeyError if it is missing; discard(x) deletes it quietly if it is missing. pop() removes and returns some item (you can't choose which). x in colors is the main reason sets exist: it is O(1) on average (the time does not grow with the size; Topic 4.5) instead of scanning every item as a list does.
4
Sets do maths. a | b (union) is everything in either set. a & b (intersection) is what both share. a - b (difference) is what is in a but not in b. a ^ b (symmetric difference) is what is in exactly one. Tests: a <= b (subset), a >= b (superset), a.isdisjoint(b) (nothing in common). Each also has a named method (union, intersection, difference) that accepts any iterable.
5
Set members must be hashable, so a set cannot contain a list, a dictionary or another set; tuples and strings are fine. If you need a set of sets, or a set as a dictionary key, use a **frozenset**: an immutable set made with frozenset(items). It has the same read operations and can be hashed.
6
Typical jobs for a set: remove duplicates, check membership in a large collection, find items two collections have in common (or are missing from one), and track "what have I already seen?" in a loop. In AI work a set holds the unique tokens of a text (the small pieces, such as words, that a language model reads; the set of them is its vocabulary) or the ids of documents already processed.

Explain it without notes

How do you remove duplicates from a list, and what do you lose?

What is the difference between remove and discard on a set?

Why is x in my_set faster than x in my_list?

What is a frozenset and when do you need one?

How do you find the duplicates in a list in O(n) time?

Practice

Given votes = ["a", "b", "a", "c", "b", "a"], print how many different options were voted for and the sorted list of options.

Two friends have watched {"Dune", "Up", "Cars"} and {"Cars", "Coco", "Up"}. Print which films both watched and which films only the first friend watched, each sorted.

Write a loop that goes through [4, 7, 4, 9, 7], prints new: <n> the first time it sees a number and seen: <n> after that.

Trade-offs

↔
Speed and set maths cost order and indexing. A set is the right choice for membership and comparisons, and the wrong one when position matters.
↔
A set copy costs memory. Building set(big_list) to speed up lookups needs a hash table with spare room, often several times the size of the list's pointer array. For a handful of lookups, scanning the list is cheaper.

Done when you can

Done when you can create a set, add and remove items, and say why {} is not an empty set.
Done when you can remove duplicates from a list and say what is lost.
Done when you can use union, intersection, difference and symmetric difference.
Done when you can explain why membership in a set is fast and why members must be hashable.
Done when you can print a set in a stable order and use a frozenset as a dictionary key.

Command Palette

Words you'll meet

Step by step

01Create a set and drop duplicates

02Add, remove and test membership

03Deduplicate a list

04Set operations

05Subsets and disjoint sets

06frozenset: a set that can be a key

Try it yourself

Who is missing?

Count the vocabulary

Code & diagrams

Break it on purpose

Index into a set

Remove an item that is not there

Myth vs fact

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can