Dizionari e insiemi in Python

Gli ADT mappa e insieme

Definizione (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.

Esempio. Con voti = {"Ada": 30, "Alan": 27}, voti["Ada"] = 28 aggiorna la coppia senza duplicare la chiave; {3, 1, 4, 1, 5} vale {1, 3, 4, 5}.

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

Definizione (dict: operazioni principali)

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)

Esempio. Con voti = {"Ada": 28, "Alan": 27}: voti.get("Bob", 0) restituisce 0, "Ada" in voti vale True e voti["Bob"] solleva KeyError.

Iterazione

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

Proprietà (chiavi hashable). 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.

Esempio. {(1, 2): "a"}[(1, 2)] restituisce 'a', mentre {[1]: 2} solleva TypeError.

Schemi tipici

Definizione (schemi tipici con i dizionari)

# 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()}

Esempio. Sulle parole a b a, freq[parola] = freq.get(parola, 0) + 1 dà {'a': 2, 'b': 1}; Counter("mississippi").most_common(2) dà [('i', 4), ('s', 4)].

Con collections:

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

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

Definizione (operazioni sugli insiemi)

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)

Esempio. Con a = {1, 2, 3} e b = {3, 4}: a | b è {1, 2, 3, 4}, a & b è {3}, a - b è {1, 2} e a ^ b è {1, 2, 4}.

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.

# 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

Proprietà (dict e set come 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)$ 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(1)$ medio
ordine e indici	sì	no (il dict mantiene l'ordine di inserimento)
duplicati	ammessi	no (chiavi uniche)

Esempio. Con un milione di elementi x in lista può scorrerli tutti, mentre x in set(lista) costa in media $O(1)$; una lista come chiave solleva TypeError.

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.