Sets & The frozenset

A Set is an unordered collection of unique elements. It is the Pythonic implementation of mathematical set theory. If your data requires that there be no duplicates, or if you need to perform operations like “Find everything in List A that is NOT in List B,” the set is your most efficient tool.

---

1. Defining Sets

Sets are created using curly braces {} or the set() constructor.

syntax.py

# Literal
primes = {2, 3, 5, 7}

# From a list (Automatically removes duplicates!)
names = ["Alice", "Bob", "Alice"]
unique_names = set(names) # {'Alice', 'Bob'}

# Empty Set
# WARNING: {} creates a dictionary. Use set() for an empty set.
empty = set()

---

2. Mathematical Power: Set Operations

Python sets support standard mathematical operations using intuitive operators.

Operation	Symbol	Description
Union	`A	B`
Intersection	A & B	Only what is common to both.
Difference	A - B	In A, but not in B.
Symmetric Diff	A ^ B	In A or B, but NOT both.

set_math.py

admins = {"alice", "bob"}
users = {"bob", "charlie"}

print(admins & users) # {"bob"} (Admins who are also users)
print(admins - users) # {"alice"} (Admins who are NOT standard users)

---

3. The frozenset: Immutable Sets

Standard sets are mutable (you can .add() or .remove() items). Because they can change, they are unhashable and cannot be used as dictionary keys or stored inside other sets.

The frozenset is an immutable version of a set. Once created, it can never change.

frozenset_demo.py

# A set of sets?
# nested = {{1, 2}, {3, 4}} # Raises TypeError

# Using frozenset
nested = {frozenset([1, 2]), frozenset([3, 4])} # This works!

---

4. Under the Hood: The O(1) Guarantee

Sets are essentially Dictionaries without values.

When you ask if "alice" in users, Python doesn’t look through the set one by one. It hashes the string “alice,” calculates its memory location, and checks if that slot is filled.

• List Search: $O(n)$ (Slows down as data grows).
• Set Search: $O(1)$ (Stays instant regardless of data size).

Performance Rule

If you are frequently checking for membership (e.g., if item in collection) and you have more than 10-20 items, you should almost always be using a Set instead of a List.

---

5. Summary Table: Set vs. List

Feature	List	Set
Ordered	Yes	No
Duplicates	Allowed	Forbidden
Search Speed	$O(n)$ (Linear)	$O(1)$ (Constant)
Syntax	[1, 2, 3]	{1, 2, 3}

---

6. Practical Example: Permission Filtering

Imagine you have a list of all possible “tags” for a blog post, and you want to ensure the user only uses valid ones.

tag_validator.py

VALID_TAGS = {"python", "tutorial", "coding", "starlight"}
user_input = ["python", "java", "tutorial"]

# Use intersection to find valid tags provided by the user
valid_entries = VALID_TAGS.intersection(user_input)

# Use difference to find which tags were invalid
invalid_entries = set(user_input) - VALID_TAGS

print(f"Accepted: {valid_entries}")
print(f"Rejected: {invalid_entries}")