Dedicare un post al calcolo della media può sembrare assurdo, ma in realtà gli aspetti ingegneristici che sono dietro l’implementazione di concetti matematici così semplici non sono assolutamente trascurabili. In questo post si vuole mostrare come una soluzione lineare non è sempre la più corretta.
Partiamo dalla definizione di media aritmetica. La media aritmetica è un numero calcolata sommando tutti i valori a disposizione e dividendo il risultato per il numero complessivo dei dati. Per utilizzare un simbolismo matematico:
Una possibile implementazione in java di una classe che esegue la media aritmetica di N numeri è:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
import java.util.ArrayList; import java.util.List; public class Mean { private List<Integer> values = new ArrayList<Integer>(); public void add( Integer value ) { this.values.add( value ); } public Double execute() { Integer mean = 0; for ( Integer value : values ) { mean += value; } return mean.doubleValue() / values.size(); } } |
Tutto il lavoro è eseguito dal metodo execute che esegue il ciclo sui valori della lista sommandoli e dividendo il risultato per il numero di elementi. Vediamo ora cosa accade con il semplice Main di test mostrato di seguito:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public class MeanTest { public static void main(String[] args) throws IOException { Mean m1 = new Mean(); m1.add( 5 ); m1.add( 6 ); m1.add( 7 ); System.out.println( "Media di 5, 6, 7: " + m1.execute() ); Mean m2 = new Mean(); m2.add( Integer.MAX_VALUE ); m2.add( Integer.MAX_VALUE ); m2.add( Integer.MAX_VALUE ); m2.add( Integer.MAX_VALUE ); System.out.print( "Media di 4 volte " + Integer.MAX_VALUE + ": " ); System.out.printf( "%f\n", m2.execute() ); } } |
|
1 2 |
Media di 5, 6, 7: 6.0 Media di 4 volte 2147483647: -1,000000 |
Il primo risultato è corretto mentre il secondo è palesemente sbagliato. Quello che è accaduto è che la somma dei tre valori 2147483647 ha ecceduto il valore massimo rappresentabile con un intero, determinando un overflow che, java ha gestito tornando al valore minimo e proseguendo da questo. In altre parole: Integer.MAX_VALUE + 1 == Integer.MIN_VALUE.
Per ovviare all’inconveniente possiamo progettare una versione dell’algoritmo di media aritmetica più robusto seguendo i seguenti semplici passi “matematici”:
Al passo 5 è evidente che la media di N numeri è calcolabile a partire dalla conoscenza della media dei primi N-1 numeri della sequenza. Questo consente di determinare un algoritmo di calcolo incrementale che non richiede la somma di tutti i valori ma esegue una serie di operazioni parziali che limitano il pericolo di avere overflow. Il codice risultante è:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
import java.util.ArrayList; import java.util.List; public class Mean { Double mean = 0D; private List<Integer> values = new ArrayList<Integer>(); public Double add( Integer value ) { values.add( value ); mean = mean * ( values.size() -1 ) / values.size() + value / values.size(); return mean; } } |
add restituisce la media parziale calcolata sino all’ultimo valore inserito.