Setacciare numeri con il serpente (parte 2)

Caught me crawlin’, baby, Crawlin’ ‘round your door, Seein’ everything I want, I’m gonna crawl on your floor. – The Doors, Crawlin’ King Snake

[youtube https://www.youtube.com/watch?v=Z-ffGKXtvGE&w=560&amp]

Nel post di qualche mese fa, Setacciare numeri con il serpente, avevo preso lo spunto da un semplice programma che calcolava i numeri primi mediante il famoso Crivello di Eratostene, traducendo il programma dal BASIC originale in Python, che considero il linguaggio di programmazione più interessante, oggi.

Nella traduzione in Python avevo cercato di lasciare il più possibile inalterato il codice originale, aggiungendo solo alcune righe per mostrare i risultati del calcolo, righe che mancavano del tutto nel programma BASIC di partenza.

Questa volta voglio rendere il codice più moderno e facile da usare, facendo anche in modo che l’output del programma sia più immediatamente comprensibile.

Ecco quindi la versione rivista del programma in Python per il calcolo dei numeri primi. Poiché questo non vuole essere un corso di Python, ma solo una introduzione generale alla bellezza ed alle potenzialità del linguaggio, non entrerò negli aspetti specifici del codice, che possono essere approfonditi utilizzando i link forniti nella bibliografia.

from math import sqrt, ceil

num_max = 256
root = int(ceil(sqrt(num_max)))

flags = {}
for num in range(1, num_max + 1):
    flags[num] = "P"

for num in range(2, root):
    if flags[num] == "P":
        for mult in range(num**2, num_max + 1, num):
            flags[mult] = "-"

print("Sieve of Eratosthenes between 1 and %d (PYTHON-style): true/false map" %(num_max))
print flags
print

print("Sieve of Eratosthenes between 1 and %d (PYTHON-style): prime numbers" %(num_max))
for key,val in flags.items():
    if val == "P":
        print key,
    else:
        print "-",

Per provare il programma si può copiare il codice in un editor di testo (i soliti TextWrangler, TextMate, Atom, Brackets o editor analoghi), salvarlo sul disco rigido come “sieve_v2.py”, ed eseguirlo dal Terminale con il comando

$ python sieve_v2.py

Nella versione originale, prima di ogni esecuzione bisogna inserire a mano nel codice del programma sia il massimo numero intero fino a cui calcolare la lista dei numeri primi (num_max) sia la sua radice quadrata (root), arrotondata al primo intero più grande.

Ma i due numeri sono collegati, perché non far fare questi calcoli al computer?

Per svolgere le operazioni matematiche il Python ha bisogno di caricare esplicitamente la libreria esterna math. Questo meccanismo serve per rendere il più compatto possibile il codice di base dell’interprete Python, aumentandone potenza e capacità di svolgere operazioni particolari solo in caso di effettiva necessità.

Alla riga 1 viene quindi caricata la libreria matematica math, importando solo le funzioni che ci servono veramente, la radice quadrata (sqrt) e quella che effettua l’arrotondamento all’intero superiore (ceil) (per caricare l’intera libreria matematica, basta trasformare la riga 1 in import math).

Queste funzioni vengono usate alla riga 3, che deve essere letta dall’interno all’esterno. Per prima cosa si calcola la radice quadrata di num_max e il risultato è un numero con la virgola (float in Python). La funzione ceil() lo approssima al primo numero intero maggiore o uguale alla radice quadrata, lasciandolo però in formato di numero con la virgola. Infine int() converte il risultato in un vero numero intero.

Avrei anche potuto scrivere questa riga in modo più esplicito

...
temp1 = sqrt(num_max)
temp2 = int(temp1)
root = int(temp2)
...

introducendo due variabili temporanee, temp1 e temp2, che servono solo a memorizzare i risultati intermedi di calcolo, ma credo che questa forma sia persino meno comprensibile di quella originale.

Nella riga 5 la variabile flags, che nel codice originale è una variabile di tipo lista, cioè una serie ordinata di valori identificati da un indice numerico (un array in C) viene trasformata in un dizionario, un tipo di dati (detto anche array associativo) molto utile e caratteristico del Python e di (pochi) altri linguaggi.

...
flags = {}
for num in range(1, num_max + 1):
    flags[num] = "P"
...

Il vantaggio di usare un dizionario rispetto ad una lista sta nel fatto che gli elementi di un dizionario possono essere identificati da indici costituiti non solo da numeri interi ma anche da stringhe. Questo tipo di dati equivale quindi ad una lista non ordinata di dati, in cui ogni elemento di un dizionario è identificato da una chiave (key) e dal valore (val) corrispondente.

In questo caso particolare gli indici sono costituiti dai numeri interi da 1 fino a num_max, e a ciascuno elemento del dizionario viene inizialmente associato un valore costituito dalla stringa “P”.

Il resto del codice è quasi immutato, a parte il fatto che ogni volta che l’algoritmo determina che il numero in esame non è primo, impone il valore dell’elemento corrispondente del dizionario alla stringa “-“, invece che al valore logico False com’era in origine (riga 13).

La lista finale dei numeri primi viene stampata in due modi diversi. Nel primo (riga 16), la stampa della variabile dizionario flags mostra automaticamente la chiave (il numero intero) e la stringa associata (“P” se è primo, “-“ altrimenti).

[caption id=”attachment_1305” align=”aligncenter” width=”605”] Output della versione rivista del programma in Python per il calcolo dei numeri primi.[/caption]

Nel secondo, viene usato un metodo standard per accedere ai dizionari in Python

for key,val in flags.items():

con il quale si può accedere alle singole coppie chiave e valore di ciascun elemento di un dizionario (riga 20).

Qual’è il più veloce?

Ma è più veloce usare una lista o un dizionario? Per scoprirlo, misuriamo il tempo di esecuzione delle due versioni del codice Python, la versione originale sieve.py e la versione modificata mostrata sopra sieve_v2.py, per valori crescenti di num_max. Per evitare di influenzare le misure è consigliabile cancellare (o commentare) la sezione finale del codice contenente i comandi di stampa dei risultati, comandi molto più lenti rispetto al codice di calcolo vero e proprio.

Con il mio iMac del 2008 ottengo i risultati mostrati nella tabella seguente

num_max	sieve.py	sieve_v2.py
10.000	0.048	0.038
1.000.000	0.852	1.018
4.000.000	3.650	4.215
9.000.000	8.171	9.574
16.000.000	14.676	19.142
25.000.000	23.311	30.104

(chi fosse interessato può scaricare da questo link un foglio elettronico in formato Excel contenente una versione estesa della tabella con il relativo grafico).

I dati mostrano che in Python una lista è più veloce di un dizionario ma che la differenza non è comunque particolarmente significativa, almeno nei casi normali. Per gestire un dizionario, infatti, il Python deve eseguire una serie di processi di sistema che finiscono per incidere sempre di più sul tempo totale di esecuzione del programma, al crescere del numero massimo entro il quale calcolare i numeri primi.¹

Guardando la tabella (o il grafico Excel) si nota che con entrambi i programmi i tempi di calcolo crescono linearmente all’aumentare del valore massimo da calcolare. Tecnicamente si dice che l’algoritmo utilizzato è di ordine O(n), dove n indica in modo simbolico il valore massimo da raggiungere nel corso del calcolo.

Una crescita lineare del tempo di calcolo con n è un caso quasi ideale. Nella maggior parte dei casi i tempi di calcolo aumentano molto più rapidamente all’aumentare di n. Non è un caso quindi che la ricerca di metodi di calcolo sempre più efficienti sia uno dei campi più fecondi della matematica applicata e dell’informatica (che sono oggi più o meno la stessa cosa).

Bibliografia

La migliore introduzione a Python è senza dubbio How to Think Like a Computer Scientist: Learning with Python (è preferibile usare la seconda edizione per Python 2.x).

Ne esiste anche una versione nella nostra lingua, Pensare da informatico: Imparare con Python, disponibile sul sito ufficiale italiano di Python.

Mi piacciono anche Learn Python The Hard Way e il wiki PyTrieste, che ha il vantaggio di essere relativamente sintetico.

Uno strumento utilissimo è l’Online Python Tutor perché permette di osservare cosa succede veramente quando si esegue il codice Python che abbiamo scritto. Imperdibile.

1. Quanto detto è evidente dai dati della tabella Excel, dove, per le due versioni del programma, è elencato il tempo di calcolo vero e proprio (colonna “user”), il tempo impiegato ad eseguire i processi del sistema operativo (colonna “sys”) e la somma dei due tempi (colonna “user+sys”). I valori della colonna “user” sono abbastanza simili nelle due versioni del programma (cerchi aperti), mentre l’incremento progressivo dell’incidenza dei processi di sistema determina una divergenza crescente nel tempo totale di calcolo all’aumentare di num_max fra le due versioni del programma (cerchi chiusi). ↩