Ottimizzare C++/Tecniche generali di ottimizzazione: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m ha spostato C++ ottimizzato/Tecniche generali di ottimizzazione a Ottimizzare C++/Tecniche generali di ottimizzazione: correggo il titolo |
Nessun oggetto della modifica |
||
Riga 1:
In questa sezione vengono proposte alcune tecniche di ottimizzazione algoritmica di ampia utilizzabilità, e sostanzialmente indipendenti sia dal linguaggio di programmazione, che dalla piattaforma software e hardware.
4.1.1. Per eseguire operazioni di input/output, invece di usare le primitive del linguaggio, usa direttamente le chiamate al sistema operativo.▼
▲
Le primitive di I/O dei linguaggi di programmazione sono pensate soprattutto tenendo conto della comodità d’uso invece che le prestazioni, in quanto solitamente per tale codice il collo di bottiglia non è il processore, ma la periferica. Tuttavia, a volte si vuole ottimizzare anche il codice eseguito per effettuare operazioni di I/O. Inoltre, nel caso del C++, la libreria degli stream è particolarmente inefficiente. Le chiamate al sistema operativo garantiscono la massima efficienza, a costo di rinunciare alla portabilità ad altri sistemi operativi, e di dover gestire manualmente la formattazione, la bufferizzazione, e gli errori.
I numeri in formato binario occupano mediamente meno spazio, e quindi richiedono meno tempo per essere letti da disco e scritti su disco, ma, soprattutto, scrivendo e leggendo i dati nello stesso formato che hanno in memoria non c’è bisogno di nessuna conversione da o verso il formato testuale.
Mentre le operazioni di posizionamento (seek) richiedono un certo tempo, con i memory mapped file tali operazioni diventano semplici assegnazioni a un puntatore.
Line 20 ⟶ 24:
A rigore, questa è una tecnica dipendente dalla piattaforma, in quanto la funzionalità dei memory mapped files non esiste in tutti i sistemi operativi. Tuttavia, dato che tale funzionalità esiste in tutti i principali sistemi operativi dotati di memoria virtuale, questa tecnica si può considerare di ampia applicabilità.
Le tecniche di caching si basano sul principio che se una funzione pura (o funzione matematica) deve essere calcolata più volte per un dato argomento, e tale calcolo richiede parecchio tempo, si risparmia tempo salvando il risultato la prima volta che si esegue la funzione, e ritornando il valore salvato le volte successive.
L’accesso a un array, soprattutto se si trova nella cache dei dati del processore, è molto veloce. Per esempio, dovendo calcolare la radice quadrata di un numero intero compreso tra 0 e 9, si può usare la seguente funzione:
double sqrt10(int i) {
static double lookup_table[] = {
0, 1, sqrt(2.), sqrt(3.), 2,
sqrt(5.), sqrt(6.), sqrt(7.), sqrt(8.), 3,
};
assert(0 <= i && i < 10);
return lookup_table[i];
}
Per esempio, invece di scrivere:
double f(double x, double y) {
return sqrt(x * x + y * y);
}
double f(double x, double y) {
static double prev_x = 0;
static double prev_y = 0;
static double result = 0;
if (x == prev_x && y == prev_y) {
return result;
}
prev_x = x;
prev_y = y;
result = sqrt(x * x + y * y);
return result;
}
Ovviamente, questa soluzione peggiora le prestazioni, invece di migliorarle, nel caso in cui la funzione è chiamata con parametri variabili spesso, o se il confronto tra i parametri nuovi e quelli vecchi richiede più tempo del calcolo della funzione.
Questo algoritmo è detto anche "caching a un posto", in quanto si memorizza solo una coppia argomento-risultato.
In alcuni casi, la funzione viene chiamata con parametri variabili, ma appartenenti a un insieme molto limitato. In tale caso si può implementare una cache a più posti, invece di una cache a un singolo posto, come quella appena vista. Ecco un esempio, riferito alla stessa funzione di sopra:
double f(double x, double y) {
static const int n_buckets = 8; // Dovrebbe essere una potenza di 2
static struct {
double x; double y; double result;
} cache[n_buckets];
static int last_read_i;
static int last_written_i;
int i = last_read_i;
do {
if (cache[i].x == x && cache[i].y == y) {
return cache[i].result;
}
i = (i + 1) % n_buckets;
} while (i != last_read_i);
last_read_i = last_written_i = (last_written_i + 1) % n_buckets;
cache[last_written_i].x = x;
cache[last_written_i].y = y;
cache[last_written_i].result = sqrt(x * x + y * y);
return cache[last_written_i].result;
}
Si noti anche che negli esempi si assumeva che la funzione valesse 0 per i parametri di input entrambi zero. In caso contrario, si dovrebbe, o inizializzare il campo result al valore appropriato, o aggiungere un flag che indica se tale campo ha un valore valido e controllare tale flag, o usare un valore inammissibile per il campo result come indicatore del fatto che non contiene un valore valido.
Line 98 ⟶ 105:
Questo algoritmo è detto anche "caching a N posti".
4.3.1. Prima di confrontare una stringa con una serie di altre stringhe, trasforma tutte le stringhe in lettere maiuscole (o in minuscole), ed esegui il confronto distinguendo tra minuscole e maiuscole (case-sensitive).▼
▲
Il confronto tra stringhe case-insensitive costa di più del confronto case-sensitive.
Supponiamo di avere una collezione (o un insieme di collezioni) incapsulati in una classe. Tale classe espone uno o più metodi per estrarre (o filtrare) da tale collezione un sottoinsieme. Un modo di ottenere ciò è costruire una nuova collezione, copiarci i dati estratti, e restituire tale collezione al chiamante. Questa tecnica è però inefficiente, perché ognuna delle suddette operazioni è costosa.
Line 111 ⟶ 121:
Questa tecnica è indipendente dal linguaggio di programmazione, in quanto il concetto di iteratore è un design pattern, implementabile in qualsiasi linguaggio.
Se l'array viene saltuariamente modificato, l'algoritmo può essere ancora competitivo, purché le modifiche siano molte meno delle ricerche.
Line 118 ⟶ 129:
Se invece la modifica è più massiccia, conviene ricreare tutto l'array.
L’algoritmo countingsort ha complessità O(N+M), dove N è il numero di elementi da ordinare e M è il range delle chiavi di ordinamento, cioè la differenza tra la chiave massima e la chiave minima. Nel caso in cui si vogliano ordinare N elementi la cui chiave è un numero intero appartenente a un intervallo di non oltre 2 * N valori, questo algoritmo può essere notevolmente più veloce di quicksort. A volte è più veloce anche per range più grandi, fino a 50 * N.
Questo algoritmo può essere usato anche per un ordinamento parziale; per esempio, se la chiave è un intero compreso tra zero e un miliardo, si può ordinare solamente in base al byte più significativo della chiave, così da ottenere un ordine tale per cui per ogni n vale la formula a[n] < a[n + 1] + 256*256*256.
La “slist”, pur avendo molte limitazioni, occupa meno memoria ed è più veloce.
Infatti, tipicamente, l’intestazione di un oggetto “std::list” contiene un puntatore alla cima, un puntatore al fondo della lista, e il contatore del numero di elementi, mentre l’intestazione di un oggetto “slist” contiene solo un puntatore alla cima della lista. Inoltre, tipicamente, ogni nodo di un oggetto “std::list” contiene un puntatore all’elemento precedente e un puntatore all’elemento successivo, mentre ogni nodo di un oggetto “slist” contiene solo un puntatore all’elemento successivo. Infine, ogni inserimento di un elemento da un oggetto “std::list” deve aggiornare quattro puntatori e un contatore, mentre ogni inserimento da un oggetto “slist” deve aggiornare solo due puntatori.
In STL c'è l'algoritmo partition, che è più veloce dell'algoritmo sort, in quanto ha complessità O(N).
In STL c'è l'algoritmo stable_partition, che è leggermente più lento dell'algoritmo partition, e c'è l'algoritmo stable_sort, che è leggermente più lento dell'algoritmo sort.
In STL c'è l'algoritmo nth_element, che, pur essendo è leggermente più lento dell'algoritmo stable_partition, è notevolmente più veloce dell'algoritmo sort, in quanto ha complessità O(N).
In STL ci sono gli algoritmi partial_sort e partial_sort_copy, che, pur essendo più lenti di dell'algoritmo nth_element, sono tanto più veloci dell'algoritmo sort quanto più è breve la sequenza parziale da ordinare rispetto a quella totale.
|