在第 1.8 节 “当出现递归时”中我们看到，现实中的递归函数可能性能非常差。解决绝大部分这种性能问题的最容易、最通用的方案就是缓存。不仅如此，在非递归的环境中也经常要使用缓存。

假设有个程序可以将图像从一种格式转换成另一种格式。假设输入为流行的GIF格式，输出为可以发送到打印机的格式。而这台打印机并不是放在你的桌面上的小型打印机，而是能输出超大型出版物的打印机，一个下午能印出一百万份杂志的那种。

打印机要求CMYK格式的图像。CMYK的意思是“Cyan-Magenta-Yello-Black”，即“青-洋红-黄-黑”，这是打印机用于印刷杂志时使用的墨水的四种颜色。 ^[6] 但是，GIF图像中的颜色是RGB值，是电脑显示器显示图片时发出的红光、绿光、蓝光的亮度。现在需要把用于显示器的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);   # 最小值
  for ($c, $m, $y) { $_ -= $k }
  [$c, $m, $y, $k];
}
		

剩下的程序就是打开GIF文件，每次读取一个像素，再对每个像素调用RGB_to_CMYK()，最后将CMYK值写成适当的格式。

这里有个小问题。假设GIF图像宽度为1024像素、高度为768像素，这样总共有786,432个像素。这样就得调用RGB_to_CMYK()786,432次。看起来似乎没问题，不过有一点：根据GIF格式的定义，GIF图像的不同颜色数不会超过256中。这就是说，在786,432次调用中，至少有786,176次是纯粹的浪费时间，因为每次都在重复以前执行过的计算。如果能找个方法将RGB_to_CMYK()的计算结果保存下来，并在需要的时候去除，也许能提高些性能。

Perl中一说起检查是否出现的问题，解决方法几乎总是散列表。这次也不例外。如果将RGB值作为键，就可以生成一个散列，保存之前遇到的RGB值，以及相应的CMYK值。这样，程序逻辑可以改成这样：要将一组RGB值转换成一组CMYK值，首先在散列中查找RGB值。如果没有，就进行计算，并将结果保存到散列中之后，再像通常一样返回CMYK。如果散列中有这个RGB值，就直接从散列中取得CMYK值并返回，就不必再次计算了。

代码如下所示：

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];
}
		

假设调用RGB_to_CMYK()时使用的参数是128,0,64。第一次调用时，函数首先查找%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 + (1 - h)f。没有缓存的函数的执行时间显然永远是f，因此两者的差异就是bf - K。如果K < bf，有缓存的版本就要比没有缓存的快。要提高缓存函数的速度，可以提高缓存命中率b，或者降低缓存管理的开销K。如果f很大，那么K < bf就很容易满足，所以缓存在原始函数运行时间非常长的时候更容易有效。最坏情况下，缓存一次也不命中，从而b = 0，此时“加速”效果实际上是降低了-K的速度。

# 计算给定的第n月中兔子的对数
sub fib {
  my ($month) = @_;
    if ($month < 2){1}
  else {
    fib($month-1) + fib($month-2);
  }
}