Sets

A set is a collection of unique, unordered elements. Three superpowers:

1. Automatic deduplication: adding the same element twice has no effect.
2. O(1) membership test: x in s is extremely fast even with millions of elements (it's hash-based, like dicts).
3. Set operations: union, intersection, difference, symmetric difference.

Creating a set

vuoto = set()           # ATTENZIONE: {} è un dict vuoto, non un set!
numeri = {1, 2, 3}
da_lista = set([1, 1, 2, 3, 3, 3])   # {1, 2, 3}

Braces alone {} create an empty dictionary, not a set: for an empty set you need set().

Modifying a set

s = {1, 2, 3}
s.add(4)         # {1, 2, 3, 4}
s.add(1)         # nessun effetto (già presente)
s.discard(99)    # rimuove se presente, silenzioso altrimenti
s.remove(2)      # rimuove o solleva KeyError

Set operations

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

a | b    # {1, 2, 3, 4, 5, 6}     unione
a & b    # {3, 4}                  intersezione
a - b    # {1, 2}                  differenza (in a ma non in b)
a ^ b    # {1, 2, 5, 6}            differenza simmetrica (xor)

There are also method forms (a.union(b), a.intersection(b), …) which in addition accept any iterable, not only sets.

Membership test

parole = {"ciao", "mondo", "python"}
"ciao" in parole       # True   O(1)
"java" not in parole   # True

For comparison: searching with in inside a list is O(n) and on long lists it is much slower.

Frozen set: the immutable version

frozenset({1, 2, 3}) is the hashable version: it can be a dict key or an element of another set.

Set operations and performance

Sets are implemented as hash tables, which makes membership testing (x in my_set) extremely fast: it runs in constant time O(1), unlike lists where searching takes linear time O(n). Additionally, they support algebraic operations like union (|), intersection (&), and difference (-).

Try it

Review exercise

Additional challenge