inserisci una discussione prematura-is-the-root-of-all-evil
Detto questo, ecco alcune abitudini in cui sono entrato per evitare l'efficienza non necessaria, e in alcuni casi, rendere il mio codice più semplice e più corretto.
Questa non è una discussione sui principi generali, ma su alcune cose da tenere presente per evitare l'introduzione di inutili inefficienze nel codice.
Conosci il tuo big-O
Questo dovrebbe probabilmente essere unito alla lunga discussione di cui sopra. È quasi logico che un ciclo all'interno di un ciclo, in cui il ciclo interno ripete un calcolo, sarà più lento. Ad esempio:
for (i = 0; i < strlen(str); i++) {
...
}
Ciò richiederà una quantità di tempo orrenda se la stringa è veramente lunga, poiché la lunghezza viene ricalcolata ad ogni iterazione del ciclo. Nota che GCC effettivamente ottimizza questo caso perché strlen()
è contrassegnato come una pura funzione.
Quando si ordina un milione di numeri interi a 32 bit, tipi di bolle sarebbe il modo sbagliato di andare . In generale, l'ordinamento può essere fatto in O (n * log n) tempo (o meglio, nel caso di radix sort), quindi a meno che non si sappia che i dati saranno piccoli, cercare un algoritmo che sia almeno O (n * log n).
Allo stesso modo, quando si ha a che fare con i database, tenere conto degli indici. Se si SELECT * FROM people WHERE age = 20
, e non si ha un indice su persone (età), richiederà una scansione sequenziale O (n) piuttosto che una scansione indice O (log n) molto più veloce.
Gerarchia aritmetica intera
Quando si programma in C, tenere presente che alcune operazioni aritmetiche sono più costose di altre. Per i numeri interi, la gerarchia è simile a questa (prima la meno cara):
Certo, il compilatore di solito ottimizza automaticamente cose come n / 2
in n >> 1
se stai prendendo di mira un computer mainstream, ma se stai prendendo di mira un dispositivo incorporato, potresti non ottenere quel lusso.
Inoltre, % 2
e & 1
hanno semantica diversa. La divisione e il modulo di solito arrotonda verso lo zero, ma è definito dall'implementazione. Il buon vecchio >>
e il &
arrotonda sempre verso l'infinito negativo, il che (secondo me) ha molto più senso. Ad esempio, sul mio computer:
printf("%d\n", -1 % 2); // -1 (maybe)
printf("%d\n", -1 & 1); // 1
Quindi, usa ciò che ha senso. Non pensare di essere un bravo ragazzo usando % 2
quando avresti dovuto scrivere & 1
.
Operazioni costanti in virgola mobile
Evita le operazioni pesanti in virgola mobile come pow()
e log()
nel codice che non ne ha veramente bisogno, specialmente quando si ha a che fare con numeri interi. Prendi, ad esempio, la lettura di un numero:
int parseInt(const char *str)
{
const char *p;
int digits;
int number;
int position;
// Count the number of digits
for (p = str; isdigit(*p); p++)
{}
digits = p - str;
// Sum the digits, multiplying them by their respective power of 10.
number = 0;
position = digits - 1;
for (p = str; isdigit(*p); p++, position--)
number += (*p - '0') * pow(10, position);
return number;
}
Non solo questo uso di pow()
(e le int
< - > double
conversioni necessarie per usarlo) è piuttosto costoso, ma crea un'opportunità per la perdita di precisione (per inciso, il codice sopra non avere problemi di precisione). Ecco perché mi diverto quando vedo questo tipo di funzione usata in un contesto non matematico.
Inoltre, nota come l'algoritmo "intelligente" di seguito, che moltiplica per 10 per ogni iterazione, è in realtà più conciso del codice sopra:
int parseInt(const char *str)
{
const char *p;
int number;
number = 0;
for (p = str; isdigit(*p); p++) {
number *= 10;
number += *p - '0';
}
return number;
}