Come Funzionano Diversamente gli Insiemi

Insiemi: Costruiti per Domande di Appartenenza

Un insieme memorizza elementi unici usando una tecnica chiamata hashing. Quando aggiungi un elemento, il computer calcola un hash (un'impronta numerica) che dice esattamente dove memorizzare quell'elemento.

Quando controlli l'appartenenza, il computer calcola lo stesso hash & salta direttamente al punto giusto. Nessuna scansione.

# A set of pets
pets = {"cat", "dog", "cat", "fish", "dog"}

print(pets)      # {"cat", "dog", "fish"} — duplicates removed
print(len(pets)) # 3 — only unique items

Nota tre differenze dalle liste:

1. Nessun duplicato. "cat" è apparso due volte nell'input ma l'insieme mantiene una sola copia.

2. Nessun ordine garantito. L'insieme potrebbe stampare elementi in qualsiasi disposizione.

3. Nessun accesso per indice. Non puoi scrivere pets[0] — gli insiemi non hanno posizioni.

Il compromesso: perdi ordine & duplicati. Guadagni O(1) test di appartenenza — controllare se un elemento esiste richiede lo stesso tempo se l'insieme ha 5 elementi o 5 milioni.

# Membership check — is "fish" in the set?
if "fish" in pets:    # hash("fish") → jump to bucket → found
    print("found!")   # checked exactly 1 spot, not 4

Insieme vs Lista per Appartenenza

Hai 500 nomi di studenti memorizzati in un insieme anziché in una lista.

students = {"Alex", "Maria", ..., "Zara", ...}  # 500 names
if "Zara" in students:
    print("enrolled")

Confronto Fianco a Fianco

Foglio di Aiuto Operazioni

Usa una lista quando hai bisogno di:

- Elementi in un ordine specifico (una playlist, una ricetta, una coda)

- Accesso per posizione (items[3])

- Duplicati preservati ("cat" appare 3 volte = 3 gatti)

Usa un insieme quando hai bisogno di:

- Controlli di appartenenza veloce ("l'ho già visto?")

- Rimozione automatica dei duplicati

- Nessuna preoccupazione sull'ordine

Usa entrambi quando hai bisogno di ordine E ricerca veloce:

seen = set()     # O(1) membership checks
result = []      # preserves insertion order
for item in data:
    if item not in seen:  # O(1) check
        seen.add(item)    # O(1) add
        result.append(item)  # O(1) append
# Total: O(N) — one pass, each step O(1)

Questo schema "insieme + lista" ti dà il meglio di entrambi: risultati ordinati con rilevamento veloce dei duplicati.

Scegli la Struttura Giusta

Tre problemi. Per ciascuno, decidi: lista, insieme, o entrambi?

1. Devi memorizzare una playlist di canzoni nell'ordine in cui l'utente le ha aggiunte.

2. Devi controllare rapidamente se un nome utente è già stato preso.

3. Devi rimuovere email duplicate da una lista di distribuzione ma mantenerle nell'ordine in cui si sono iscritte.

Il Problema della Deduplicazione

Problema: Rimuovi i Duplicati, Preserva l'Ordine

Ricevi una lista di iscrizioni email. Alcuni si sono iscritti due volte. Devi inviare una email per persona, nell'ordine in cui si sono iscritti per la prima volta.

Tentativo 1: solo lista (lento)

signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
unique = []
for email in signups:
    if email not in unique:  # O(N) scan of unique list
        unique.append(email)
# Works! But: O(N) check × N items = O(N²)

Con 100 iscrizioni, questo fa ~5.000 controlli. Con 10.000 iscrizioni: ~50.000.000 controlli.

Tentativo 2: insieme + lista (veloce)

signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
seen = set()
unique = []
for email in signups:
    if email not in seen:   # O(1) hash lookup
        seen.add(email)     # O(1) add to set
        unique.append(email) # O(1) append to list
# O(1) check × N items = O(N)

Stesso risultato. Stesso ordine. Ma: 10.000 iscrizioni ora richiedono ~10.000 controlli invece di ~50.000.000.

Calcola l'Accelerazione

La versione solo lista funziona a O(N²). La versione insieme+lista funziona a O(N).

Hai 10.000 iscrizioni email da deduplicare.

Trovare Elementi Comuni

Problema: Trova Elementi in Entrambe le Liste

Hai due elenchi di classe. Devi trovare gli studenti iscritti a entrambe le classi.

Approccio lento: cicli annidati O(N × M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b = ["Bob", "Diana", "Eve", "Frank"]
both = []
for student in class_a:        # N iterations
    if student in class_b:     # M scans each time
        both.append(student)
# O(N × M) — each student scanned against all of class_b

Approccio veloce: converti una lista in insieme O(N + M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b_set = set(class_b)     # O(M) to build
both = []
for student in class_a:        # N iterations
    if student in class_b_set: # O(1) each time
        both.append(student)
# O(N + M) — build the set once, check N times at O(1) each

O ancora più semplice usando l'intersezione di insiemi integrata di Python:

both = set(class_a) & set(class_b)  # O(N + M)

L'operatore & trova tutti gli elementi che compaiono in entrambi gli insiemi.

Riscrivi per Velocità

Una scuola ha due club con 200 membri ciascuno. Questo codice trova gli studenti in entrambi i club:

chess_club = [...]   # 200 names
art_club = [...]     # 200 names
both_clubs = []
for student in chess_club:
    if student in art_club:
        both_clubs.append(student)

Il Tuo Framework Decisionale

Il Tuo Framework Decisionale della Struttura Dati

Ogni volta che scrivi codice che memorizza una collezione di elementi, chiedi:

1. Ho bisogno che gli elementi siano in ordine? → lista

2. Ho bisogno di controlli di appartenenza veloce? → insieme

3. Ho bisogno sia di ordine CHE di controlli veloce? → insieme + lista insieme

4. Ho bisogno dei duplicati? → lista (gli insiemi scartano i duplicati)

---

L'intuizione chiave da questa lezione: lo stesso programma, risolvendo lo stesso problema, può funzionare da 1.000× a 1.000.000× più veloce solo scegliendo la struttura dati giusta. Nessun trucco intelligente. Nessuna matematica complicata. Solo chiedere: quali operazioni fa il mio codice più spesso? Poi scegli la struttura dove quelle operazioni costano O(1) anziché O(N).

Questa lezione ha coperto liste & insiemi. Altre strutture dati esistono (dizionari, alberi, heap) che risolvono altri problemi. Il framework decisionale rimane lo stesso: capisci le tue operazioni, poi scegli la struttura che le rende economiche.

---

Vuoi approfondire? La nostra lezione su Big O copre tassi di crescita & calcoli di scaling in dettaglio. Vedi Big O: How Fast Is Fast Enough?. Il nostro corso unhamming copre il difetto del mondo reale (MOAD-0001) dove esattamente questa correzione da lista a insieme ha prodotto un'accelerazione di 1.000× nel software di produzione. Vedi The Missing Chapter: Algorithmic Complexity.

Esegui il Debug di Questo Codice

Uno studente ha scritto questo codice per contare quante parole uniche appaiono in un libro:

words = book.split()           # list of all words
unique_count = 0
checked = []
for word in words:             # N words
    if word not in checked:    # scans checked list
        checked.append(word)
        unique_count += 1
print(unique_count)

Il libro ha 100.000 parole.