|
|
|
|
|
|
|
I tipi di dati composti che abbiamo visto finora (stringhe, liste e tuple) usano gli interi come indici. Qualsiasi tentativo di usare altri tipi di dati produce un errore.
I dizionari sono simili agli altri tipi composti ma si differenziano per il fatto di poter usare qualsiasi tipo di dato immutabile come indice. Se desideriamo creare un dizionario per la traduzione di parole dall'inglese all'italiano è utile poter usare la parola inglese come indice di ricerca della corrispondente italiana. Gli indici usati sono in questo caso delle stringhe.
Un modo per creare un dizionario è partire con un dizionario vuoto e aggiungere via via gli elementi. Il dizionario vuoto è indicato da {}:
>>> Eng2Ita = {}
>>> Eng2Ita['one'] = 'uno'
>>> Eng2Ita['two'] = 'due'
La prima assegnazione crea un dizionario chiamato Eng2Ita; le altre istruzioni aggiungono elementi al dizionario. Possiamo stampare il valore del dizionario nel solito modo:
>>> print Eng2Ita
{'one': 'uno', 'two': 'due'}
Gli elementi di un dizionario appaiono in una sequenza separata da virgole. Ogni voce contiene un indice ed il corrispondente valore separati da due punti. In un dizionario gli indici sono chiamati chiavi e un elemento è detto coppia chiave-valore.
Un altro modo di creare un dizionario è quello di fornire direttamente una serie di coppie chiave-valore:
>>> Eng2Ita = {'one': 'uno', 'two': 'due', 'three': 'tre'}
Se stampiamo ancora una volta il valore di Eng2Ita abbiamo una sorpresa:
>>> print Eng2Ita
{'one': 'uno', 'three': 'tre', 'two': 'due'}
Le coppie chiave-valore non sono in ordine! Per fortuna non c'è ragione di conservare l'ordine di inserimento dato che il dizionario non fa uso di indici numerici. Per cercare un valore usiamo infatti una chiave:
>>> print Eng2Ita['two']
'due'
La chiave 'two' produce correttamente 'due' anche se appare in terza posizione nella stampa del dizionario.
L'istruzione del rimuove una coppia chiave-valore da un dizionario. Vediamo di fare un esempio pratico creando un dizionario che contiene il nome di vari tipi di frutta (la chiave) ed il numero di frutti corrispondenti in magazzino (il valore):
>>> Magazzino = {'mele': 430, 'banane': 312, 'arance': 525,
'pere': 217}
>>> print Magazzino
{'banane': 312, 'arance': 525, 'pere': 217, 'mele': 430}
Dovessimo togliere la scorta di pere dal magazzino possiamo direttamente rimuovere la voce dal dizionario:
>>> del Magazzino['pere']
>>> print Magazzino
{'banane': 312, 'arance': 525, 'mele': 430}
o se intendiamo solo cambiare il numero di pere senza rimuoverne la voce dal dizionario possiamo cambiare il valore associato:
>>> Magazzino['pere'] = 0
>>> print Magazzino
{'banane': 312, 'arance': 525, 'pere': 0, 'mele': 430}
La funzione len opera anche sui dizionari ritornando il numero di coppie chiave-valore:
>>> len(Magazzino)
4
Un metodo è simile ad una funzione, visto che prende parametri e ritorna valori, ma la sintassi di chiamata è diversa. Il metodo keys prende un dizionario e ritorna la lista delle sue chiavi: invece di invocarlo con la sintassi delle funzioni keys(Eng2Ita) usiamo la sintassi dei metodi Eng2Ita.keys():
>>> Eng2Ita.keys()
['one', 'three', 'two']
Questa forma di notazione punto specifica il nome della funzione keys ed il nome dell'oggetto cui applicare la funzione Eng2Ita. Le parentesi vuote indicano che questo metodo non prende parametri.
Una chiamata ad un metodo è detta invocazione; in questo caso diciamo che stiamo invocando keys sull'oggetto Eng2Ita.
Il metodo values funziona in modo simile: ritorna la lista dei valori in un dizionario:
>>> Eng2Ita.values()
['uno', 'tre', 'due']
Il metodo items ritorna entrambi nella forma di una lista di tuple, una per ogni coppia chiave-valore:
>>> Eng2Ita.items()
[('one','uno'), ('three', 'tre'), ('two', 'due')]
La sintassi fornisce utili informazioni sul tipo ottenuto invocando items: le parentesi quadrate indicano che si tratta di una lista; le parentesi tonde che gli elementi della lista sono tuple.
Se un metodo prende un argomento usa la stessa sintassi delle chiamate di funzioni. Il metodo has_key prende come argomento una chiave e ritorna vero (1) se la chiave è presente nel dizionario:
>>> Eng2Ita.has_key('one')
1
>>> End2Ita.has_key('deux')
0
Se provi a invocare un metodo senza specificare l'oggetto cui si fa riferimento ottieni un errore:
>>> has_key('one')
NameError: has_key
Purtroppo il messaggio d'errore a volte, come in questo caso, non è del tutto chiaro: Python cerca di dirci che la funzione has_key non esiste, dato che con questa sintassi abbiamo chiamato la funzione has_key e non invocato il metodo has_key dell'oggetto.
Visto che i dizionari sono mutabili devi stare molto attento agli alias: quando due variabili si riferiscono allo stesso oggetto un cambio effettuato su una influenza immediatamente il contenuto dell'altra.
Se desideri poter modificare un dizionario e mantenere una copia dell'originale usa il metodo copy. Per fare un esempio costruiamo un dizionario Opposti che contiene coppie di parole dal significato opposto:
>>> Opposti = {'alto': 'basso', 'giusto': 'sbagliato',
'vero': 'falso'}
>>> Alias = Opposti
>>> Copia = Opposti.copy()
Alias e Opposti si riferiscono allo stesso oggetto; Copia si riferisce ad una copia del dizionario nuova di zecca. Se modifichiamo Alias, Opposti viene modificato:
>>> Alias['giusto'] = 'errato'
>>> Opposti['giusto']
'errato'
Opposti resta immutato se modifichiamo Copia:
>>> Copia['giusto'] = 'errato'
>>> Opposti['giusto']
'sbagliato'
Nella sezione 8.15 abbiamo usato una lista di liste per rappresentare una matrice. Questa è una buona scelta quando si tratta di rappresentare matrici i cui valori sono in buona parte diversi da zero, ma c'è un tipo di matrice detta "sparsa" i cui valori sono di tipo particolare:
La rappresentazione sotto forma di lista di questa matrice contiene molti zeri:
>>> Matrice = [ [0,0,0,1,0],
[0,0,0,0,0],
[0,2,0,0,0],
[0,0,0,0,0],
[0,0,0,3,0] ]
L'alternativa in questo caso è quella di usare un dizionario, usando come chiavi tuple composte dalla coppia riga/colonna. Ecco la stessa matrice rappresentata con un dizionario:
>>> Matrice = {(0,3): 1, (2, 1): 2, (4, 3): 3}
In questo caso abbiamo solo 3 coppie chiave-valore, una per ciascun elemento diverso da zero nella matrice. Ogni chiave è una tupla ed ogni valore un intero.
Per l'accesso ad un elemento della matrice possiamo usare l'operatore []:
>>> Matrice[(0,3)]
1
>>> Matrice[0,3] # questa sintassi e' equivalente
1
Nota come la sintassi per la rappresentazione della matrice sotto forma di dizionario sia diversa da quella della lista di liste: invece di due valori indice usiamo un unico indice che è una tupla di interi.
C'è un problema: se cerchiamo un elemento che è pari a zero otteniamo un errore, dato che non c'è una voce nel dizionario corrispondente alla tupla con quelle coordinate:
>>> Matrice[1,3]
KeyError: (1, 3)
Il metodo get risolve il problema:
>>> Matrice.get((0,3), 0)
1
Il primo argomento è la tupla-chiave, il secondo il valore che get deve ritornare nel caso la chiave non sia presente nel dizionario:
>>> Matrice.get((1,3), 0)
0
Anche se la sintassi di get non è la più intuitiva almeno abbiamo un modo efficiente per accedere ad una matrice sparsa.
Se hai fatto qualche prova con la funzione di Fibonacci nella sezione 5.7 avrai notato che man mano che l'argomento passato alla funzione cresce il tempo trascorso prima di ottenere il risultato aumenta molto rapidamente. Mentre Fibonacci(20) termina quasi istantaneamente Fibonacci(30) impiega qualche secondo e Fibonacci(40) impiega un tempo lunghissimo.
Per comprenderne il motivo consideriamo questo grafico delle chiamate per la funzione Fibonacci con n=4:
Un grafico delle chiamate mostra una serie di frame (uno per ogni funzione) con linee che collegano ciascun frame alle funzioni chiamate. A iniziare dall'alto 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.
Se conti il numero di volte in cui Fibonacci(0) e Fibonacci(1) sono chiamate ti accorgerai facilmente che questa soluzione è evidentemente inefficiente e le sue prestazioni tendono a peggiorare man mano che l'argomento diventa più grande.
Una buona soluzione è quella di tenere traccia in un dizionario di tutti i valori già calcolati per evitare il ricalcolo in tempi successivi. Un valore che viene memorizzato per un uso successivo è chiamato suggerimento. Ecco un'implementazione di Fibonacci fatta usando i "suggerimenti":
Precedenti = {0:1, 1:1}
def Fibonacci(n):
if Precedenti.has_key(n):
return Precedenti[n]
else:
NuovoValore = Fibonacci(n-1) + Fibonacci(n-2)
Precedenti[n] = NuovoValore
return NuovoValore
Il dizionario Precedenti tiene traccia dei numeri di Fibonacci già calcolati. Lo creiamo inserendo solo due coppie: 0 associato a 1 (Fibonacci(0) = 1) e 1 associato a 1 (Fibonacci(1) = 1).
La nuova funzione Fibonacci prima di tutto controlla se nel dizionario è già presente il valore cercato: se c'è viene restituito senza ulteriori elaborazioni. Nel caso non sia presente deve essere calcolato il nuovo valore che poi viene aggiunto al dizionario (per poter essere usato in momenti successivi) prima che la funzione termini.
Usando questa funzione di Fibonacci ora riusciamo a calcolare Fibonacci(40) in un attimo. Ma quando chiamiamo Fibonacci(50) abbiamo un altro tipo di problema:
>>> Fibonacci(50)
OverflowError: integer addition
La risposta che volevamo ottenere è 20365011074 ed il problema è che questo numero è troppo grande per essere memorizzato in un intero di Python. Durante il calcolo otteniamo un overflow che non è altro che uno "sbordamento" dall'intero. Fortunatamente in questo caso la soluzione è molto semplice.
Python fornisce un tipo chiamato long int che può maneggiare interi di qualsiasi grandezza.
Ci sono due modi per creare un valore intero lungo. Il primo consiste nello scrivere un intero immediatamente seguito da una L maiuscola:
>>> type(1L)
<type 'long int'>
Il secondo è l'uso della funzione long per convertire un valore in intero lungo. long può accettare qualsiasi tipo di numero e anche una stringa di cifre:
>>> long(1)
1L
>>> long(3.9)
3L
>>> long('57')
57L
Tutte le operazioni matematiche operano correttamente sugli interi lunghi così non dobbiamo fare molto per adattare Fibonacci:
>>> Precedenti = {0:1L, 1:1L}
>>> Fibonacci(50)
20365011074L
Solamente cambiando il valore iniziale di Precedenti abbiamo cambiato il comportamento di Fibonacci. I primi elementi della sequenza sono interi lunghi così tutti i numeri successivi diventano dello stesso tipo.
Esercizio: converti Fattoriale così da produrre interi lunghi come risultato.
Nel capitolo 7 abbiamo scritto una funzione che conta il numero di lettere in una stringa. Una possibile estensione è la creazione di un istogramma della stringa per mostrare la frequenza di ciascuna lettera.
Questo tipo di istogramma può essere utile per comprimere un file di testo: dato che le lettere compaiono con frequenza diversa possiamo usare codici brevi per le lettere più frequenti e codici via via più lunghi per le meno frequenti.
I dizionari permettono di realizzare istogrammi in modo elegante:
>>> ConteggioLettere = {}
>>> for Lettera in "Mississippi":
... ConteggioLettere [Lettera] = ConteggioLettere.get \
(Lettera, 0) + 1
...
>>> ConteggioLettere
{'M': 1, 's': 4, 'p': 2, 'i': 4}
Siamo partiti con un dizionario vuoto e per ogni lettera della stringa abbiamo incrementato il corrispondente conteggio. Alla fine il dizionario contiene coppie formate da lettera e frequenza e queste coppie rappresentano il nostro istogramma.
Può essere più interessante mostrare l'istogramma in ordine alfabetico, e in questo caso facciamo uso dei metodi items e sort:
>>> ConteggioLettere = ConteggioLettere.items()
>>> ConteggioLettere.sort()
>>> print ConteggioLettere
[('M', 1), ('i', 4), ('p', 2), ('s', 4)]
Abbiamo visto già il metodo items ma sort è il primo metodo che incontriamo ad essere applicabile alle liste. Ci sono parecchi altri metodi applicabili alle liste (tra gli altri append, extend e reverse). Puoi consultare la documentazione di Python per avere ulteriori informazioni a riguardo.
|
|
|
|
|
|
|