Frozensets

8.2.8. Frozensets#

A frozenset is an immutable version of a set. Once created, elements cannot be added or removed. This is useful when, for example, you need to protect data from modification, to use set as dict key or set element, or for graph edges and combinations.

import sys
from pathlib import Path

# Find project root by looking for _config.yml
current = Path.cwd()
for parent in [current, *current.parents]:
    if (parent / '_config.yml').exists():
        project_root = parent
        break
else:
    project_root = Path.cwd().parent.parent

# Add project root to path
sys.path.insert(0, str(project_root))

# Import shared teaching helpers and cell magics
from shared import thinkpython, diagram, jupyturtle, structshape
from shared.download import download

%%expect AttributeError
fs = frozenset({1, 2, 3})
fs.add(4)     # AttributeError — frozensets are immutable

AttributeError: 'frozenset' object has no attribute 'add'

8.2.8.1. Creating a frozenset#

The syntax for creating a frozenset is:

frozenset()            # empty frozenset
frozenset(iterable)    # from any iterable (list, set, string, etc.)

fs = frozenset([1, 2, 3])
print(fs)                   # frozenset({1, 2, 3})
fs = frozenset("hello")
print(fs)                   # element order may vary

frozenset({1, 2, 3})
frozenset({'e', 'o', 'l', 'h'})

8.2.8.2. Why use a frozenset?#

Because it is immutable, a frozenset is hashable, which means it can be:

used as a dictionary key, or
stored inside another set.

# As a dict key
d = {frozenset({1, 2}): "pair"}

# Inside a set
s = {frozenset({1, 2}), frozenset({3, 4})}

Feature	set	frozenset
Mutable	Yes	No
Hashable	No	Yes
Can be dict key	No	Yes
Set operations	All	Non-mutating only

8.2.8.3. Set Performance#

When you store a key in a dictionary or an element in a set, Python calls hash() on it to compute an integer, then uses that integer to determine where to store the value in memory. This is called a hash table.

The benefit is that lookups are usually O(1) on average: Python jumps directly to a bucket via hash instead of scanning the whole collection. In the worst case (many collisions), lookup can degrade toward O(n).

# O(n) — scans the entire list
"apple" in ["apple", "banana", "cherry"]

# Average O(1) — jumps directly via hash bucket
"apple" in {"apple", "banana", "cherry"}

True

O(n) and O(1) come from Big O notation, which describes how the speed of an operation scales with the size of the data. The full treatment of Big O comes in the Algorithms chapter, where sorting and searching will be covered.

For now, just know that:

Average O(1): hash-table lookups in dict/set are constant time on average, because Python uses the hash to jump to a bucket.
Worst-case O(n): if many keys collide into the same bucket, Python may need to scan multiple entries.
O(n): linear time. The operation gets slower as the collection grows. A list search is O(n) because Python checks each element one by one until it finds a match:

d = {"apple": 1, "banana": 2, "cherry": 3}
d["apple"]   # same speed whether dict has 3 or 3 million items

"apple" in ["apple", "banana", "cherry"]  # checks up to n items

True

In short,

O(1) is like looking up a word in a dictionary: you go directly to the page
O(n) is like finding a word in a novel: you read until you find it

You already saw this in the dictionary section, and the same idea applies here:

O(1) means near-constant lookup time on average (key in dict, item in set).
O(n) means linear time, where Python may scan through many elements (item in list).

So for membership checks, sets are usually much faster than lists as data grows.

8.2.8.4. Performance Demo#

This benchmark mirrors the dictionary example: same data size, worst-case target (n - 1), and timing for membership checks.

import time

n = 1_000_000
big_list = list(range(n))
big_set = set(range(n))
target = n - 1                  # worst case for linear list search

# O(n): list search scans until it finds target
start = time.perf_counter()     # time.perf_counter() is better for benchmarking code
result = target in big_list
list_time = time.perf_counter() - start

# Average O(1): set lookup jumps to hash bucket
start = time.perf_counter()
result = target in big_set
set_time = time.perf_counter() - start

print(f"List lookup (O(n)): {list_time:.6f} s")
print(f"Set lookup (avg O(1)): {set_time:.6f} s")
print(f"Set was ~{list_time / set_time:.0f}x faster")

List lookup (O(n)): 0.004151 s
Set lookup (avg O(1)): 0.000016 s
Set was ~254x faster

8.2.8.5. Set Comprehensions#

A set comprehension builds a set from an expression, using the same syntax as a list comprehension but with curly braces {}. Because the result is a set, duplicates are automatically discarded.

The syntax for creating sets is:

{expression for item in iterable}
{expression for item in iterable if condition}

# Create a set of squares
square_set = {x**2 for x in range(-3, 4)}
print("Square set:", square_set)

# Remove duplicates and transform
sentence = "the quick brown fox jumps over the lazy dog"
unique_lengths = {len(word) for word in sentence.split()}
print("Unique word lengths:", unique_lengths)

# Filter vowels
vowels = {char.lower() for char in "Hello World" if char.lower() in 'aeiou'}
print("Vowels found:", vowels)

Square set: {0, 9, 4, 1}
Unique word lengths: {3, 4, 5}
Vowels found: {'e', 'o'}

### Exercise: Set Comprehension Practice
# 1. From nums = [1, 2, 2, 3, 4, 4, 5], build a set of squared values.
# 2. From text = "apple banana apple cherry", build a set of unique word lengths.
# 3. Print both sets.
### Your code starts here.




### Your code ends here.

Squares: {1, 4, 9, 16, 25}
Unique lengths: {5, 6}

8.2.8.6. Comparing with `dict` Comprehension#

# Set comprehension — curly braces, no colon
{x**2 for x in range(5)}

# Dict comprehension — curly braces WITH colon
{x: x**2 for x in range(5)}

{0: 0, 1: 1, 2: 4, 3: 9, 4: 16}