Insiemi — una collezione senza duplicati

Il problema che stiamo risolvendo

Le vendite di un giorno arrivano in una lista, una voce per vendita:

sold = ["pen", "bag", "pen", "ink", "pen"]

La domanda: quanti prodotti diversi sono stati venduti? len(sold) dice cinque, ma quello è il numero delle vendite. I prodotti distinti erano tre.

I capitoli precedenti ce la fanno — parti da una lista vuota e, per ogni elemento, controlla if item not in unique: prima di aggiungerlo. Sei righe, e funziona.

Ma se la domanda è "quali prodotti sono stati venduti sia lunedì sia martedì?" servono due cicli annidati. "Solo lunedì?" — un altro ancora. Queste domande sono abbastanza comuni da avere una loro branca della matematica, e in Python quella matematica si può scrivere direttamente.

Un insieme è il contenitore giusto: non contiene duplicati, e risponde "in entrambi", "in uno ma non nell'altro" con un solo carattere.

Alla fine di questo capitolo sarai in grado di

• Costruire un insieme e togliere i duplicati da una lista
• Confrontare due insiemi con |, &, - e ^
• Spiegare perché {} non è un insieme vuoto
• Sapere che un insieme non ha ordine, e quando conta
• Scrivere il pattern che toglie i duplicati mantenendo l'ordine

Prerequisiti: Dizionari — coppie di chiave e valore.

Un insieme — una collezione senza duplicati

sold = ["pen", "bag", "pen", "ink", "pen"]

unique = set(sold)
print(sorted(unique))
print(len(unique))

['bag', 'ink', 'pen']
3

set(...) prende una lista e butta via i duplicati. Tre pen diventano uno.

Nota il sorted() attorno alla stampa, anch'esso voluto — il motivo arriva a breve.

Puoi anche scriverne uno direttamente, con le parentesi graffe:

letters = {"a", "b", "a"}
print(sorted(letters))
print(len(letters))

['a', 'b']
2

Il secondo "a" è svanito in silenzio. Nessun errore — un insieme non ha il concetto della stessa cosa che compare due volte.

{} non è un insieme vuoto

not_a_set = {}
real_set = set()

print(type(not_a_set))
print(type(real_set))

<class 'dict'>
<class 'set'>

Le parentesi graffe sono nate per i dizionari, quindi una {} vuota è rimasta un dizionario. Per un insieme vuoto devi scrivere set().

L'errore resta zitto all'inizio: parti con {}, chiama .add() e ottieni un AttributeError che fa sembrare che il problema sia add.

Non c'è ordine

Questa è la limitazione più importante di un insieme, e la sua proprietà più fraintesa.

Le cose in un insieme non hanno ordine. Non ci sono indici e non ci sono slice:

tags = {"new", "sale"}
print(tags[0])

TypeError: 'set' object is not subscriptable

E l'ordine che vedi quando ne stampi uno non è affidabile — esegui lo stesso programma due volte e può cambiare. Per questo ogni esempio di questo capitolo ordina prima di stampare: ciò che vedi stampando un insieme direttamente non è garantito che sia ciò che vedrai la volta successiva.

Il modo più breve per togliere i duplicati da una lista è list(set(sold)), e butta via l'ordine originale. Quando l'ordine conta, affianca un insieme e una lista:

sold = ["pen", "bag", "pen", "ink", "bag"]
seen = set()
unique = []

for item in sold:
    if item not in seen:
        seen.add(item)
        unique.append(item)

print(unique)

['pen', 'bag', 'ink']

La lista tiene l'ordine e l'insieme ricorda ciò che è già passato. Quella coppia è un pattern molto comune.

Aggiungere e rimuovere

tags = {"new"}

tags.add("sale")
tags.add("new")
print(sorted(tags))

tags.discard("gone")
tags.remove("sale")
print(sorted(tags))

['new', 'sale']
['new']

add mette una cosa dentro — e se c'è già, non succede nulla e nessuno si lamenta. L'append di una lista avrebbe fatto una seconda copia; un insieme no.

La rimozione ha due forme, e la differenza è utile:

tags = {"new"}
tags.remove("gone")

KeyError: 'gone'

remove si ferma quando non trova la cosa; discard fa come se nulla fosse. Se la cosa ci deve essere, scrivi remove così la sua assenza viene colta.

Confrontare due insiemi

È qui che gli insiemi sono davvero utili:

monday = {"rafi", "ahmed", "bilal"}
tuesday = {"ahmed", "dia"}

print(sorted(monday | tuesday))
print(sorted(monday & tuesday))
print(sorted(monday - tuesday))
print(sorted(monday ^ tuesday))

['ahmed', 'bilal', 'dia', 'rafi']
['ahmed']
['bilal', 'rafi']
['bilal', 'dia', 'rafi']

Quattro simboli, quattro domande:

• | — in uno dei due (unione). Tutti quelli che sono venuti nell'arco dei due giorni.
• & — in entrambi (intersezione). Quelli venuti in entrambi i giorni.
• - — nel primo ma non nel secondo (differenza). Quelli venuti solo lunedì.
• ^ — in esattamente uno (differenza simmetrica). Quelli venuti in un giorno ma non in entrambi.

Nota che - tiene conto dell'ordine: monday - tuesday e tuesday - monday danno risposte diverse. Gli altri tre si leggono allo stesso modo in entrambe le direzioni.

Scrivere quei quattro con i cicli richiederebbe diverse righe ciascuno, con buone probabilità di sbagliarne almeno uno.

Cosa può entrare

La stessa regola delle chiavi del dizionario: tutto ciò che metti dentro deve essere immutabile.

s = set()
s.add([1, 2])

TypeError: unhashable type: 'list'

Parola per parola lo stesso messaggio, per lo stesso motivo — anche un insieme usa l'hashing al suo interno. Stringhe, numeri e tuple vanno bene; liste e dizionari no.

Un esempio completo

sales.py:

# Which products sold on both days, and which only on one
monday = ["pen", "bag", "pen", "ink"]
tuesday = ["ink", "bottle", "pen", "ink"]

mon = set(monday)
tue = set(tuesday)

print("Monday sold    :", sorted(mon), f"({len(monday)} sales, {len(mon)} products)")
print("Tuesday sold   :", sorted(tue), f"({len(tuesday)} sales, {len(tue)} products)")
print()
print("Either day     :", sorted(mon | tue))
print("Both days      :", sorted(mon & tue))
print("Monday only    :", sorted(mon - tue))
print("Exactly one day:", sorted(mon ^ tue))
print()
print("Was ink sold on Monday?", "ink" in mon)

Monday sold    : ['bag', 'ink', 'pen'] (4 sales, 3 products)
Tuesday sold   : ['bottle', 'ink', 'pen'] (4 sales, 3 products)

Either day     : ['bag', 'bottle', 'ink', 'pen']
Both days      : ['ink', 'pen']
Monday only    : ['bag']
Exactly one day: ['bag', 'bottle']

Was ink sold on Monday? True

Tre cose da notare.

Le liste originali sono state conservate. len(monday) riporta quattro vendite, len(mon) tre prodotti. Dopo la conversione in insieme il numero delle vendite non c'è più — quindi l'insieme non è un sostituto dei dati, è uno strumento per fare un tipo di domanda su di essi.

sorted() prima di ogni stampa. Senza di esso l'ordine sembrerebbe arbitrario, e potrebbe cambiare da un'esecuzione all'altra.

Dice "ink" in mon, non "ink" in monday. Entrambi danno True, ma cercare in un insieme è più veloce che cercare in una lista — in una lista Python confronta un elemento alla volta, in un insieme calcola l'hash e va dritto al posto. Con quattro cose non significa nulla; con quarantamila sì.

Quando qualcosa va storto

AttributeError: 'dict' object has no attribute 'add' Qualcuno ha scritto s = {} pensando a un insieme, ma quello è un dizionario vuoto. Scrivi s = set().

TypeError: 'set' object is not subscriptable Qualcuno ha scritto s[0]. Un insieme non ha ordine, quindi non ha indici. Se ti serve un elemento in particolare, probabilmente volevi una lista o un dizionario; altrimenti sorted(s) ti dà una lista.

KeyError: 'gone' A remove è stato chiesto di togliere qualcosa che l'insieme non contiene. Se entrambi gli stati sono normali, usa discard.

TypeError: unhashable type: 'list' Un tentativo di mettere una lista in un insieme. Convertila con tuple(...).

Dopo list(set(...)) l'ordine è venuto sballato È normale; gli insiemi non hanno ordine. Se ti serve, usa il pattern seen sopra, oppure sorted().

Ho confrontato due insiemi con == e ho ottenuto True nonostante l'ordine diverso Giustamente. Due insiemi sono uguali quando contengono le stesse cose — l'ordine non c'entra. [1, 2] == [2, 1] è False per le liste; {1, 2} == {2, 1} è True per gli insiemi.

Tocca a te

Scrivi un file chiamato visitors.py con tre liste di visitatori, una per giorno, in cui alcuni nomi compaiono in più di un giorno.

Poi stampa:

1. Quante visite ogni giorno, e quante persone distinte
2. Quante persone distinte in tutti e tre i giorni
3. Le persone venute in tutti e tre i giorni
4. Le persone venute solo il primo giorno
5. Le persone venute in esattamente uno dei primi due giorni

Poi due esperimenti:

• Togli i duplicati in due modi — list(set(...)) e il pattern seen sopra — e stampa i due risultati affiancati. Qual è la differenza?
• Prova a creare un insieme vuoto con {} e a chiamare .add() su di esso. Quale errore torna indietro, e quale tipo di oggetto indica il messaggio?

Il secondo è piccolo, e vederlo una volta con i tuoi occhi significa che quell'errore non ti costerà mai più dieci minuti.