Ottimizzare C++/Tecniche generali di ottimizzazione/Caching: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
RamaccoloBot (discussione | contributi)
m Bot: Sostituzione automatica (-[[Categoria:Ottimizzare C++|Ottimizzare C++/Tecniche generali di ottimizzazione/ +[[Categoria:Ottimizzare C++|)
Nessun oggetto della modifica
Riga 1:
{{Ottimizzare C++}}
 
Le tecniche di ''caching'' (in inglese chiamate anche tecniche di [[w:Memoizzazione|''memoizationmemoizzazione'']]) si basano sul principio che se una funzione pura ossia una funzione [[w:Trasparenza referenziale|''referenzialmente trasparente'']] (cioè una [[w:Funzione (matematica)|funzione matematica]]) deve essere calcolata più volte per lo stesso argomento, e se tale calcolo richiede parecchio tempo, si risparmia tempo salvando il risultato la prima volta che si esegue la funzione, e recuperando il valore salvato le volte successive.
 
=== ''Look-up table'' ===
 
'''Se devi calcolare spesso una funzione avente come dominio un piccolo intervallo di numeri interi, pre-calcola (in fase di sviluppo del software o in fase di inizializzazione dell’applicazione) tutti i valori della funzione per ogni valore del dominio e ponili in un array statico, detto "[[w:Look-Up Table|''lookup-table"'']]. Quando devi calcolare il valore della funzione per un dato valore del dominio, preleva l'elemento corrispondente di tale array.'''
 
L'accesso a un array, soprattutto se si trova nella cache dei dati del processore, è molto veloce. Pertanto, se la look-up table non è grande, quasi sicuramente è più veloce della funzione che si deve calcolare.
Riga 22:
</source>
 
Se la funzione da calcolare è piuttosto lenta, e si ha a disposizione molta memoria, può essere opportuno usare una ''look-up table'' anche se risulta piuttosto grande. Tuttavia, raramente è opportuno definire una ''look-up table'' più grande di un megabyte.
 
=== Caching a un posto ===
Riga 96:
Per cache piccole, nel caso sopra di 8 elementi, l’algoritmo più efficiente è la scansione sequenziale su un array. Tuttavia, se si volesse fare una cache di dimensioni maggiori, un albero di ricerca o una hashtable sarebbero più efficienti.
 
La ricerca nella cache parte sempre dall'ultimo elemento letto, in quanto solitamente è il più probabile. La scrittura nella cache di un elemento non presente sovrascrive l'elemento successivo all'ultimo elemento scritto, cioè si sostituisce l'elemento meno recentemente ''scritto'. Si avrebbe un algoritmo migliore sostituendo l'elemento meno recentemente ''letto'', ma ciò richiederebbe che si prendesse nota dell'ordine di accesso.
 
[[Categoria:Ottimizzare C++|Caching]]
{{Avanzamento|75100%|2325 maggio 2008}}