Salta al contenuto
Note per Studenti Dizionari e insiemi in Python

Dizionari e insiemi in Python

In questa pagina 5

Gli ADT mappa e insieme

  • Mappa (dizionario): associa a ogni chiave un valore; operazioni: inserire/aggiornare una coppia, cercare il valore di una chiave, togliere una chiave, scorrere le coppie.
  • Insieme: collezione senza duplicati e senza ordine; operazioni: aggiungere, togliere, verificare l'appartenenza, unione, intersezione, differenza.

Python li fornisce come tipi predefiniti dict e set (vedi Tipi di dato astrattiUn ADT è definito dalle operazioni e dal loro comportamento, non dalla rappresentazione; interfaccia e implementazione; realizzazione in Python con le classi e in C con header e tipo opaco; esempio di un ADT Frazione.Tipi di dato astratti →).

dict

python
voti = {"Ada": 30, "Alan": 27}
vuoto = {}                            # dizionario vuoto (NON un insieme)
d = dict(a=1, b=2)
quadrati = {x: x * x for x in range(5)}   # dict comprehension

voti["Grace"] = 29        # inserisce
voti["Ada"] = 28          # aggiorna: una chiave compare una volta sola
voti["Ada"]               # 28
voti["Bob"]               # KeyError
voti.get("Bob")           # None
voti.get("Bob", 0)        # 0: valore di default
"Ada" in voti             # True: cerca tra le CHIAVI
del voti["Alan"]
voti.pop("Grace")         # toglie e restituisce 29
len(voti)

Iterazione

python
for nome in voti:                 # chiavi
    ...
for nome, voto in voti.items():   # coppie
    print(nome, voto)
voti.keys(), voti.values()
for nome in sorted(voti):         # in ordine di chiave
    ...

L'ordine di iterazione è quello di inserimento. Non si possono aggiungere o togliere chiavi mentre si scorre il dizionario (RuntimeError).

Chiavi

Le chiavi devono essere hashable (immutabili): int, float, str, tuple di immutabili. Una list non può essere chiave (TypeError: unhashable type); i valori invece possono essere qualsiasi cosa.

Schemi tipici

python
# conteggio delle frequenze
freq = {}
for parola in testo.split():
    freq[parola] = freq.get(parola, 0) + 1

# raggruppamento
per_iniziale = {}
for nome in nomi:
    per_iniziale.setdefault(nome[0], []).append(nome)

# chiave con valore massimo
piu_frequente = max(freq, key=freq.get)

# inversione (valori distinti)
inverso = {v: k for k, v in d.items()}

Con collections:

python
from collections import Counter, defaultdict
Counter("mississippi").most_common(2)   # [('i', 4), ('s', 4)]
gruppi = defaultdict(list)              # valore iniziale automatico: lista vuota
gruppi["a"].append("Ada")

set

python
s = {3, 1, 4, 1, 5}       # {1, 3, 4, 5}: i duplicati spariscono
vuoto = set()             # {} sarebbe un dizionario
unici = set(lista)
s.add(9)
s.remove(3)               # KeyError se manca
s.discard(3)              # nessun errore se manca
4 in s                    # appartenenza: O(1) in media
Operazione Operatore Metodo
unione a | b a.union(b)
intersezione a & b a.intersection(b)
differenza a - b a.difference(b)
differenza simmetrica a ^ b a.symmetric_difference(b)
sottoinsieme a <= b a.issubset(b)

Gli elementi devono essere hashable; frozenset è la versione immutabile (utilizzabile come chiave o elemento di un altro insieme). Un insieme non ha indici: s[0] → TypeError.

python
# elementi comuni a due liste, in tempo lineare
comuni = set(a) & set(b)
# rimuovere i duplicati mantenendo l'ordine
visti, unici = set(), []
for x in lista:
    if x not in visti:
        visti.add(x)
        unici.append(x)

Come funzionano: tabelle hash

dict e set sono tabelle hash: un array di celle in cui la posizione di una chiave è calcolata da hash(chiave) modulo la dimensione dell'array. Ricerca, inserimento e rimozione costano quindi O(1)O(1) in media, indipendentemente dal numero di elementi; due chiavi nella stessa cella (collisione) vengono gestite cercando un'altra cella. Quando la tabella si riempie viene ingrandita e le chiavi ridistribuite (costo ammortizzato, come l'append delle liste).

Per questo le chiavi devono essere immutabili: se una chiave cambiasse dopo l'inserimento, il suo hash cambierebbe e non verrebbe più trovata.

list set / dict
x in ... O(n)O(n) O(1)O(1) medio
ordine e indici sì no (il dict mantiene l'ordine di inserimento)
duplicati ammessi no (chiavi uniche)

Uso nell'analisi dei costi: Complessità computazionaleCosto di un algoritmo in funzione della dimensione dell'input; caso peggiore, migliore e medio; notazione O-grande e classi di crescita; come contare i passi di cicli e ricorsioni; costo delle operazioni Python.Complessità computazionale →.

Errori tipici

  • {} per creare un insieme vuoto.
  • Accedere con d[k] a una chiave che può mancare: usare in, get o defaultdict.
  • Usare una lista come chiave: convertirla in tupla.
  • Aspettarsi un ordine dagli elementi di un set.

Teoria collegata