Buy this book at Amazon.com

Chapter 11  Dizionari

Questo capitolo illustra un altro tipo predefinito chiamato dizionario. I dizionari sono una delle migliori caratteristiche di Python; sono i mattoni che costituiscono molti eleganti ed efficienti algoritmi.

11.1  Un dizionario è una mappatura

Un dizionario è simile ad una lista, ma è più generico. Infatti, mentre in una lista gli indici devono essere numeri interi, in un dizionario possono essere (quasi) di ogni tipo.

Un dizionario contiene una raccolta di indici, chiamati chiavi, e una raccolta di valori. Ciascuna chiave è associata ad un unico valore. L’associazione tra una chiave e un valore è detta coppia chiave-valore o anche elemento.

In linguaggio matematico, un dizionario rappresenta una relazione di corrispondenza, o mappatura, da una chiave a un valore, e si può dire pertanto che ogni chiave “mappa in” un valore.

Come esempio, costruiamo un dizionario che trasforma le parole dall’inglese all’italiano, quindi chiavi e valori saranno tutte delle stringhe.

La funzione dict crea un nuovo dizionario privo di elementi. Siccome dict è il nome di una funzione predefinita, è meglio evitare di usarlo come nome di variabile.

>>> eng2it = dict()
>>> eng2it
{}

Le parentesi graffe, {}, rappresentano un dizionario vuoto. Per aggiungere elementi al dizionario, usate le parentesi quadre:

>>> eng2it['one'] = 'uno'

Questa riga crea un elemento che contiene una corrispondenza dalla chiave 'one' al valore 'uno'. Se stampiamo di nuovo il dizionario, vedremo ora una coppia chiave-valore separati da due punti:

>>> eng2it
{'one': 'uno'}

Questo formato di output può essere anche usato per gli inserimenti. Ad esempio potete creare un nuovo dizionario con tre elementi:

>>> eng2it = {'one': 'uno', 'two': 'due', 'three': 'tre'}

Se stampate ancora una volta eng2it, avrete una sorpresa:

>>> eng2it
{'one': 'uno', 'three': 'tre', 'two': 'due'}

L’ordine delle coppie chiave-valore non è necessariamente lo stesso. Se scrivete lo stesso esempio nel vostro computer, potreste ottenere un altro risultato ancora. In genere, l’ordine degli elementi di un dizionario è imprevedibile.

Ma questo non è un problema, perché gli elementi di un dizionario non sono indicizzati con degli indici numerici. Infatti, per cercare un valore si usano invece le chiavi:

>>> eng2it['two']
'due'

La chiave 'two' corrisponde correttamente al valore 'due' e l’ordine degli elementi nel dizionario è ininfluente.

Se la chiave non è contenuta nel dizionario, viene generato un errore::

>>> print(eng2it['four'])
KeyError: 'four'

La funzione len è applicabile ai dizionari, e restituisce il numero di coppie chiave-valore:

>>> len(eng2it)
3

Anche l’operatore in funziona con i dizionari: informa se qualcosa compare come chiave nel dizionario (non è condizione sufficiente che sia contenuto come valore).

>>> 'one' in eng2it
True
>>> 'uno' in eng2it
False

Per controllare invece se qualcosa compare come valore, potete usare il metodo values, che restituisce una raccolta dei valori, e quindi usare l’operatore in:

>>> vals = eng2it.values()
>>> 'uno' in vals
True

L’operatore in utilizza algoritmi diversi per liste e dizionari. Per le prime, ne ricerca gli elementi in base all’ordine, come nel Paragrafo 8.6. Se la lista si allunga, anche il tempo di ricerca si allunga in proporzione. Per i secondi, Python usa un algoritmo chiamato tabella hash che ha notevoli proprietà: l’operatore in impiega sempre circa lo stesso tempo, indipendentemente da quanti elementi contiene il dizionario. Rimando la spiegazione di come ciò sia possibile all’Appendice B.4: per capirla, occorre prima leggere qualche altro capitolo.

11.2  Il dizionario come raccolta di contatori

Supponiamo che vi venga data una stringa e che vogliate contare quante volte vi compare ciascuna lettera. Ci sono alcuni modi per farlo:

1. Potete creare 26 variabili, una per lettera dell’alfabeto. Quindi, fare un attraversamento della stringa e per ciascun carattere incrementate il contatore corrispondente, magari usando delle condizioni in serie.
2. Potete creare una lista di 26 elementi, quindi convertire ogni carattere in un numero (usando la funzione predefinita ord), utilizzare il numero come indice e incrementare il contatore corrispondente.
3. Potete creare un dizionario con i caratteri come chiavi e i contatori come valore corrispondente. La prima volta che incontrate un carattere, lo aggiungete come elemento al dizionario. Successivamente, incrementerete il valore dell’elemento esistente.

Ciascuna di queste opzioni esegue lo stesso calcolo, ma lo implementa in modo diverso.

Un’implementazione è un modo per effettuare un’elaborazione. Le implementazioni non sono tutte uguali, alcune sono migliori di altre: per esempio, un vantaggio dell’implementazione con il dizionario è che non serve sapere in anticipo quali lettere ci siano nella stringa e quali no, dobbiamo solo fare spazio per le lettere che compariranno effettivamente.

Ecco come potrebbe essere scritto il codice:

def istogramma(s):
    d = dict()
    for c in s:
        if c not in d:
            d[c] = 1
        else:
            d[c] += 1
    return d

Il nome di questa funzione è istogramma, che è un termine statistico per indicare un insieme di contatori (o frequenze).

La prima riga della funzione crea un dizionario vuoto. Il ciclo for attraversa la stringa. Ad ogni ripetizione, se il carattere c non compare nel dizionario crea un nuovo elemento di chiave c e valore iniziale 1 (dato che incontra questa lettera per la prima volta). Se invece c è già presente, incrementa d[c] di una unità.

Vediamo come funziona:

>>> h = istogramma('brontosauro')
>>> h
{'a': 1, 'b': 1, 'o': 3, 'n': 1, 's': 1, 'r': 2, 'u': 1, 't': 1}

L’istogramma indica che le lettere 'a' e 'b' compaiono una volta, la 'o' tre volte e così via.

I dizionari supportano il metodo get che richiede una chiave e un valore predefinito. Se la chiave è presente nel dizionario, get restituisce il suo valore corrispondente, altrimenti restituisce il valore predefinito. Per esempio:

>>> h = istogramma('a')
>>> h
{'a': 1}
>>> h.get('a', 0)
1
>>> h.get('b', 0)
0

Come esercizio, usate get per scrivere istogramma in modo più compatto. Dovreste riuscire a fare a meno dell’istruzione if.

11.3  Cicli e dizionari

Se usate un dizionario in un ciclo for, quest’ultimo attraversa le chiavi del dizionario. Per esempio, stampa_isto visualizza ciascuna chiave e il valore corrispondente:

def stampa_isto(h):
    for c in h:
        print(c, h[c])

Ecco come risulta l’output:

>>> h = istogramma('parrot')
>>> stampa_isto(h)
a 1
p 1
r 2
t 1
o 1

Di nuovo, le chiavi sono alla rinfusa. Per attraversare le chiavi disponendole in ordine, si può utilizzare la funzione predefinita sorted:

>>> for chiave in sorted(h):
...     print(chiave, h[chiave])
a 1
o 1
p 1
r 2
t 1

11.4  Lookup inverso

Dato un dizionario d e una chiave k, è facile trovare il valore corrispondente alla chiave: v = d[k]. Questa operazione è chiamata lookup.

Ma se invece volete trovare la chiave k conoscendo il valore v? Avete due problemi: primo, ci possono essere più chiavi che corrispondono al valore v. A seconda dell’applicazione, potete riuscire a trovarne uno, oppure può essere necessario ricavare una lista che li contenga tutti. Secondo, non c’è una sintassi semplice per fare un lookup inverso; dovete impostare una ricerca.

Ecco una funzione che richiede un valore e restituisce la prima chiave a cui corrisponde quel valore:

def inverso_lookup(d, v):
    for k in d:
        if d[k] == v:
            return k
    raise LookupError()

Questa funzione è un altro esempio di schema di ricerca, ma usa un’istruzione che non abbiamo mai visto prima, raise. L’istruzione raise solleva un’eccezione; in questo caso genera un errore LookupError, che è un eccezione predefinita usata per indicare che un’operazione di lookup è fallita.

Se arriviamo a fine ciclo, significa che v non compare nel dizionario come valore, per cui solleviamo un’eccezione.

Ecco un esempio di lookup inverso riuscito:

>>> h = istogramma('parrot')
>>> chiave = inverso_lookup(h, 2)
>>> chiave
'r'

E di uno fallito:

>>> chiave = inverso_lookup(h, 3)
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "<stdin>", line 5, in inverso_lookup
LookupError

Quando generate un errore, l’effetto è lo stesso di quando lo genera Python: viene stampato un traceback con un messaggio di errore.

L’istruzione raise può ricevere come parametro opzionale un messaggio di errore dettagliato. Per esempio:

>>> raise LookupError('il valore non compare nel dizionario')
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
LookupError: il valore non compare nel dizionario

Un lookup inverso è molto più lento di un lookup; se dovete farlo spesso, o se il dizionario diventa molto grande, le prestazioni del vostro programma potrebbero risentirne.

11.5  Dizionari e liste

Le liste possono comparire come valori in un dizionario. Per esempio, se avete un dizionario che fa corrispondere le lettere alle loro frequenze, potreste volere l’inverso; cioè creare un dizionario che a partire dalle frequenze fa corrispondere le lettere. Poiché ci possono essere più lettere con la stessa frequenza, ogni valore del dizionario inverso dovrebbe essere una lista di lettere.

Ecco una funzione che inverte un dizionario:

def inverti_diz(d):
    inverso = dict()
    for chiave in d:
        valore = d[chiave]
        if valore not in inverso:
            inverso[valore] = [chiave]
        else:
            inverso[valore].append(chiave)
    return inverso

Per ogni ripetizione del ciclo, chiave prende una chiave da d e valore assume il corrispondente valore. Se valore non appartiene a inverso, vuol dire che non è ancora comparso, per cui creiamo un nuovo elemento e lo inizializziamo con un singleton (lista che contiene un solo elemento). Altrimenti, se il valore era già apparso, accodiamo la chiave corrispondente alla lista esistente.

Ecco un esempio:

>>> isto = istogramma('parrot')
>>> isto
{'a': 1, 'p': 1, 'r': 2, 't': 1, 'o': 1}
>>> inverso = inverti_diz(isto)
>>> inverso
{1: ['a', 'p', 't', 'o'], 2: ['r']}

---

Figure 11.1: Diagramma di stato.

---

La Figura 11.1 è un diagramma di stato che mostra isto e inverso. Un dizionario viene rappresentato come un riquadro con la scritta dict sopra e le coppie chiave-valore all’interno. Se i valori sono interi, float o stringhe, li raffiguro dentro il riquadro, lascio invece all’esterno le liste per mantenere semplice il diagramma.

Le liste possono essere valori nel dizionario, come mostra questo esempio, ma non possono essere chiavi. Ecco cosa succede se ci provate:

>>> t = [1, 2, 3]
>>> d = dict()
>>> d[t] = 'oops'
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
TypeError: list objects are unhashable

Ho accennato che i dizionari sono implementati usando una tabella hash, e questo implica che alle chiavi deve poter essere applicato un hash.

Un hash è una funzione che prende un valore (di qualsiasi tipo) e restituisce un intero. I dizionari usano questi interi, chiamati valori hash, per conservare e consultare le coppie chiave-valore.

Questo sistema funziona se le chiavi sono immutabili; ma se sono mutabili, come le liste, succedono disastri. Per esempio, nel creare una coppia chiave-valore, Python fa l’hashing della chiave e la immagazzina nello spazio corrispondente. Se modificate la chiave e quindi viene nuovamente calcolato l’hash, si collocherebbe in un altro spazio. In quel caso potreste avere due voci della stessa chiave, oppure non riuscire a trovare una chiave. In ogni caso il dizionario non funzionerà correttamente.

Ecco perché le chiavi devono essere idonee all’hashing, e quelle mutabili come le liste non lo sono. Il modo più semplice per aggirare questo limite è usare le tuple, che vedremo nel prossimo capitolo.

Dato che i dizionari sono mutabili, non possono essere usati come chiavi ma possono essere usati come valori.

11.6  Memoizzazione

Se vi siete sbizzarriti con la funzione fibonacci del Paragrafo 6.7, avrete notato che più grande è l’argomento che passate, maggiore è il tempo necessario per l’esecuzione della funzione. Inoltre, il tempo di elaborazione cresce rapidamente.

Per capire il motivo, confrontate la Figura 11.2, che mostra il grafico di chiamata di fibonacci con n=4:

---

Figure 11.2: Grafico di chiamata.

---

Un grafico di chiamata mostra l’insieme dei frame della funzione, con linee che collegano ciascun frame ai frame delle funzioni che chiama a sua volta. In cima al grafico, fibonacci con n=4 chiama fibonacci con n=3 e n=2. A sua volta, fibonacci con n=3 chiama fibonacci con n=2 e n=1. E così via.

Provate a contare quante volte vengono chiamate fibonacci(0) e fibonacci(1). Questa è una soluzione inefficiente del problema, che peggiora ulteriormente al crescere dell’argomento.

Una soluzione migliore è tenere da parte i valori che sono già stati calcolati, conservandoli in un dizionario. La tecnica di conservare per un uso successivo un valore già calcolato, così da non doverlo ricalcolare ogni volta, viene detta memoizzazione. Ecco una versione di fibonacci che usa la memoizzazione:

memo = {0:0, 1:1}

def fibonacci(n):
    if n in memo:
        return memo[n]

    res = fibonacci(n-1) + fibonacci(n-2)
    memo[n] = res
    return res

memo è un dizionario che conserva i numeri di Fibonacci già conosciuti. Parte con due elementi: 0 che corrisponde a 0, e 1 che corrisponde a 1.

Ogni volta che fibonacci viene chiamata, controlla innanzitutto memo. Se quest’ultimo contiene già il risultato, ritorna immediatamente. Altrimenti deve calcolare il nuovo valore, lo aggiunge al dizionario e lo restituisce.

Provate ad eseguire questa versione di fibonacci e a confrontarla con l’originale: troverete che è molto più veloce.

11.7  Variabili globali

Nell’esempio precedente, memo viene creato esternamente alla funzione, pertanto appartiene al frame speciale chiamato __main__. Le variabili di __main__ sono dette anche globali perché ad esse possono accedere tutte le funzioni. A differenza delle variabili locali, che sono distrutte una volta terminata l’esecuzione della loro funzione, quelle globali persistono tra una chiamata di funzione e l’altra.

Di frequente le variabili globali vengono usate come controlli o flag; vale a dire, variabili booleane che indicano quando una certa condizione è soddisfatta (True). Per esempio, alcuni programmi usano un flag di nome verbose per controllare che livello di dettaglio dare ad un output:

verbose = True

def esempio1():
    if verbose:
        print('esempio1 in esecuzione')

Se cercate di riassegnare una variabile globale, potreste avere una sorpresa. L’esempio seguente vorrebbe controllare se una funzione è stata chiamata:

stata_chiamata = False

def esempio2():
    stata_chiamata = True         # SBAGLIATO

Ma se la eseguite vedrete che il valore di stata_chiamata non cambia. Il motivo è che la funzione esempio2 crea una nuova variabile di nome stata_chiamata, che è locale, viene distrutta al termine della funzione e non ha effetti sulla variabile globale.

Per riassegnare una variabile globale dall’interno di una funzione, dovete dichiarare la variabile globale prima di usarla:

stata_chiamata = False

def esempio2():
    global stata_chiamata 
    stata_chiamata = True

L’istruzione global dice all’interprete una cosa del genere: “In questa funzione, quando dico stata_chiamata, intendo la variabile globale: non crearne una locale”.

Ecco un altro esempio che cerca di aggiornare una variabile globale:

conta = 0

def esempio3():
    conta = conta + 1          # SBAGLIATO

Se lo eseguite, ottenete:

UnboundLocalError: local variable 'conta' referenced before assignment

Python presume che conta all’interno della funzione sia una variabile locale, e con questa premessa significa che state usando la variabile prima di averla inizializzata. La soluzione è ancora quella di dichiarare conta globale.

def esempio3():
    global conta
    conta += 1

Se una variabile globale fa riferimento ad un valore mutabile, potete modificare il valore senza dichiarare la variabile:

noto = {0:0, 1:1}

def esempio4():
    noto[2] = 1

Pertanto, potete aggiungere, rimuovere e sostituire elementi di una lista o dizionario globali; tuttavia, se volete riassegnare la variabile, occorre dichiararla:

def esempio5():
    global noto
    noto = dict()

Le variabili globali possono risultare utili, ma se ce ne sono molte e le modificate di frequente, possono rendere difficile il debug del programma.

11.8  Debug

Se lavorate con banche dati di grosse dimensioni, può diventare oneroso fare il debug stampando e controllando i risultati di output manualmente. Ecco allora alcuni suggerimenti per fare il debug in queste situazioni:

Ridurre l’input:

Se possibile, riducete le dimensioni della banca dati. Per esempio, se il programma legge un file di testo, cominciate con le sole prime 10 righe o con il più piccolo campione che riuscite a trovare. Potete anche adattare i file stessi, o (meglio) modificare il programma, in modo che legga solo le prime n righe.

Se c’è un errore, potete ridurre n al più piccolo valore per il quale si manifesta l’errore, poi aumentarlo gradualmente finché non trovate e correggete l’errore.

Controllare riassunti e tipi:

Invece di stampare e controllare l’intera banca dati, prendete in considerazione di stampare riassunti dei dati: ad esempio il numero di elementi in un dizionario o la sommatoria di una lista di numeri.

Una causa frequente di errori in esecuzione è un valore che non è del tipo giusto. Per fare il debug di questo tipo di errori basta spesso stampare il tipo di un valore.

Scrivere controlli automatici:

Talvolta è utile scrivere del codice per controllare automaticamente gli errori. Per esempio, se dovete calcolare la media di una lista di numeri, potete controllare che il risultato non sia maggiore dell’elemento più grande della lista e non sia minore del più piccolo. Questo è detto “controllo di congruenza” perché mira a trovare i risultati “incongruenti”.

Un altro tipo di controllo confronta i risultati di due calcoli per vedere se collimano. Questo è chiamato “controllo di coerenza”.

Stampare gli output in bella copia:

Una buona presentazione dei risultati di debug rende più facile trovare un errore. Abbiamo visto un esempio nel Paragrafo 6.9. Uno strumento utile è il modulo pprint: esso contiene la funzione pprint che mostra i tipi predefiniti in un formato più leggibile (pprint infatti sta per “pretty print”).

Ancora, il tempo che impiegate a scrivere del codice temporaneo può essere ripagato dalla riduzione del tempo di debug.

11.9  Glossario

mappatura:

Relazione per cui a ciascun elemento di un insieme corrisponde un elemento di un altro insieme.

dizionario:

Una mappatura da chiavi nei loro valori corrispondenti.

coppia chiave-valore:

Rappresentazione della mappatura da una chiave in un valore.

elemento:

In un dizionario, altro nome della coppia chiave-valore.

chiave:

Oggetto che compare in un dizionario come prima voce di una coppia chiave-valore.

valore:

Oggetto che compare in un dizionario come seconda voce di una coppia chiave-valore. È più specifico dell’utilizzo del termine “valore” fatto sinora.

implementazione:

Un modo per effettuare un’elaborazione.

tabella hash:

Algoritmo usato per implementare i dizionari in Python.

funzione hash:

Funzione usata da una tabella hash per calcolare la collocazione di una chiave.

hash-abile:

Un tipo a cui si può applicare la funzione hash. I tipi immutabili come interi, float e stringhe lo sono; i tipi mutabili come liste e dizionari no.

lookup:

Operazione su un dizionario che trova il valore corrispondente a una data chiave.

lookup inverso:

Operazione su un dizionario che trova una o più chiavi alle quali è associato un dato valore.

singleton:

Lista (o altra sequenza) con un singolo elemento.

grafico di chiamata:

Diagramma che mostra tutti i frame creati durante l’esecuzione di un programma, con frecce che collegano ciascun chiamante ad ogni chiamata.

memoizzazione:

Conservare un valore calcolato per evitarne il successivo ricalcolo.

variabile globale:

Variabile definita al di fuori di una funzione, alla quale ogni funzione può accedere.

istruzione global:

Istruzione che dichiara globale il nome di una variabile.

controllo o flag:

Variabile booleana usata per indicare se una condizione è soddisfatta.

dichiarazione:

Istruzione come global, che comunica all’interprete un’informazione su una variabile.

11.10  Esercizi

Buy this book at Amazon.com

Contribute

Pay what you want:

Small $1.00 USD Medium $5.00 USD Large $10.00 USD X-Large $20.00 USD XX-Large $50.00 USD

Are you using one of our books in a class?