Per completare l'esempio sul calcolo dei numeri di Fibonacci iniziato con una discussione su La Memoizzazione, riporto alcuni dati sui tempi di esecuzione dei vari algoritmi possibili per il calcolo dell'n-esimo numero di
Il primo algoritmo è quello ricorsivo, che ho implementato così (con relativo main di test):
Questo codice è stato compilato col flag -O3 di gcc.
I risultati sono (inaspettatamente per chi non ha letto l'altra discussione) evidentemente terribili: per calcolare anche solo il 50-esimo numero della successione (che sembra una bazzecola) ci sono voluti in media 91 secondi. Abbastanza impressionate anche perché il 40-esimo numero viene calcolato in appena 0.000004 secondi (4µs). Per calcolare il 60-esimo numero sono serviti ~10924 secondi, nonché ~182 minuti, ovvero 3 ore. Ancora più sconvolgente se pensiamo che il nostro parametro è aumentato solo di 10.
È interessante anche notare come questi numeri crescano velocemente: se il ventesimo numero di Fibonacci è 6765, che può sembrare ancora piccolo, il sessantesimo numero è 1548008755920, un numero formato da 13 cifre (e qui si vede come il numero di cifre cresca linearmente col VALORE di n: infatti 13 è circa 60/5 (cf. la discussione linkata sopra). Tutto questo ci dà una prima idea di quanto intrattabili siano i problemi per cui si conoscono solo algoritmi esponenziali.
Passiamo adesso all'algoritmo che impiega tempo
. I tempi di esecuzione adesso ci appaiono molto più ragionevoli: il 50-esimo numero è stato calcolato in 4µs, lo stesso tempo che c'era voluto con l'altro algoritmo per calcolare il 40-esimo. Con questo algoritmo è stato possibile calcolare anche il 100-esimo, il 150-esimo e il 190-esimo in una media ancora di 4µs (il 200-esimo non si può calcolare con un long in C).
Il codice che ho usato per il secondo algoritmo è il seguente, e non ho usato nessun flag di ottimizzazione a tempo di compilazione:
Adesso possiamo renderci bene conto di quanto sia importante ancora oggi scrivere programmi efficienti, perché i miglioramenti alla potenza di calcolo delle macchine non consentono comunque di trattare problemi esponenziali (o in questo caso algoritmi esponenziali).
Perfavore,
Entra
oppure
Registrati
per vedere i Link!
, per dare un supporto sperimentale all'argomento teorico della discussione linkata sopra.Il primo algoritmo è quello ricorsivo, che ho implementato così (con relativo main di test):
C:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
I risultati sono (inaspettatamente per chi non ha letto l'altra discussione) evidentemente terribili: per calcolare anche solo il 50-esimo numero della successione (che sembra una bazzecola) ci sono voluti in media 91 secondi. Abbastanza impressionate anche perché il 40-esimo numero viene calcolato in appena 0.000004 secondi (4µs). Per calcolare il 60-esimo numero sono serviti ~10924 secondi, nonché ~182 minuti, ovvero 3 ore. Ancora più sconvolgente se pensiamo che il nostro parametro è aumentato solo di 10.
È interessante anche notare come questi numeri crescano velocemente: se il ventesimo numero di Fibonacci è 6765, che può sembrare ancora piccolo, il sessantesimo numero è 1548008755920, un numero formato da 13 cifre (e qui si vede come il numero di cifre cresca linearmente col VALORE di n: infatti 13 è circa 60/5 (cf. la discussione linkata sopra). Tutto questo ci dà una prima idea di quanto intrattabili siano i problemi per cui si conoscono solo algoritmi esponenziali.
Passiamo adesso all'algoritmo che impiega tempo
Il codice che ho usato per il secondo algoritmo è il seguente, e non ho usato nessun flag di ottimizzazione a tempo di compilazione:
C:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
Adesso possiamo renderci bene conto di quanto sia importante ancora oggi scrivere programmi efficienti, perché i miglioramenti alla potenza di calcolo delle macchine non consentono comunque di trattare problemi esponenziali (o in questo caso algoritmi esponenziali).
Ultima modifica:
