Quali sono alcune comuni opportunità di ottimizzazione algoritmica di cui tutti dovrebbero essere a conoscenza? Recentemente ho revisionato / revisionato del codice da un'applicazione, e ho notato che sembrava funzionare molto più lentamente di quanto avrebbe potuto. Il seguente loop si è rivelato essere il colpevole,
...
float s1 = 0.0;
for (int j = 0; j < size; ++j) {
float diff = a[j] - b[j];
s1 += (diff*diff * c[j]) + log(1.0/c[j]);
}
...Questo è equivalente a,
Σ j {(a j -b j ) 2 * c j + log (1 / c j )}
Ogni volta che si esegue il programma, questo ciclo viene chiamato forse più di 100k volte, quindi le chiamate ripetute per registrare e dividere risultano in un risultato di prestazioni molto grande. Un rapido sguardo alla rappresentazione del sigma rende abbastanza chiaro che esiste una soluzione banale, assumendo che tu ricordi le tue identità di logaritmo abbastanza bene da individuarlo,
Σ j {(a j -b j ) 2 * c j + log (1 / c j )} =
Σ j {(a j -b j ) 2 * c j } + Σ j {log (1.0 / c j )} =
Σ j {(a j -b j ) 2 * c j } + log (1.0 / (Π j c j ))
e porta a uno snippet molto più efficiente,
...
float s1 = 0.0;
float s2 = 1.0;
for (int j = 0; j < size; ++j) {
float diff = a[j] - b[j];
s2 *= c[j];
s1 += (diff*diff * c[j]);
}
s1 += log(1.0/s2);
...questo ha comportato un notevole aumento della velocità e dovrebbe essere entrato nell'implementazione originale. Presumo che non fosse perché gli sviluppatori originali non erano a conoscenza, o non erano 'attivamente consapevoli' di questo semplice miglioramento.
Questo mi ha fatto chiedere, quali altre, simili, comuni opportunità e I perdere o trascurare, e come posso imparare a individuarle meglio? Non sono tanto interessato a casi limite complessi per particolari algoritmi, ma piuttosto esempi come quello sopra che coinvolgono quelli che potreste pensare come concetti "ovvi" che emergono frequentemente, ma che altri potrebbero non farlo.