3.10 可供选择的记忆术
大多数纯函数提供一个缓存的机会。尽管乍一看纯函数很少，它们只以一定频率出现。纯函数特别普遍的地方是在排序中用做比较器函数。
Perl内置的sort操作符是通用的，它可以把一列任何种类的数据以程序要求的任何次序排序。默认状态下，它把一列字符串以字母表次序排序，但是程序员可以任意提供一个比较器函数（comparator function），告诉Perl怎样重排sort的参数列表。比较器函数被反复调用，每次带有待排序列表中的两个不同元素，如果两个元素次序正确，就必须返回一个负值；如果两个元素次序不正确，就返回一个正值，如果无所谓，就返回零。通常，一个比较器函数的返回值只依赖它的参数的值，待比较的两个列表条目，所以它是一个纯函数。
最简单的比较器函数的例子也许是按大小比较数字的比较器了：
@sorted_numbers = sort { $a <=> $b } @numbers;
这里{ $a <=> $b } 就是比较器函数。sort操作符检查列表@numbers，把$a和$b设置成将要比较的数字，然后调用比较器函数。<=>是一个特殊的Perl操作符，如果$a小于$b，就返回一个负值；如果$a大于$b，就返回一个正值；如果$a与$b相等，就返回零。cmp是一个针对字符串的类似的操作符，如果不提供一个明确的比较器，Perl就默认使用它。
一个可选的语法是使用一个具名函数而不是一个裸露的块：
@sorted_numbers = sort numerically @numbers;
sub numerically { $a <=> $b }
这等价于裸露块版本。
一个更有趣的例子是把一列形如"Apr 16, 1945"的日期字符串按时间次序排序：
### Code Library: chrono-1
@sorted_dates = sort chronologically @dates;
%m2n =
( jan => 1, feb => 2, mar => 3,
apr => 4, may => 5, jun => 6,
jul => 7, aug => 8, sep => 9,
oct => 10, nov => 11, dec => 12, );
sub chronologically {
my ($am, $ad, $ay) =
($a =~ /(\w{3}) (\d+), (\d+)/);
my ($bm, $bd, $by) =
($b =~ /(\w{3}) (\d+), (\d+)/);
$ay <=> $by
|| $m2n{lc $am} <=> $m2n{lc $bm}
|| $ad <=> $bd;
}
要被比较的两个日期字符串，和先前一样，放在$a和$b里，然后拆分成$ay，$by，$am等。$ay与$by，是年份，最先比较。这里的||操作符是个一般的习惯用法，在排序的比较器中用第二个关键词排序。||操作符返回它的左操作数，除非那是零，那种情况它就返回右操作数。如果年份相同，那么$ay <=> $by返回零，||操作符把控制传递到进入月份的表达式部分，用来解开关联的部分。但是如果年份不同，那么第一个<=>的结果是非零，这就是||表达式的结果，指示sort如何把$a与$b排序到结果列表中，而不必再看月份和日子了。如果控制传递到了$am <=> $bm部分，会发生同样的事情。月份被比较；如果结果是结论性的，那么函数立即返回，如果月份相同，控制传递到最后的日子比较的决胜局。
从内部看，Perl的sort操作符已经被多种算法实现，运行时间是O(n log n)。这意味着对一个大n倍的列表排序一般会花费比n倍稍微长的时间。如果列表规模加倍，运行时间比双倍更多。下面的表比较了参数列表的长度和比较器函数通常的调用次数：
Length # calls calls / element
5 7 1.40
10 26 2.60
20 60 3.00
40 195 4.87
80 417 5.21
100 569 5.69
1000 9502 9.50
10000 139136 13.91
我如此得到“# call”列的，依照指示的长度产生一列随机数，然后用一个比较器函数排序，每次被调用，计数器就增加。调用的次数将因列表和比较器函数而不同，但这些值是典型的。
现在考察有10 000个日期的列表。139 136次比较器函数的调用，每次调用执行两次模式匹配操作，所以一共有278 272次模式匹配。这意味着每个日期平均拆分成年、月、日27.8次。由于给定日期的这三个组成部分不会改变，显然26.8次模式匹配是浪费的。
首先想到的是，使chronologically函数带记忆，但这实际上行不通。尽管sort将以相同的日期反复调用chronologically函数，但它不会对同一对（pair）日期调用两次（除非，当然，输入列表包含重复的日期）。由于散列键必须结合两个参数，带记忆的函数将永远不会有一次缓存命中。
而本文是采取稍微不同的做法，只使函数中浪费的部分带记忆。这将需要能处理一个返回列表的函数的memoize()版本。
### Code Library: chrono-2
@sorted_dates = sort chronologically @dates;
%m2n =
( jan => 1, feb => 2, mar => 3,
apr => 4, may => 5, jun => 6,
jul => 7, aug => 8, sep => 9,
oct => 10, nov => 11, dec => 12, );
sub chronologically {
my ($am, $ad, $ay) = split_date($a);
my ($bm, $bd, $by) = split_date($b);
$ay <=> $by
|| $m2n{lc $am} <=> $m2n{lc $bm}
|| $ad <=> $bd;
}
sub split_date {
$_[0] =~ /(\w{3}) (\d+), (\d+)/;
}
如果对split_date设置缓存，仍将进行278 272次调用，但是268 272次将导致缓存命中，只有剩下的10 000次需要模式匹配。唯一的挑战是将不得不手动写缓存代码，因为split_date返回一个列表，而memoize函数只能正确处理返回标量的函数。
此刻，可以向三个方向行进。可以增强memoize函数能正确处理列表上下文返回。（或者可以使用CPAN Memoize模块，它能对返回列表的函数正确工作。）可以手写缓存代码。但更有益的是绕过这个问题，通过用一个返回标量的函数替代split_date。如果标量构造正确，将能免除chronologically中复杂的||逻辑，而仅使用一个简单的字符串比较。
这里有一个策略：拆分日期，和先前一样，但是不再返回一列字段，而是把一列字段放入一个单一的字符串。字段将按照要检查的次序出现在字符串中，年份最先，然后是月份，然后是日期。对"Apr 16, 1945"的字符串将是"19450416"。当用cmp比较字符串时，Perl将尽快停止比较，因此如果一个字符串以"1998..."开头，而另一个以"1996..."开头，Perl一看到第四个字符就知道了结果，不再操心检查月份和日期。字符串的比较是非常快的，多半可以战胜一系列<=>和||。
修改后的代码如下：
### Code Library: chrono-3
@sorted_dates = sort chronologically @dates;
%m2n =
( jan => 1, feb => 2, mar => 3,
apr => 4, may => 5, jun => 6,
jul => 7, aug => 8, sep => 9,
oct => 10, nov => 11, dec => 12, );
sub chronologically {
date_to_string($a) cmp date_to_string($b)
}
sub date_to_string {
my ($m, $d, $y) = ($_[0] =~ /(\w{3}) (\d+), (\d+)/);
sprintf "%04d%02d%02d", $y, $m2n{lc $m}, $d;
}
现在可以使date_to_string带记忆。这能否战胜先前的版本，依赖sprintf加cmp是否比<=>加||更快。一般需要一个基准比较测试，它证明带sprintf的代码要快大约两倍。
排序经常是在程序里需要尽可能压榨出最多性能的地方之一。对一个10 000个日期的列表，可以精确地调用sprintf 10 000次（一旦date_to_string已经带记忆），但是仍然要调用date_to_string 278 272次。随着日期列表变长，这种不对称也将增长，函数调用的时间最终将超过排序的运行时间。
可以通过简化缓存处理和削减268 272次额外的函数调用获得更多的速度优势。为此，回到手写的缓存代码：
### Code Library: chrono-orc
{ my %cache;
sub chronologically {
($cache{$a} ||= date_to_string($a))
cmp
($cache{$b} ||= date_to_string($b))
}
}
这里使用||=操作符，看上去几乎是为缓存应用定制的。$x ||= $y产生$x的值，如果$x是真的；如果不是，它把$y赋值给$x并产生$y的值。$cache{$a ||= date_to_string($a)}查看$cache{$a}是否有一个真值，如果有，那就是用cmp操作符比较时使用过的值。如果还没有任何东西缓存，那么$cache{$a}是假，然后chronologically就调用date_to_string，把结果存在缓存里，并在比较时使用这个结果。这种内联的缓存技术就称为Orcish Maneuver，因为它的本质特性是||和缓存。
使date_to_string带记忆，产生2.5倍的加速；用Orcish Maneuver代替记忆术产生额外的两倍加速。
机敏的读者将会注意到Orcish Maneuver不总是完全正确。在这个例子里，date_to_string不可能总是返回一个假值。但是短暂返回计算每个投资者的投资总数的例子：
{ my %cache;
sub by_total_invested {
($cache{$a} ||= total_invested($a))
<=>
($cache{$b} ||= total_invested($b))
}
}
假设Luke Hermit根本没投资过。他第一次出现在by_total_invested时，为Luke调用total_invested，然后得到0。把这个0以Luke为键存放在缓存里。Luke下次出现时，检查缓存并发现存放在那里的值是0。因为这个值是假，所以再次调用total_invested，即使已经命中缓存了。这里的问题是||=操作符无法区分缓存脱靶与缓存命中的值恰好是假。
Lisp玩家给这种现象取了个名字：称为半谓词问题（semipredicate problem）。一个谓词（predicate）就是一个返回布尔值的函数。一个半谓词（semipredicate）能返回一个特定的假值，表示失败，或者许多有意义的真值之一，表示成功。$cache{$a}是一个半谓词，因为它可能返回0，或者无数有用的真值之一。当0也是真值之一时，就遇到麻烦了，因为无法把它与0意味着假区分开。这就是半谓词问题。
在先前的例子里，半谓词问题不会引起太多的麻烦。仅有的代价就是对那些没有投资过的人们会多些额外的total_invested调用。如果发现这些额外的调用在明显地拖慢排序（不经常，但有可能），就可以用下面的版本替换比较器函数：
{ my %cache;
sub by_total_invested {
(exists $cache{$a} ? $cache{$a} : ($cache{$a} = total_invested($a)))
<=>
(exists $cache{$b} ? $cache{$b} : ($cache{$b} = total_invested($b)))
}
}
这个版本使用了可靠的exists操作符检查缓存是否被占据。即使存储在缓存的值是假，exists仍将返回真。请注意，不过，这样比简单版本慢10%左右。
还有个方法几乎没有额外的代价，但具有奇异的缺点。它基于这样的秘籍：当Perl里的字符串"0e0"用做一个数字时，它就完全和0一样；e0被Perl解释成科学计数法的指数。但是和普通的0不同，字符串"0e0"是真而不是假。
如果这样写by_total_invested，就几乎没付出额外的代价而避免了半谓词问题：
{ my %cache;
sub by_total_invested {
($cache{$a} ||= total_invested($a) || "0e0")
<=>
($cache{$b} ||= total_invested($b) || "0e0")
}
}
如果total_invested返回零，函数就缓存"0e0"。下次寻找同一个客户投资的总数时，函数在缓存里看到"0e0"，而这个值是真，所以它不会第二次调用total_invested。这个"0e0"就是给<=>操作符比较的值，但是在数字比较中它表现得和0完全一样，这也正是我们期望的。额外的||操作的速度损失，仅存在于total_invested()返回一个假值的时候，是非常小的。