优化 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 个位置），最有效的算法是数组上的顺序扫描。但是，要实现更大的缓存，搜索树或哈希表可能更有效。此外，示例中的缓存大小固定，但它可能是可变大小的缓存。
通常，最后读取的元素最有可能在下一次调用时使用。因此，如示例所示，可能需要保存其位置，并从该位置开始搜索。
如果缓存不会无限扩展，则存在选择要替换的元素的问题。显然，最好替换在下一次调用中最不可能被请求的元素。在示例中，假定在缓存中的元素中，第一个插入的元素在下一次调用中最不可能被请求。因此，写入循环地扫描数组。通常，更好的标准是替换最近最少读取的元素，而不是最近最少写入的元素。要实现这种标准，需要更复杂的算法。