Buy this book at Amazon.com

Chapter 13  Esercitazione: Scelta della struttura di dati

Giunti a questo punto, avete conosciuto le principali strutture di dati di Python, e visto alcuni algoritmi che le utilizzano. Se vi interessa saperne di più sugli algoritmi, potrebbe essere un buon momento per leggere l’Appendice B. Non è però necessario per proseguire la lettura: fatelo quando vi pare opportuno.

L’esercitazione di questo capitolo vi aiutèrà ad impratichirvi nella scelta e nell’uso delle strutture di dati.

13.1  Analisi di frequenza delle parole

Come al solito, tentate almeno di risolvere gli esercizi prima di guardare le mie risoluzioni.

>>> import string
>>> string.punctuation
'!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~'

13.2  Numeri casuali

A parità di dati di partenza, i programmi, per la maggior parte, fanno la stessa cosa ogni volta che vengono eseguiti, e per questo motivo sono detti deterministici. Di solito il determinismo è una buona cosa, in quanto dagli stessi dati in ingresso è logico aspettarsi sempre lo stesso risultato. Per alcune applicazioni, invece, serve che l’esecuzione sia imprevedibile: i videogiochi sono un esempio lampante, ma ce ne sono tanti altri.

Creare un programma realmente non-deterministico è una cosa piuttosto difficile, ma ci sono dei sistemi per renderlo almeno apparentemente non-deterministico. Uno di questi è utilizzare degli algoritmi che generano dei numeri pseudocasuali. Questi numeri non sono veri numeri casuali, dato che sono generati da un elaboratore deterministico, ma a prima vista è praticamente impossibile distinguerli da numeri casuali.

Il modulo random contiene delle funzioni che generano numeri pseudocasuali (d’ora in avanti chiamati “casuali” per semplicità).

La funzione random restituisce un numero casuale in virgola mobile compreso nell’intervallo tra 0.0 e 1.0 (incluso 0.0 ma escluso 1.0). Ad ogni chiamata di random, si ottiene il numero successivo di una lunga serie di numeri casuali. Per vedere un esempio provate ad eseguire questo ciclo:

import random

for i in range(10):
    x = random.random()
    print(x)

La funzione randint richiede due parametri interi, uno inferiore e uno superiore, e restituisce un intero casuale nell’intervallo tra i due parametri (entrambi compresi)

>>> random.randint(5, 10)
5
>>> random.randint(5, 10)
9

Per estrarre un elemento a caso da una sequenza, potete usare choice:

>>> t = [1, 2, 3]
>>> random.choice(t)
2
>>> random.choice(t)
3

Il modulo random contiene anche delle funzioni per generare valori pseudocasuali da distribuzioni continue, incluse gaussiane, esponenziali, gamma, e alcune altre.

>>> t = ['a', 'a', 'b']
>>> isto = istogramma(t)
>>> isto
{'a': 2, 'b': 1}

13.3  Istogramma di parole

Provate a risolvere gli esercizi precedenti prima di procedere oltre. Le soluzioni sono scaricabili da http://thinkpython2.com/code/analyze_book1.py. Vi servirà anche http://thinkpython2.com/code/emma.txt.

Ecco un programma che legge un file e costruisce un istogramma della parole in esso contenute:

import string

def elabora_file(nomefile):
    isto = dict()
    fp = open(nomefile)
    for riga in fp:
        elabora_riga(riga, isto)
    return isto

def elabora_riga(riga, isto):
    riga = riga.replace('-', ' ')
    
    for parola in riga.split():
        parola = parola.strip(string.punctuation + string.whitespace)
        parola = parola.lower()
        isto[parola] = isto.get(parola, 0) + 1

isto = elabora_file('emma.txt')

Questo programma legge il file emma.txt, che contiene il testo di Emma di Jane Austen.

elabora_file legge ciclicamente le righe del file, passandole una per volta a elabora_riga. L’istogramma isto viene usato come un accumulatore.

elabora_riga usa il metodo delle stringhe replace per sostituire i trattini con gli spazi, prima di usare split per suddividere la riga in una lista di stringhe. Attraversa poi la lista di parole e usa strip e lower per togliere la punteggiatura e convertire in lettere minuscole. (Diciamo per semplicità che le stringhe sono “convertite”: essendo queste immutabili, i metodi come strip e lower in realtà restituiscono nuove stringhe).

Infine, elabora_riga aggiorna l’istogramma creando un nuovo elemento o incrementandone uno esistente.

Per contare il numero di parole totali, possiamo aggiungere le frequenze nell’istogramma:

def parole_totali(isto):
    return sum(isto.values())

Il numero di parole diverse è semplicemente il numero di elementi nel dizionario:

def parole_diverse(isto):
    return len(isto)

Ed ecco del codice per stampare i risultati:

print('Numero totale di parole:', parole_totali(isto))
print('Numero di parole diverse:', parole_diverse(isto))

E i relativi risultati:

Numero totale di parole: 161080
Numero di parole diverse: 7214

13.4  Parole più comuni

Per trovare le parole più comuni, possiamo creare una lista di tuple, in cui ciascuna tupla contiene una parola e la sua frequenza, ed ordinarle:

La funzione seguente prende un istogramma e restituisce una lista di tuple parola-frequenza:

def piu_comuni(isto):
    t = []
    for chiave, valore in isto.items():
        t.append((valore, chiave))

    t.sort(reverse=True)
    return t

In ogni tupla, la frequenza compare per prima, quindi la lista risultante è ordinata per frequenza. Ecco un ciclo che stampa le dieci parole più comuni:

t = piu_comuni(hist)
print('Le parole più comuni sono:')
for freq, parola in t[:10]:
    print(parola, freq, sep='\t')

Ho usato l’argomento con nome sep per dire a print di usare un carattere di tabulazione come “separatore”, anziché uno spazio, in modo che la seconda colonna risulti allineata. E questi sono i risultati nel caso di Emma:

Le parole più comuni sono:
to      5242
the     5205
and     4897
of      4295
i       3191
a       3130
it      2529
her     2483
was     2400
she     2364

Si potrebbe semplificare il codice utilizzando il parametro key della funzione sort. Se vi incuriosisce, leggete https://wiki.python.org/moin/HowTo/Sorting.

13.5  Parametri opzionali

Abbiamo già visto funzioni predefinite e metodi che ricevono argomenti opzionali. È possibile anche scrivere funzioni personalizzate con degli argomenti opzionali. Ad esempio, questa è una funzione che stampa le parole più comuni in un istogramma:

def stampa_piu_comuni(isto, num=10):
    t = piu_comuni(isto)
    print('Le parole più comuni sono:')
    for freq, parola in t[:num]:
        print(parola, freq, sep='\t')

Il primo parametro è obbligatorio; il secondo è opzionale. Il valore di default di num è 10.

Se passate un solo argomento:

stampa_piu_comuni(isto)

num assume il valore predefinito. Se ne passate due:

stampa_piu_comuni(isto, 20)

num assume il valore che avete specificato. In altre parole, l’argomento opzionale sovrascrive il valore predefinito.

Se una funzione ha sia parametri obbligatori che opzionali, tutti quelli obbligatori devono essere scritti per primi, seguiti da quelli opzionali.

13.6  Sottrazione di dizionari

Trovare le parole del libro non comprese nell’elenco words.txt è un problema che possiamo classificare come sottrazione di insiemi, cioè occorre trovare le parole appartenenti a un insieme (le parole contenute nel libro) che non si trovano nell’altro insieme (l’elenco).

sottrai prende i dizionari d1 e d2 e ne restituisce uno nuovo che contiene tutte le chiavi di d1 che non si trovano in d2. Siccome non ci interessano affatto i valori, li impostiamo tutti a None.

def sottrai(d1, d2):
    res = dict()
    for chiave in d1:
        if chiave not in d2:
            res[chiave] = None
    return res

Quindi usiamo elabora_file per costruire un istogramma di words.txt, per poi sottrarre:

parole = elabora_file('words.txt')
diff = sottrai(isto, parole)

print("Parole del libro che non si trovano nell'elenco:")
for parola in diff:
    print(parola, end=' ')

Ecco alcuni risultati per Emma:

Parole del libro che non si trovano nell'elenco:
 rencontre jane's blanche woodhouses disingenuousness 
friend's venice apartment ...

Alcune parole sono nomi propri e possessivi. Altre come “rencontre” sono desuete. Ma qualcuna è davvero una parola comune che nell’elenco dovrebbe esserci!

13.7  Parole a caso

Per scegliere una parola a caso dall’istogramma, l’algoritmo più semplice è costruire una lista che contiene più copie di ciascuna parola, secondo la frequenza osservata, e poi estrarre a caso da questa lista:

def parola_caso(h):
    t = []
    for parola, freq in h.items():
        t.extend([parola] * freq)

    return random.choice(t)

L’espressione [parola] * freq crea una lista con freq copie della stringa parola. Il metodo extend è simile a append, con la differenza che l’argomento è una sequenza.

Questo algoritmo funziona, ma non è molto efficiente: ogni volta che estraete una parola, ricostruisce la lista, che è grande come il libro originale. Un ovvio miglioramento è di costruire la lista una sola volta e poi fare estrazioni multiple, ma la lista è ancora grande.

Un’alternativa è:

1. Usare keys per ottenere una lista delle parole del libro.
2. Costruire una lista che contiene la somma cumulativa delle frequenze delle parole (vedere l’Esercizio 2). L’ultimo elemento della lista è il numero totale delle parole nel libro, n.
3. Scegliere un numero a caso da 1 a n. Usare una ricerca binaria (vedere l’Esercizio 10) per trovare l’indice dove il numero casuale si inserirebbe nella somma cumulativa.
4. Usare l’indice per trovare la parola corrispondente nella lista di parole.

13.8  Analisi di Markov

Scegliendo a caso delle parole dal libro, potete avere un’idea del vocabolario usato dall’autore, ma difficilmente otterrete una frase di senso compiuto:

this the small regard harriet which knightley's it most things

Una serie di parole estratte a caso raramente hanno senso, perché non esistono relazioni tra parole successive. In una frase, per esempio, è prevedibile che ad un articolo come “il” segua un aggettivo o un sostantivo, ma non un verbo o un avverbio.

Un modo per misurare questo tipo di relazioni è l’analisi di Markov che, per una data sequenza di parole, descrive la probabilità della parola che potrebbe seguire. Prendiamo la canzone dei Monty Python Eric, the Half a Bee che comincia così:

Half a bee, philosophically,
Must, ipso facto, half not be.
But half the bee has got to be
Vis a vis, its entity. D’you see?

But can a bee be said to be
Or not to be an entire bee
When half the bee is not a bee
Due to some ancient injury?

In questo testo, la frase “half the” è sempre seguita dalla parola “bee,” ma la frase “the bee” può essere seguita sia da “has” che da “is”.

Il risultato dell’analisi di Markov è una mappatura da ciascun prefisso (come “half the” e “the bee”) in tutti i possibili suffissi (come “has” e “is”).

Eseguita questa mappatura, potete generare un testo casuale partendo da qualunque prefisso e scegliendo a caso uno dei possibili suffissi. Poi, potete combinare la fine del prefisso e il nuovo suffisso per formare il successivo prefisso, e ripetere l’operazione.

Ad esempio, se partite con il prefisso “Half a,” la parola successiva sarà senz’altro “bee,” perché il prefisso compare solo una volta nel testo. Il prefisso successivo sarà “a bee,” quindi il suffisso successivo potrà essere “philosophically”, “be” oppure “due”.

In questo esempio, la lunghezza del prefisso è sempre di due parole, ma potete fare l’analisi di Markov con prefissi di qualunque lunghezza.

Cercate di svolgere questo esercizio prima di andare oltre; poi potete scaricare la mia soluzione dal sito http://thinkpython2.com/code/markov.py. Vi servirà anche http://thinkpython2.com/code/emma.txt.

13.9  Strutture di dati

Utilizzare l’analisi di Markov per generare testi casuali è divertente, ma c’è anche un obiettivo in questo esercizio: la scelta della struttura di dati. Per risolverlo, dovevate infatti scegliere:

• Come rappresentare i prefissi.
• Come rappresentare la raccolta di possibili suffissi.
• Come rappresentare la mappatura da ciascun prefisso nella raccolta di suffissi.

L’ultima è facile: un dizionario è la scelta scontata per mappare da chiavi nei corrispondenti valori.

Per i prefissi, le possibili scelte sono: stringa, lista di stringhe o tuple di stringhe. Per i suffissi, un’opzione è una lista, l’altra è un istogramma (cioè un dizionario).

Quale scegliere? Per prima cosa dovete chiedervi quali tipi di operazione dovete implementare per ciascuna struttura di dati. Per i prefissi, ci serve poter rimuovere le parole all’inizio e aggiungerne in coda. Per esempio, se il prefisso attuale è “Half a,” e la parola successiva è “bee,” dobbiamo essere in grado di formare il prefisso successivo, “a bee”.

La prima ipotesi allora potrebbe essere una lista, dato che permette di aggiungere e rimuovere elementi in modo semplice, tuttavia abbiamo anche bisogno di usare i prefissi come chiavi di un dizionario, cosa che esclude le liste. Con le tuple non possiamo aggiungere o rimuovere, ma possiamo sempre usare l’operatore di addizione per formare una nuova tupla:

def cambia(prefisso, parola):
    return prefisso[1:] + (parola,)

cambia prende una tupla di parole, prefisso, e una stringa, parola, e forma una nuova tupla che comprende tutte le parole in prefisso tranne la prima, e parola aggiunta alla fine.

Per la raccolta di suffissi, le operazioni che dobbiamo eseguire comprendono l’aggiunta di un nuovo suffisso (o l’incremento della frequenza di un suffisso esistente) e l’estrazione di un elemento a caso.

Aggiungere un nuovo suffisso è ugualmente semplice sia nel caso di implementazione di una lista sia di un istogramma. Estrarre un elemento da una lista è facile, da un istogramma difficile da fare in modo efficiente (vedere Esercizio 7).

Sinora abbiamo considerato soprattutto la facilità di implementazione, ma ci sono altri fattori da tenere in considerazione nella scelta delle strutture di dati. Una è il tempo di esecuzione. A volte ci sono ragioni teoriche per attendersi che una struttura sia più veloce di un’altra; per esempio ho già accennato che l’operatore in è più rapido nei dizionari che non nelle liste, almeno in presenza di un gran numero di elementi.

Ma spesso non è possibile sapere a priori quale implementazione sarà più veloce. Una scelta possibile è implementarle entrambe e provare quale si comporta meglio. Questo approccio è detto benchmarking. Un’alternativa pratica è quella di scegliere la struttura di dati più facile da implementare e vedere se è abbastanza veloce per quell’applicazione. Se è così, non c’è bisogno di andare oltre. Altrimenti, ci sono strumenti, come il modulo profile che è in grado di segnalare i punti in cui il programma impiega la maggior parte del tempo.

Altro fattore da considerare è lo spazio di archiviazione. Ad esempio, usare un istogramma per la raccolta di suffissi può richiedere meno spazio, perché è necessario memorizzare ogni parola solo una volta, indipendentemente da quante volte compaia nel testo. In qualche caso, risparmiare spazio significa avere un programma più veloce; in casi estremi, il programma può non funzionare affatto se provoca l’esaurimento della memoria. Ma per molte applicazioni, lo spazio è di secondaria importanza rispetto al tempo di esecuzione.

Un’ultima considerazione: in questa discussione, era sottointeso che avremmo dovuto usare una stessa struttura di dati sia per l’analisi che per la generazione. Ma siccome sono fasi separate, nulla vieta di usare un tipo di struttura per l’analisi e poi convertirlo in un’altra struttura per la generazione. Sarebbe un guadagno, se il tempo risparmiato durante la generazione superasse quello impiegato nella conversione.

13.10  Debug

Quando fate il debug di un programma, e specialmente se state affrontando un bug ostico, ci sono cinque cose da provare:

Leggere:

Esaminate il vostro codice, rileggetelo e controllate che esprima esattamente quello che voi intendete dire.

Eseguire:

Sperimentate facendo modifiche ed eseguendo le diverse versioni. Spesso, se visualizzate la cosa giusta al posto giusto all’interno del programma, il problema diventa evidente; magari occorre spendere un po’ di tempo per inserire qualche “impalcatura”.

Rimuginare:

Prendetevi il tempo per pensarci su! Che tipo di errore è: di sintassi, di runtime o di semantica? Che informazioni si traggono dal messaggio di errore o dall’output del programma? Che tipo di errore potrebbe causare il problema che vedete? Quali modifiche avete fatto prima che si verificasse il problema?

Parlare a una papera di gomma:

Spiegando il problema a qualcun altro, talvolta si trova la risposta ancor prima di finire di formulare la domanda. Ma spesso non serve nemmeno un’altra persona: potete semplicemente parlare ad una papera di gomma. E da qui nasce la nota tecnica chiamata debug con la papera di gomma. Non me lo sono inventato: date un’occhiata a https://en.wikipedia.org/wiki/Rubber_duck_debugging.

Tornare indietro:

A un certo punto, la cosa migliore da fare è tornare sui vostri passi, annullare le ultime modifiche, fino a riottenere un programma funzionante e comprensibile. Poi rifate da capo.

I programmatori principianti a volte si fissano su uno di questi punti e tralasciano gli altri. Ciascuno di essi ha dei punti deboli.

Per esempio, leggere il codice va bene se il problema è un errore di battitura, ma non se c’è un fraintendimento concettuale. Se non capite cosa fa il vostro programma, potete leggerlo 100 volte senza riuscire a trovare l’errore, perché l’errore sta nella vostra testa.

Fare esperimenti va bene, specie se si tratta di piccoli, semplici test. Ma se fate esperimenti senza pensare o leggere il codice, potete cascare in uno schema che io chiamo “programmare a tentoni”, che significa fare tentativi a casaccio finché il programma non fa la cosa giusta. Inutile dirlo, questo può richiedere un sacco di tempo.

Dovete prendervi il tempo di riflettere. Il debug è come una scienza sperimentale. Dovete avere almeno un’ipotesi di quale sia il problema. Se ci sono due o più possibilità, provate a elaborare un test che ne elimini una.

Ma anche le migliori tecniche di debug falliranno se ci sono troppi errori o se il codice che state cercando di sistemare è troppo grande e complesso. Allora l’opzione migliore è di tornare indietro e semplificare il programma, fino ad ottenere qualcosa di funzionante e che riuscite a capire.

I principianti spesso sono riluttanti a tornare sui loro passi e si spaventano all’idea di cancellare anche una singola riga di codice (anche se è sbagliata). Se vi fa sentire meglio, copiate il programma in un altro file prima di sfrondarlo, potrete così ripristinare i pezzi di codice uno alla volta.

Trovare un bug difficile richiede lettura, esecuzione, rimuginazione e a volte ritornare sui propri passi. Se rimanete bloccati su una di queste attività, provate le altre.

13.11  Glossario

deterministico:

Qualità di un programma di fare le stesse cose ogni volte che viene eseguito, a parità di dati di input.

pseudocasuale:

Detto di una sequenza di numeri che sembrano casuali, ma sono generati da un programma deterministico.

valore di default:

Il valore predefinito di un parametro opzionale quando non viene specificato altrimenti.

sovrascrivere:

Sostituire un valore di default con un argomento.

benchmarking:

Procedura di scelta tra strutture di dati di vario tipo, implementando le alternative e provandole su un campione di possibili input.

debug con la papera di gomma:

Fare il debug spiegando il problema ad un oggetto inanimato, come una papera di gomma. Articolare un problema può aiutare a risolverlo, nonostante la papera di gomma non sappia nulla di Python.

13.12  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?