第3章
缓存与记忆术
在1.8节看到了一个普通的递归函数有时执行得非常糟糕。解决许多这些性能问题的一个简单和普遍的方法，和非递归环境里出现的一样，就是缓存（caching）。
考虑一个程序把图像从一种格式转换到另一种格式。特定的，假设输入的是流行的GIF格式，输出是将要发送到打印机的。打印机不是那种书桌上的小设备，而是一个拥有巨大打印压力的大公司要在周四下午打印上百万份杂志的那种。
该打印机希望图像是一种特定的CMYK格式。CMYK代表“青-紫红-黄-黑”，即该打印机用来打印杂志的四种专用墨水的颜色。然而，GIF 图像的颜色由RGB数值指定，该数值是计算机显示器显示图像时发射的红、绿和蓝光的明暗程度。需要把适合显示器的RGB数值转换成适合打印的CMYK数值。
该转换仅是一些简单的算术运算：
### Code Library: RGB-CMYK
sub RGB_to_CMYK {
my ($r, $g, $b) = @_;
my ($c, $m, $y) = (255-$r, 255-$g, 255-$b);
my $k = $c < $m ? ($c < $y ? $c : $y)
: ($m < $y ? $m : $y); # Minimum
for ($c, $m, $y) { $_ -= $k }
[$c, $m, $y, $k];
}现在书写程序的剩余部分，这部分程序打开GIF文件，每次读取一个像素，对每个像素调用RGB_to_CMYK()，然后用合适的格式写出CMYK数值结果。
这里有一个小问题。假设GIF图像是1024像素宽，768像素高，总共786 432像素。需要执行786 432次RGB_to_CMYK()调用。这看上去还不错，但有个例外：GIF格式定义的方式决定了没有GIF图像能包含超过256种不同的颜色。即在786 432次调用中，至少有786 176次是在浪费时间，因为之前已经做过的相同的计算了。如果能指出如何保存RGB_to_CMYK()计算结果并在合适的时候取出，就可以赢回一些性能。
在Perl里，当考虑要检查是否已经看到过某物时，答案几乎总是使用散列。这次也不例外。如果能使用RGB数值作为一个散列键，就可以制作一个散列记录之前是否已经看到过某套RGB数值，以及如果看到了，相应的CMYK数值是多少。那么程序的逻辑将像这样进行：要转换一套RGB数值到一套CMYK数值，首先在散列里寻找RGB数值。如果没有，就和先前一样计算，把结果存在散列里，并照常返回该结果。如果数值在散列里，那就从散列获得CMYK数值并跳过第二次计算而返回该数值。
代码如下：
### Code Library: RGB-CMYK-caching
my %cache;
sub RGB_to_CMYK {
my ($r, $g, $b) = @_;
my $key = join ',', $r, $g, $b;
return $cache{$key} if exists $cache{$key};
my ($c, $m, $y) = (255-$r, 255-$g, 255-$b);
my $k = $c < $m ? ($c < $y ? $c : $y)
: ($m < $y ? $m : $y); # Minimum
for ($c, $m, $y) { $_ -= $k }
return $cache{$key} = [$c, $m, $y, $k];
}假设以参数(128,0,64)调用RGB_to_CMYK()。第一次这么做的时候，函数将在%cache散列里寻找键'128,0,64'，散列里什么也没有，所以它将继续，照常执行运算，然后在最后一行，把结果存入$cache{'128,0,64'}，并返回结果。第二次以相同参数调用函数时，它算出相同的键，并返回$cache{'128,0,64'}的值而不再做任何多余的运算。当在缓存里找到了需要的值而无需更多运算时，那就称为一次缓存命中（cache hit）；当计算了正确的键但是发现还没有值缓存在那个键上时，这就称为一次缓存脱靶（cache miss）。
当然有一种可能就是额外的程序逻辑和散列搜索会耗尽因避免运算得到的好处。这真正取决于原先的运算所消耗的时间和缓存命中的可能性。当原先的运算消耗时间很长，缓存更可能是赚了。为了确定，对两个版本的函数进行仔细的基准比较测试。但是为了帮助建立对各类权衡的期许的直觉，将简短地介绍理论。
假设实际函数的典型调用需耗时f。带记忆的版本的平均耗时将决定于两个参数：缓存管理的开销K以及对任何特定调用的缓存命中的概率h。在从未缓存命中过的极端情况下，h是零；随着缓存命中的可能性增加，h趋近于1。
对于一个带记忆的函数，每次调用的平均时间将至少是K，由于每次调用必须检查缓存，如果缓存脱靶，还得加上一个额外的f，总计是K + (1h)f。函数的不带记忆的版本，当然，总是耗时f，因此不同之处仅是hfK。如果K < hf，函数的带记忆的版本将比不带记忆的更快。为加速带记忆的版本，可以增加缓存命中率h，或减少缓存管理的开销K。当f很大时，就更容易达成K < hf，所以缓存技术对运行时间长的原始函数更可能有效。在最差情况下，没有一次命中，h=0，所以“加速”实际上是减速 K。
