Cosa è l’Analisi degli Algoritmi?¶

Quando due programmi risolvono lo stesso problema, come si fa a dire se uno è meglio dell’altro?

In particolare ci sono molti algoritmi per risolvere lo stesso problema. Inoltre ci sono molti modi di implementare lo stesso algoritmo, dipendentemente dalle strutture dati usate per esempio o dal linguaggio di programmazione.

A questo proposito, osserviamo la funzione mostrata in ActiveCode 1. Questa funzione risolve il problema del calcolo della somma dei primi n interi.

def sumOfN(n):
   theSum = 0
   for i in range(1,n+1):
       theSum = theSum + i

   return theSum

print(sumOfN(10))

Summation of the First n Integers (active1)

Adesso osserviamo la funzione in ActiveCode 2. Questa versione è sicuramente meno leggibile e c’è un assegnamento evitabile.

def foo(tom):
    fred = 0
    for bill in range(1,tom+1):
       barney = bill
       fred = fred + barney

    return fred

print(foo(10))

Another Summation of the First n Integers (active2)

La funzione sumOfN è meglio della funzione``foo`` in termini di leggibilità, a causa anche del nome dato alle variabili.

L’analisi degli algoritmi confronta invece due algoritmi in termini di efficienza, ovvero confrontando la quantità di calcolo e di risorse computazionali che entrambi richiedono. In questi termini, i due programmi sopra sono molto simili nel senso che applicano lo stesso algoritmo, anche se uno spreca una variabile in più.

A questo punto, è importante pensare a cosa vuol dire risorse computazionali. In particolare, ci sono due criteri che possono essere considerati.

Il primo criterio è lo spazio o la memoria usata da un algoritmo. Questa quantità è tipicamente dipendente dall’input del problema.
Un criterio alternativo allo spazio è il tempo, per cui confrontare due algoritmi significa controllare la quantità di tempo necessaria per completare il loro compito. Questa misure è chiamata “tempo di esecuzione” dell’algoritmo.

Un modo per misurare il tempo di esecuzione della funzione sumOfN è quello di fare un benchmark. Questo significa che misureremo il tempo richiesto dal programma usando il modulo time, in cui c’è una funzione time che ritorna il numero di cicli di clock in secondi passati da un certo momento di riferimento. Chiamando questa funzione due volte, all’inizio e alla fine, e calcolando la differenza, possiamo sapere il numero di secondi esatti che sono stati usati per l’esecuzione del programma.

Listing 1

import time

def sumOfN2(n):
   start = time.time()

   theSum = 0
   for i in range(1,n+1):
      theSum = theSum + i

   end = time.time()

   return theSum,end-start

Listing 1 mostra la funzione sumOfN originale con le chiamate a time. La funzione ritorna una tupla che contiene il tempo (in secondi). Se la eseguiamo 5 volte, possiamo ottenere:

>>>for i in range(5):
       print("Sum is %d required %10.7f seconds"%sumOfN(10000))
Sum is 50005000 required  0.0018950 seconds
Sum is 50005000 required  0.0018620 seconds
Sum is 50005000 required  0.0019171 seconds
Sum is 50005000 required  0.0019162 seconds
Sum is 50005000 required  0.0019360 seconds

Il tempo è più meno lo stesso e in media è 0.0019 seconds. Che succede se eseguiamo la funzione con 100 mila interi?

>>>for i in range(5):
       print("Sum is %d required %10.7f seconds"%sumOfN(100000))
Sum is 5000050000 required  0.0199420 seconds
Sum is 5000050000 required  0.0180972 seconds
Sum is 5000050000 required  0.0194821 seconds
Sum is 5000050000 required  0.0178988 seconds
Sum is 5000050000 required  0.0188949 seconds
>>>

Ancora una volta, il tempo sembra più o meno lo stesso, ma sembra metterci 10 volte il tempo che ci metteva prima. Per n uguale a 1 milione:

>>>for i in range(5):
       print("Sum is %d required %10.7f seconds"%sumOfN(1000000))
Sum is 500000500000 required  0.1948988 seconds
Sum is 500000500000 required  0.1850290 seconds
Sum is 500000500000 required  0.1809771 seconds
Sum is 500000500000 required  0.1729250 seconds
Sum is 500000500000 required  0.1646299 seconds
>>>

Anche in questo caso, ci sta mettendo 10 volte di più del caso precedente.

Adesso consideriamo ActiveCode 3, che mostra un modo diverso di risolvere il problema della somma. Questa funzione, sumOfN3, si avvale dell’equazione \(\sum_{i=1}^{n} i = \frac {(n)(n+1)}{2}\) per calcolare la somma dei primi n interi senza iterare.

def sumOfN3(n):
   return (n*(n+1))/2

print(sumOfN3(10))

Summation Without Iteration (active3)

Se rifacciamo i test di prima con la funzione sumOfN3, usando 5 diversi valori di n (10,000, 100,000, 1,000,000, 10,000,000, and 100,000,000), otteniamo il seguente risultato:

Sum is 50005000 required 0.00000095 seconds
Sum is 5000050000 required 0.00000191 seconds
Sum is 500000500000 required 0.00000095 seconds
Sum is 50000005000000 required 0.00000095 seconds
Sum is 5000000050000000 required 0.00000119 seconds

Due cose da notare:

Questi tempi sono molto minori di quelli che abbiamo verificato con il precedente algoritmo.
Non importa il valore di n. Il comportamento di sumOfN3 non è influenzato dal valore di n.

Nella soluzione iterativa, i tempi crescono con n. Tuttavia lo studio che abbiamo fatto dipende dal computer che abbiamo usato o dal linguaggio di programmazione.

Un modo migliore per caratterizzare l’esecuzione dei nostri algoritmi dovrebbe prescindere dalla macchina usata, per giudicare solo l’algoritmo indipendentemente dagli aspetti collaterali.

Next Section - La Notazione O-Grande