Set

Un set è una collezione di elementi unici e non ordinati. Tre superpoteri:

1. Deduplicazione automatica: aggiungere lo stesso elemento due volte non ha effetto.
2. Test di appartenenza in O(1): x in s è velocissimo anche con milioni di elementi (è basato su hash, come i dict).
3. Operazioni insiemistiche: unione, intersezione, differenza, differenza simmetrica.

Creare un 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}

Le graffe da sole {} creano un dizionario vuoto, non un set: per il set vuoto serve set().

Modificare un 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

Operazioni insiemistiche

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)

Esistono anche le forme metodo (a.union(b), a.intersection(b), …) che in più accettano qualunque iterabile, non solo set.

Test di appartenenza

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

A confronto: cercare in dentro una list è O(n) e su liste lunghe è molto più lento.

Frozen set: la versione immutabile

frozenset({1, 2, 3}) è la versione hashable: può essere chiave di dict o elemento di un altro set.

Set operazione e prestazioni

I set sono implementati tramite tabelle hash, il che rende la verifica di appartenenza (x in mio_set) estremamente rapida: richiede tempo costante O(1), a differenza delle liste dove la ricerca richiede tempo lineare O(n). Inoltre, supportano operazioni algebriche come l'unione (|), l'intersezione (&) e la differenza (-).

Prova tu

Esercizio di ripasso

Sfida aggiuntiva