Sets and frozensets for membership and maths

Proving that a number is not in a list of 100,000 takes 100,000 comparisons, because a list can only be checked item by item. A set, such as {"tea", "rice"}, is an unordered collection of distinct values that answers the same question by looking in one place, so its membership test stays fast however big it grows. Adding a value that is already there changes nothing, so turning a list into a set removes its duplicates, and sets do the arithmetic of groups: union, intersection, difference and symmetric difference, written |, &, - and ^.

Below you can watch a list and a set search the same five seat numbers, sort the members of two clubs into regions, see why a set of strings prints in another order on each run, and remove repeats from a list while keeping its order. frozenset, the set that cannot change, closes the lesson.

A set keeps one copy of each value

A visitor log of six entries, [3, 1, 3, 2, 1, 3], holds only three different visitors, and set(visits) finds them in one step, because a set keeps each value once. Braces with values make a set too, and repeats vanish as it is built:

empty = set()  # the only way to write an empty set ...
not_a_set = {}  # ... because {} is an empty dictionary
print(type(empty).__name__, type(not_a_set).__name__)

tags = {"python", "lists", "python"}  # the repeat disappears
tags.add("sets")
tags.add("lists")  # already there: nothing changes
tags.discard("java")  # discard() is quiet about a missing item
print(len(tags), "sets" in tags, sorted(tags))

visits = [3, 1, 3, 2, 1, 3]
print(sorted(set(visits)), len(set(visits)), "different visitors")

tags.remove("java")  # remove() raises KeyError for a missing item

set dict
3 True ['lists', 'python', 'sets']
[1, 2, 3] 3 different visitors

Traceback (most recent call last):
  File "set_basics.py", line 14, in <module>
    tags.remove("java")  # remove() raises KeyError for a missing item
    ~~~~~~~~~~~^^^^^^^^
KeyError: 'java'

The empty set has to be written set(), because {} was taken long ago by the empty dictionary. add(x) adds one value and does nothing when it is already there. discard(x) removes a value if it is present, while remove(x) insists on it and raises KeyError, as the last line shows. len() counts the distinct values, so len(set(visits)) answers “how many different visitors?” in one expression. Press Edit, change the last line to tags.discard("java") and run it again: the program now ends without an error.

Sets have no positions, so there is no s[0] and no slicing. To print one in a predictable order, sort it, as the examples in this lesson do, apart from the one that shows why: sorted(s) returns a sorted list. Like the keys of a dictionary, the items of a set must be hashablehashable: A value that can be a dict key or a set item, because its hash never changes while it exists: numbers, strings and tuples of hashable values are hashable; lists, dicts and sets are not. More in “functools: cache, partial, reduce and more”; the next sections show why.

Union, intersection and difference pick regions of two sets

Two clubs that share some members show all four operations:

chess = {"Asha", "Ravi", "Mei", "Dev"}
drama = {"Mei", "Kiran", "Asha", "Zoya"}

print(sorted(chess & drama))  # in both clubs: intersection
print(sorted(chess | drama))  # in either club: union
print(sorted(chess - drama))  # in chess but not drama: difference
print(sorted(chess ^ drama))  # in exactly one club: symmetric difference

print({"Asha", "Mei"} <= chess, chess.isdisjoint({"Zoya", "Bilal"}))
print(sorted(chess.union(["Bilal", "Asha"])))  # methods take any iterable

['Asha', 'Mei']
['Asha', 'Dev', 'Kiran', 'Mei', 'Ravi', 'Zoya']
['Dev', 'Ravi']
['Dev', 'Kiran', 'Ravi', 'Zoya']
True True
['Asha', 'Bilal', 'Dev', 'Mei', 'Ravi']

Every student of either club falls in one of three regions: chess only, both clubs, or drama only. The diagram sorts the six students into those regions, and each operator keeps some of them:

• a | b, the union, holds everything in either set.
• a & b, the intersection, holds what is in both.
• a - b, the difference, holds what is in a but not in b; b - a is a different set.
• a ^ b, the symmetric differencesymmetric difference: The items that are in exactly one of two sets, a ^ b: everything in either set except what the two share. {1, 2} ^ {2, 3} is {1, 3}., holds what is in exactly one of them.

a <= b asks whether every item of a is also in b, which makes a a subsetsubset: A set whose every item is also in another set. a <= b tests it; a < b also needs b to hold something more, which makes a a proper subset. of b (< also requires b to have something more), and a.isdisjoint(b) whether the two share nothing. The operators need sets on both sides: chess | ["Bilal"] raises TypeError. The named methods, union(), intersection(), difference(), symmetric_difference(), issubset() and the others, accept any iterable, which is why chess.union(["Bilal", "Asha"]) works. Each operator also has an in-place form, such as a |= b, that changes a instead of building a new set. Press Edit, add print(sorted(drama - chess)) and run it: Kiran and Zoya, the drama-only region.

A set finds a value without looking through every item

Take five booked seat numbers, [12, 30, 7, 25, 41], and ask whether seat 19 is among them. A list has no shortcut: 19 in seats compares 19 with each item in turn, and only after the last one can it say no. Step through it:

Five comparisons for five seats, and for a list of 100,000 it would be 100,000. A set stores its items in a hash tablehash table: A table of slots in which each key is kept at a place worked out from its hash, so a lookup looks in one slot or a few instead of comparing every key. Python's dict and set are hash tables. More in “Dictionaries: keys, values and views”, as a dictionary stores its keys. To answer 19 in booked, for the set booked = set(seats), Python computes the hashhash: The whole number hash() works out from a value. Values that are equal have equal hashes, and a dict or a set uses the hash to decide where to look, then compares the keys it finds there with ==. More in “Dictionaries: keys, values and views” of 19 and looks only where 19 would be stored. The next figure is a small model of such a table, the textbook kind with 8 slots: a whole number k goes to slot k mod 8, and when that slot is taken, to the next one. Step through the five seats going in, then the two lookups:

41 wanted slot 1, which 25 had taken, so it went into slot 2, and finding it took two looks. Finding that 19 is missing took one: slot 3 was empty, so 19 cannot be anywhere else. Python’s dictionaries and sets are resizable hash tables, and the time a test takes depends on how many values share the places it looks in, not on how many values the set holds. This program measures it on 100,000 numbers:

from timeit import timeit

n = 100_000
as_list = list(range(n))
as_set = set(as_list)
missing = -1  # not there: the list must look at every item to be sure

for name, items, runs in (("list", as_list, 200), ("set", as_set, 200_000)):
    seconds = timeit("missing in items", globals={"missing": missing, "items": items}, number=runs)
    print(f"{name}: {seconds / runs * 1e6:.3f} microseconds per lookup of a missing value")

list: 613.981 microseconds per lookup of a missing value
set: 0.013 microseconds per lookup of a missing value

The value is missing on purpose, the worst case for the list, which had to look at all 100,000 numbers on every lookup. The set answered in a small fraction of a microsecond, tens of thousands of times faster. The comparison favours the set more the longer the list gets, but two things limit it. Building the set is itself a pass over the list, so for a single lookup the list scan is just as good; the set pays off when you look up many values. And for a handful of items both are so fast that the difference does not matter.

A set has no order you can rely on

The order in which a set prints comes from the hashes of its items, and the hashes of strings change from one run of Python to the next. Python picks a random salt for string hashes when it starts, a protection against input crafted to make every hash collide; this is called hash randomisationhash randomisation: The random value Python mixes into the hashes of str and bytes objects, chosen afresh when each process starts, so a set of strings can come out in another order on each run. PYTHONHASHSEED fixes it.. This program starts a new Python three times, each time with a fixed salt chosen through the PYTHONHASHSEED environment variable, and prints the same set:

import os
import subprocess
import sys

program = 'print({"mango", "apple", "kiwi", "fig", "plum"}); print({16, 1, 8})'

for seed in ("1", "2", "3"):
    env = dict(os.environ, PYTHONHASHSEED=seed)  # fix the hash seed of a new Python
    run = subprocess.run([sys.executable, "-c", program], env=env, capture_output=True, text=True)
    first, second = run.stdout.splitlines()
    print(f"seed {seed}: {first}  {second}")

print("sorted:", sorted({"mango", "apple", "kiwi", "fig", "plum"}), sorted({16, 1, 8}))

seed 1: {'mango', 'kiwi', 'plum', 'fig', 'apple'}  {16, 1, 8}
seed 2: {'fig', 'plum', 'mango', 'apple', 'kiwi'}  {16, 1, 8}
seed 3: {'mango', 'fig', 'kiwi', 'apple', 'plum'}  {16, 1, 8}
sorted: ['apple', 'fig', 'kiwi', 'mango', 'plum'] [1, 8, 16]

The five fruits come out in a different order each time, while the set of numbers prints the same way in every run, because the hash of a small integer is the integer itself. That order is still not sorted: {16, 1, 8} prints as it was written, not as {1, 8, 16}. Two rules follow. Sort a set before you show it, and compare sets with ==, which ignores order, never by comparing their printed text. Setting PYTHONHASHSEED to a fixed value is a debugging aid, not a fix.

A dictionary removes duplicates and keeps the first-seen order

set(items) removes duplicates but forgets the order of the items. When the first-seen order matters, use a dictionary, which keeps insertion order, and take its keys. Step through dict.fromkeys() on a list of five emails with two repeats:

A repeat finds its email already a key and changes nothing, so every key keeps the place where its email first appeared. The program does the same in one line, next to the set version for comparison:

emails = ["b@x.org", "a@x.org", "b@x.org", "c@x.org", "a@x.org"]

print(list(dict.fromkeys(emails)))  # first-seen order kept
print(sorted(set(emails)))  # a set keeps no order, so sort it to show it
print(len(emails) - len(set(emails)), "repeats")

rows = [["a", 1], ["a", 1]]
print(set(rows))  # lists cannot be set elements

['b@x.org', 'a@x.org', 'c@x.org']
['a@x.org', 'b@x.org', 'c@x.org']
2 repeats

Traceback (most recent call last):
  File "dedupe_order.py", line 8, in <module>
    print(set(rows))  # lists cannot be set elements
          ~~~^^^^^^
TypeError: cannot use 'list' as a set element (unhashable type: 'list')

dict.fromkeys(emails) makes a dictionary whose keys are the emails, each once, in the order they first appeared, and list() turns its keys back into a list. Both ways need hashable items. A list of lists cannot become a set, and Python 3.14 says so plainly: TypeError: cannot use 'list' as a set element (unhashable type: 'list'). Turn each inner list into a tuple first.

frozenset is a set that cannot change, so it can be a key

A set can change, so it is not hashable: it cannot be a dictionary key or an item of another set. frozenset is the immutable version, with every operation that reads a set and none that changes one:

relations = {
    frozenset({"Asha", "Ravi"}): "cousins",
    frozenset({"Mei", "Dev"}): "neighbours",
}
print(relations[frozenset({"Ravi", "Asha"})])  # the order inside does not matter

seen = set()
seen.add(frozenset({"tea", "milk"}))
print(frozenset({"milk", "tea"}) in seen)

letters = frozenset("abc")
print(sorted(letters | {"d"}), type(letters | {"d"}).__name__)

seen.add({"sugar"})  # a plain set cannot go inside a set

cousins
True
['a', 'b', 'c', 'd'] frozenset

Traceback (most recent call last):
  File "frozen.py", line 14, in <module>
    seen.add({"sugar"})  # a plain set cannot go inside a set
    ~~~~~~~~^^^^^^^^^^^
TypeError: cannot use 'set' as a set element (unhashable type: 'set')

A frozenset makes a good key for something that has no order of its own, such as a pair of people: {"Asha", "Ravi"} and {"Ravi", "Asha"} are equal, so both find the same entry. A set of sets must be a set of frozensets, and a plain set inside one fails. Operators between a frozenset and a set return the type of the left-hand operand, so letters | {"d"} is a new frozenset.

Practise: hours that suit everyone, and spotting repeats

The exercise has two small set problems from a timetable: the hours that every person in a group has open, which is an intersection of their calendars, and a test for repeated items, which compares a list with the set made from it. Write each function and run the sample tests; the first hint names the operator to start with:

def common_free_slots(calendars):
    """Hours free in every calendar, as a sorted list."""
    return []


def has_duplicates(xs):
    """True when some item of xs appears more than once."""
    return False

from slots import common_free_slots, has_duplicates


def test_common_slots():
    """finds the hours free in every calendar, sorted"""
    assert common_free_slots([[9, 10, 11, 14], [10, 11, 15], [11, 10, 9]]) == [10, 11]
    assert common_free_slots([[16, 9, 12], [12, 16]]) == [12, 16]


def test_one_person_and_repeats():
    """works for one calendar and for hours listed twice"""
    assert common_free_slots([[14, 9, 14]]) == [9, 14]
    assert common_free_slots([[10, 10], [10]]) == [10]


def test_no_common_slots():
    """returns an empty list when nobody, or not everybody, is free"""
    assert common_free_slots([]) == []
    assert common_free_slots([[9, 10], []]) == []
    assert common_free_slots([[9], [10]]) == []


def test_duplicates():
    """spots repeated items"""
    assert has_duplicates([1, 2, 1]) is True
    assert has_duplicates(["tea", "rice", "tea"]) is True
    assert has_duplicates([1, 2, 3]) is False
    assert has_duplicates(["a", "A"]) is False
    assert has_duplicates([]) is False


def test_unhashable_items():
    """raises TypeError for items a set cannot hold"""
    try:
        has_duplicates([[1], [1]])
    except TypeError:
        return
    raise AssertionError("expected TypeError for a list of lists")

Six ideas, from making a set to frozensets, are in the self-check. It opens with whichever of them your answers so far have shown to be the shakiest, and each choice comes with the reason it is right or wrong:

Interview questions

Fresher · Why is x in a_set usually faster than x in a_list, and when is it not?

A set is a hash table. For x in a_set, Python computes hash(x), goes straight to the slot where x would be and compares only the few items stored there, so the average cost hardly grows with the size of the set. x in a_list compares x with each item in turn and, when x is missing, with every item, so its cost grows with the length of the list. The set loses its edge in three cases: when the collection is tiny and both are fast anyway; when you search only once, because building the set takes a full pass over the list first; and when many items have equal hashes, which makes lookups slow down towards a scan. It also needs hashable items, so a list of lists cannot become a set at all.

Key takeaways

• A set holds distinct, hashable values with no order, set() is the empty set because {} is a dictionary, and remove() raises KeyError for a missing value where add() and discard() never complain.
• |, &, - and ^ give the union, intersection, difference and symmetric difference of two sets, <= tests for a subset, and the named methods also accept lists.
• x in s looks only where the hash of x leads, so it takes about the same time for any size of set, while x in a_list checks the items one by one.
• String hashes are salted per run, so a set of strings can print in another order every time: sort a set before showing it, and compare sets with ==.
• list(dict.fromkeys(items)) removes duplicates and keeps the first-seen order, which set(items) forgets.
• frozenset is hashable and immutable, so it can be a dictionary key or an item of another set.