最佳化 C++/通用最佳化技術/記憶化
記憶化 技術（又稱快取技術）基於這樣的原理：如果必須重複計算一個純函式，即一個引用透明 函式（又稱數學函式），對於相同的引數，並且如果這種計算需要大量時間，可以透過儲存第一次評估的結果並在其他時間檢索該結果來節省時間。
如果您經常需要呼叫一個純函式，該函式的域為一個小整數區間，則可以預先計算（在編譯時或程式啟動時）函式在域中每個值的全部值，並將它們放入一個名為查詢表的靜態陣列中。當您需要函式在域中特定值的函式值時，讀取該陣列的相應值。
例如，要計算 0 到 9 之間的整數的平方根，以下函式更快
double sqrt10(int i) {
static const 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];
}
陣列訪問非常快，尤其是在訪問的單元在處理器資料快取中的情況下。因此，如果查詢表不大，幾乎可以肯定其訪問速度快於評估函式。
如果查詢表很大，由於記憶體佔用空間、預先計算所有值所需的時間（如果它不適合處理器資料快取），它可能不再高效。但如果要評估的函式很慢，它被呼叫很多次，而且您可以使用大量的記憶體，請考慮使用一個大小達到幾百 KB 的查詢表。很少有超過 1 MB 的效率。
如果您經常需要用相同的引數呼叫一個純函式，那麼第一次呼叫該函式時，將引數和結果儲存在靜態變數中。再次呼叫該函式時，將新的引數與已儲存的引數進行比較；如果匹配，則返回已儲存的結果，否則計算結果並存儲新的引數和新的結果。
例如，而不是以下函式
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;
}
請注意，為了更快地處理，該函式不需要在整個程式會話中都使用相同的引數呼叫。它只要在某些時間使用相同的引數呼叫，然後在其他時間使用其他引數呼叫即可。在這種情況下，計算僅在引數更改時執行。
顯然，此技術可能會降低速度，而不是提高速度，因為該函式幾乎總是使用更改後的引數呼叫，或者比較新的引數和舊的引數所需的時間比函式本身的計算時間更長。
請注意，如果您使用靜態變數，此函式不是執行緒安全的，也不能遞迴呼叫。如果此函式必須由多個執行緒併發呼叫，則需要用每個執行緒都不同的變數替換靜態變數。
另請注意，在示例中，假定該函式在兩個引數都為零時值為零。如果沒有，則應選擇其他解決方案，例如以下解決方案之一
- 用對應於全零引數的值初始化變數result。
- 用永遠不會作為引數傳遞的值初始化變數prev_x 和 prev_y。
- 新增一個靜態標誌，指示靜態變數是否保持有效值，並在每次呼叫時檢查該標誌。
如果您經常需要用大多數情況下屬於一個小域的引數呼叫一個純函式，請使用一個最初為空的靜態對映（又稱字典）。當呼叫該函式時，在對映中搜索函式引數。如果找到，則返回關聯的值，否則計算結果並將引數-結果對插入對映中。
以下示例使用陣列實現對映。本節“單一位置快取”準則的示例中使用了相同的函式
double f(double x, double y) {
static const int n_buckets = 8; // should be a power of 2
static struct {
double x; double y; double result;
} cache[n_buckets];
static int last_read_i = 0;
static int last_written_i = 0;
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;
}
有些函式雖然理論上域很大，但大多數情況下只用很少幾個不同的引數呼叫。
例如，文字處理器可能安裝了許多字型，但在典型文件中，只有幾種字型用於大多數字符。渲染函式必須處理文件中每個字元的字型，通常會使用很少幾個不同的值呼叫。對於這種情況，N 位置快取比單一位置快取更可取，如示例所示。
本節“單一位置快取”準則中關於靜態變數的說明也適用於這種情況。
對於小型快取（在示例中，有 8 個位置），最有效的演算法是陣列上的順序掃描。但是，要實現更大的快取，搜尋樹或雜湊表可能更有效。此外，示例中的快取大小固定，但它可能是可變大小的快取。
通常，最後讀取的元素最有可能在下一次呼叫時使用。因此，如示例所示，可能需要儲存其位置，並從該位置開始搜尋。
如果快取不會無限擴充套件，則存在選擇要替換的元素的問題。顯然，最好替換在下一次呼叫中最不可能被請求的元素。在示例中，假定在快取中的元素中，第一個插入的元素在下一次呼叫中最不可能被請求。因此，寫入迴圈地掃描陣列。通常，更好的標準是替換最近最少讀取的元素，而不是最近最少寫入的元素。要實現這種標準，需要更復雜的演算法。