Informatica I - rilevamento delle prestazioni di un programma

Valutazione delle prestazioni di un algoritmo

Le prestazioni di un algoritmo vengono valutate in funzione della dimensione dei dati trattati. Per valutare l’efficienza di un algoritmo si misura il tempo in cui viene eseguito su insiemi di dati di dimensioni via via maggiori.

Il tempo non va misurato con un cronometro, perché parte del tempo reale di esecuzione non dipende dall’algoritmo: (caricamento della JVM, caricamento delle classi del programma, lettura dei dati dallo standard input, visualizzazione dei risultati).

Il tempo di esecuzione di un algoritmo va misurato all’interno del programma con il metodo System.currentTimeMillis(), statico che, ad ogni invocazione, restituisce un numero di tipo long che rappresenta il numero di millisecondi trascorsi da un evento di riferimento (la mezzanotte del 1 gennaio 1970). Ciò che interessa è la differenza tra due valori: si invoca System.currentTimeMillis() immediatamente prima e dopo l’esecuzione dell’algoritmo (escludendo le operazioni di input/output dei dati).

Esempio: Selection Sort

Collaudiamo le prestazioni del metodo in funzione della dimensione dei dati (ovvero in funzione della lunghezza n dell'array da ordinare). Effettuiamo molte prove di ordinamento di array di numeri casuali e misuriamo il tempo di esecuzione su ciascuna prova, usando System.currentTimeMillis().

Si nota che l’andamento del tempo di esecuzione non è lineare: se n diventa il doppio, il tempo diventa circa il quadruplo. Quindi il tempo di esecuzione ha andamento quadratico. La dipendenza funzionale è di tipo parabolico: 2T(n) = a n²