Ottimizzare C++/Tecniche generali di ottimizzazione: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
m + categoria |
||
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.
=== Per eseguire operazioni di input/output, invece di usare le primitive del linguaggio, usa direttamente le chiamate al sistema operativo. ===
Riga 32:
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:
<source lang=cpp>
</source>
=== Se devi calcolare spesso una funzione con gli stessi argomenti, salva in variabili statiche gli argomenti e il risultato. Quando devi calcolare la funzione, confronta i nuovi argomenti con quelli vecchi. Se coincidono, rendi il risultato memorizzato, altrimenti calcola il risultato e memorizza nelle variabili statiche gli argomenti e il risultato. ===
Per esempio, invece di scrivere:
<source lang=cpp>
</source>
puoi scrivere:
<source lang=cpp>
</source>
Nota che, per avere un vantaggio prestazionale, non è necessario che la funzione sia chiamata con gli stessi parametri per tutta l’esecuzione del programma. È sufficiente che sia chiamata alcune volte con gli stessi parametri, poi altre volte con altri parametri, e così via. In tale caso, il calcolo viene effettuato solo al cambiamento dei parametri.
Riga 74:
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:
<source lang=cpp>
</source>
Nota che l’uso di variabili statiche rende la routine non più thread-safe. Se questa routine deve poter essere chiamata contemporaneamente da più thread, è necessario sostituire le variabili statiche con variabili distinte per ogni thread.
Riga 134:
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
=== Se per una lista ti basta l’iteratore in avanti, inserire gli elementi solo all’inizio o dopo l’elemento corrente, e non ti serve sapere quanti elementi ci sono nella lista, usa un oggetto “slist” (o in C++0x, “forward_list”). ===
Riga 157:
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.
[[Categoria:Ottimizzare C++|Tecniche generali di ottimizzazione]]
|