Memoize - 通过以时间换取空间来使函数运行得更快
use Memoize;
memoize('slow_function');
slow_function(arguments); # Is faster than it was before这通常是您需要了解的所有内容。但是，提供了很多选项
memoize(function, options...);选项包括
NORMALIZER => function
INSTALL => new_name
SCALAR_CACHE => 'MEMORY'
SCALAR_CACHE => ['HASH', \%cache_hash ]
SCALAR_CACHE => 'FAULT'
SCALAR_CACHE => 'MERGE'
LIST_CACHE => 'MEMORY'
LIST_CACHE => ['HASH', \%cache_hash ]
LIST_CACHE => 'FAULT'
LIST_CACHE => 'MERGE'备忘函数通过以时间换取空间来使函数运行得更快。它通过将函数的返回值缓存在表中来实现这一点。如果您再次使用相同的参数调用函数，memoize 会介入，并从表中为您提供值，而不是让函数重新计算值。
这是一个极端的例子。考虑由以下函数定义的斐波那契数列
# Compute Fibonacci numbers
sub fib {
my $n = shift;
return $n if $n < 2;
fib($n-1) + fib($n-2);
}此函数非常慢。为什么？要计算 fib(14)，它首先要计算 fib(13) 和 fib(12)，然后相加结果。但是要计算 fib(13)，它首先必须计算 fib(12) 和 fib(11)，然后返回并再次计算 fib(12)，即使答案相同也是如此。并且在它想要计算 fib(12) 的两次中，它都必须从头开始计算 fib(11)，然后在每次想要计算 fib(13) 时都必须再次执行此操作。此函数对旧结果进行了如此多的重新计算，以至于运行起来需要很长时间---fib(14) 对自身进行了 1,200 次额外的递归调用，以计算和重新计算它已经计算的内容。
此函数是备忘录化的良好候选。如果你对上面的 fib 函数进行备忘录化，它将准确地计算 fib(14) 一次，在它第一次需要时，然后将结果保存在一个表中。然后，如果你再次要求 fib(14)，它会从表中给你结果。在计算 fib(14) 时，它不会计算 fib(12) 两次，而是计算一次；第二次需要该值时，它从表中获取。它不会计算 fib(11) 四次；它计算一次，在接下来的三次从表中获取。它不会对 fib 进行 1,200 次递归调用，而是进行 15 次。这使函数快了大约 150 倍。
你可以通过像这样重写函数来自己进行备忘录化
# Compute Fibonacci numbers, memoized version
{ my @fib;
sub fib {
my $n = shift;
return $fib[$n] if defined $fib[$n];
return $fib[$n] = $n if $n < 2;
$fib[$n] = fib($n-1) + fib($n-2);
}
}或者你可以像这样使用此模块
use Memoize;
memoize('fib');
# Rest of the fib function just like the original version.这使得可以轻松地打开和关闭备忘录化。
这是一个更简单的示例：我编写了一个简单的光线追踪器；该程序将朝某个方向查看，找出它正在查看什么，然后将该对象的 color 值（通常是像 red 这样的字符串）转换为红色、绿色和蓝色像素值，如下所示
for ($direction = 0; $direction < 300; $direction++) {
# Figure out which object is in direction $direction
$color = $object->{color};
($r, $g, $b) = @{&ColorToRGB($color)};
...
}由于图片中的对象相对较少，因此只有少数颜色，并且会反复查找这些颜色。对 ColorToRGB 进行备忘录化将使程序加速几个百分点。
此模块仅导出一个函数，即 memoize。此包中的其余函数与你无关。
你应该说
memoize(function)其中 function 是你要备忘录化的函数的名称或对其的引用。memoize 返回对函数的新备忘录化版本或在出现非致命错误时的 undef 的引用。目前，没有非致命错误，但将来可能会有。
如果 function 是函数的名称，则 memoize 将隐藏旧版本并在旧名称下安装新的备忘录化版本，以便 &function(...) 实际调用备忘录化版本。
您可以将一些可选选项传递给 memoize 以稍微改变其行为方式。要提供选项，请像这样调用 memoize
memoize(function, NORMALIZER => function,
INSTALL => newname,
SCALAR_CACHE => option,
LIST_CACHE => option
);这些选项都是可选的；您可以包含其中一些、全部或不包含任何选项。
如果您使用 INSTALL 提供函数名称，memoize 将在您给定的名称下安装该函数的新备忘版本。例如，
memoize('fib', INSTALL => 'fastfib')将 fib 的备忘版本安装为 fastfib；如果没有 INSTALL 选项，它将使用备忘版本替换旧的 fib。
要阻止 memoize 在任何地方安装备忘版本，请使用 INSTALL => undef。
假设您的函数如下所示
# Typical call: f('aha!', A => 11, B => 12);
sub f {
my $a = shift;
my %hash = @_;
$hash{B} ||= 2; # B defaults to 2
$hash{C} ||= 7; # C defaults to 7
# Do something with $a, %hash
}现在，对函数的所有以下调用完全等效
f(OUCH);
f(OUCH, B => 2);
f(OUCH, C => 7);
f(OUCH, B => 2, C => 7);
f(OUCH, C => 7, B => 2);
(etc.)但是，除非您告诉 Memoize 这些调用是等效的，否则它不会知道这一点，并且它将分别计算这些函数调用的值，并分别存储它们。
要防止这种情况，请提供一个 NORMALIZER 函数，该函数将程序参数转换为字符串，使等效参数转换为相同的字符串。上面 f 的 NORMALIZER 函数可能如下所示
sub normalize_f {
my $a = shift;
my %hash = @_;
$hash{B} ||= 2;
$hash{C} ||= 7;
join(',', $a, map ($_ => $hash{$_}) sort keys %hash);
}上述每个参数列表都以完全相同的方式从 normalize_f 函数中输出，如下所示
OUCH,B,2,C,7您将告诉 Memoize 以这种方式使用此规范化器
memoize('f', NORMALIZER => 'normalize_f');memoize 知道，如果两个参数列表的参数的规范化版本相同，那么它可以安全地查找为一个参数列表计算的值，并将其作为使用另一个参数列表调用函数的结果返回，即使参数列表看起来不同。
默认规范化器只是将参数连接起来，中间带有字符 28。（在 ASCII 中，这称为 FS 或控制-\。）对于只有一个字符串参数的函数，这始终都能正确工作，并且当参数从不包含字符 28 时也能正确工作。但是，它可能会混淆某些参数列表
normalizer("a\034", "b")
normalizer("a", "\034b")
normalizer("a\034\034b")例如。
由于哈希键是字符串，因此默认规范化器不会区分 undef 和空字符串。当函数的参数是引用时，它也不会起作用。例如，考虑一个函数 g，它获取两个参数：一个数字和对数字数组的引用
g(13, [1,2,3,4,5,6,7]);默认的规范化器会将此变成类似于 "13\034ARRAY(0x436c1f)" 的内容。这本来是没问题的，但即使包含相同的数据，后续的数字数组也可能会存储在不同的位置。如果发生这种情况，Memoize 会认为这些参数不同，即使它们是等效的。在这种情况下，可以使用类似这样的规范化器
sub normalize { join ' ', $_[0], @{$_[1]} }对于上面的示例，这会生成键 "13 1 2 3 4 5 6 7"。
规范化器的另一个用途是当函数依赖于其参数之外的数据时。假设您有一个函数，它会返回一个取决于当前时间的值
sub on_duty {
my ($problem_type) = @_;
my $hour = (localtime)[2];
open my $fh, "$DIR/$problem_type" or die...;
my $line;
while ($hour-- > 0)
$line = <$fh>;
}
return $line;
}在 10:23，此函数会生成数据文件的第 10 行；在下午 3:45，它会生成第 15 行。默认情况下，Memoize 只会看到 $problem_type 参数。要修复此问题，请在规范化器中包含当前时间
sub normalize { join ' ', (localtime)[2], @_ }函数的调用上下文（标量或列表上下文）会传播到规范化器。这意味着，如果备忘函数在列表上下文中处理其参数的方式与在标量上下文中处理其参数的方式不同，您可以让规范化器函数根据 wantarray 的结果选择其行为。即使在列表上下文中调用，规范化器仍应返回一个字符串。
SCALAR_CACHE，LIST_CACHE通常，Memoize 会将函数的返回值缓存到一个普通的 Perl 哈希变量中。但是，您可能希望将这些值缓存到磁盘上，以便它们从程序的一次运行持续到下一次运行，或者您可能希望将一些其他有趣的语义与缓存值关联起来。
Memoize 的底层有一个小小的复杂性：实际上有 两个 缓存，一个用于标量值，一个用于列表值。当您的函数在标量上下文中调用时，其返回值会缓存到一个哈希中，当您的函数在列表上下文中调用时，其值会缓存到另一个哈希中。您可以使用这些选项独立控制两个上下文的缓存行为。
LIST_CACHE 或 SCALAR_CACHE 的参数必须是以下四个字符串之一
MEMORY
FAULT
MERGE
HASH否则，它必须是对数组的引用，数组的第一个元素是这四个字符串之一，例如 [HASH, arguments...]。
MEMORYMEMORY 表示函数的返回值将缓存在一个普通的 Perl 哈希变量中。哈希变量在程序退出后不会持久存在。这是默认值。
HASHHASH 允许你指定你提供的特定哈希将用作缓存。你可以事先绑定此哈希，以赋予它任何你想要的行为。
绑定的哈希可以具有任何语义。它通常绑定到磁盘数据库，以便将缓存值存储在数据库中，并在需要时再次从中检索，并且磁盘文件通常在你的程序退出后仍然存在。有关 tie 的更完整详细信息，请参阅 perltie。
一个典型的示例是
use DB_File;
tie my %cache => 'DB_File', $filename, O_RDWR|O_CREAT, 0666;
memoize 'function', SCALAR_CACHE => [HASH => \%cache];这会将缓存存储在名称位于 $filename 中的 DB_File 数据库中。缓存将在程序退出后仍然存在。下次程序运行时，它将发现缓存已从程序的上次运行中填充。或者，你可以通过构建在后台运行并填充缓存文件的批处理程序来强制填充缓存。然后，当你运行你的真实程序时，备忘函数将很快，因为它的所有结果都已预先计算。
使用 HASH 的另一个原因是提供你自己的哈希变量。然后，你可以检查或修改哈希的内容，以更精细地控制缓存管理。
TIE此选项不再受支持。它仍然记录在案，只是为了帮助调试使用它的旧程序。旧程序应转换为使用 HASH 选项。
memoize ... ['TIE', PACKAGE, ARGS...]仅仅是
require PACKAGE;
{ tie my %cache, PACKAGE, ARGS...;
memoize ... [HASH => \%cache];
}FAULTFAULT 表示你永远不希望在标量（或列表）上下文中调用函数，并且如果 Memoize 检测到这样的调用，它应该中止程序。错误消息之一是
`foo' function called in forbidden list context at line ...
`foo' function called in forbidden scalar context at line ...MERGEMERGE 通常表示备忘函数不区分列表和标量上下文，并且两个上下文中的返回值应一起存储。LIST_CACHE => MERGE 和 SCALAR_CACHE => MERGE 都表示相同的意思。
考虑此函数
sub complicated {
# ... time-consuming calculation of $result
return $result;
}complicated 函数将返回相同的数字 $result，无论是在列表还是标量上下文中调用它。
通常，以下代码将导致对 complicated 的两次调用，即使 complicated 已被记忆。
$x = complicated(142);
($y) = complicated(142);
$z = complicated(142);第一次调用将在标量缓存中缓存结果（例如 37）；第二次将在列表缓存中缓存列表 (37)。第三次调用不会调用真正的 complicated 函数；它从标量缓存中获取值 37。
显然，第二次对 complicated 的调用是浪费时间，而存储其返回值是浪费空间。指定 LIST_CACHE => MERGE 将使 memoize 对标量和列表上下文返回值使用相同的缓存，以便第二次调用使用第一次调用填充的标量缓存。complicated 最终只被调用一次，并且无论调用上下文如何，后续两次调用都从缓存中返回 37。
考虑此函数
sub iota { return reverse (1..$_[0]) }此函数通常返回一个列表。假设您对其进行记忆并合并缓存
memoize 'iota', SCALAR_CACHE => 'MERGE';
@i7 = iota(7);
$i7 = iota(7);这里，第一次调用缓存列表 (1,2,3,4,5,6,7)。第二次调用实际上没有意义。Memoize 无法猜测 iota 在标量上下文中应该具有什么行为，而无需在标量上下文中实际调用它。通常，Memoize 会 在标量上下文中调用 iota 并缓存结果，但 SCALAR_CACHE => 'MERGE' 选项表示不这样做，而是使用缓存列表上下文值。但它无法在标量上下文中返回一个包含七个元素的列表。在这种情况下，$i7 将接收缓存列表值的第一个元素，即 7。
MERGE 的另一个用途是当您希望将两种类型的返回值存储在同一个磁盘文件中时；这可以节省您处理两个磁盘文件而不是一个磁盘文件的工作。您可以使用归一化函数将两组返回值分开。例如
local $MLDBM::UseDB = 'DB_File';
tie my %cache => 'MLDBM', $filename, ...;
memoize 'myfunc',
NORMALIZER => 'n',
SCALAR_CACHE => [HASH => \%cache],
LIST_CACHE => 'MERGE',
;
sub n {
my $context = wantarray() ? 'L' : 'S';
# ... now compute the hash key from the arguments ...
$hashkey = "$context:$hashkey";
}此归一化函数将标量上下文返回值存储在磁盘文件中，其键以 S: 开头，并将列表上下文返回值存储在键以 L: 开头的磁盘文件中。
unmemoize有一个 unmemoize 函数，如果你愿意，可以导入它。为什么你会想要导入它？下面是一个示例：假设你的缓存绑定到一个 DBM 文件，并且你希望确保在有人中断程序时，缓存被写入磁盘。如果程序正常退出，这将无论如何发生，但如果有人键入 control-C 或类似内容，则程序将立即终止，而不同步数据库。因此，你可以执行以下操作
$SIG{INT} = sub { unmemoize 'function' };unmemoize 接受对之前记忆函数的引用或名称，并撤消它最初为提供记忆版本所做的任何操作，包括在适当的情况下使名称引用未记忆版本。它返回对函数的未记忆版本的引用。
如果你要求它取消从未记忆的函数的记忆，它会发出警告。
flush_cacheflush_cache(function) 将刷新缓存，丢弃所有缓存数据。参数可以是函数名称或对函数的引用。有关何时丢弃或过期数据的更精细控制，请参阅此软件包中包含的 Memoize::Expire 的文档。
请注意，如果缓存是绑定的哈希，flush_cache 将尝试对哈希调用 CLEAR 方法。如果没有 CLEAR 方法，这将导致运行时错误。
清除缓存的另一种方法是使用 HASH 选项（见上文）来请求 Memoize 使用特定的哈希变量作为其缓存。然后，你可以随时以任何你希望的方式检查或修改哈希。你可以使用 %hash = () 来刷新缓存。
记忆并非万能
不要记忆行为取决于其自身参数以外的程序状态的函数，例如全局变量、时间或文件输入。这些函数在记忆时不会产生正确的结果。对于一个特别简单的示例
sub f {
time;
}此函数不接受任何参数，并且就 Memoize 而言，它总是返回相同的结果。当然，Memoize 是错误的，此函数的记忆版本将调用 time 一次以获取当前时间，并且在之后每次调用它时都会返回相同的时间。
不要记忆有副作用的函数。
sub f {
my ($a, $b) = @_;
my $s = $a + $b;
print "$a + $b = $s.\n";
}此函数接受两个参数，将它们相加并打印它们的和。它的返回值是它打印的字符数，但你可能并不关心这一点。但 Memoize 不理解这一点。如果你记忆此函数，你将在第一次要求它打印 2 和 3 的和时获得预期的结果，但后续调用将返回 1（print 的返回值），而不会实际打印任何内容。
不要记忆一个返回数据结构的函数，该数据结构会被其调用者修改。
考虑以下函数：getusers 以某种方式返回用户列表，然后 main 丢弃列表中的第一个用户并打印其余用户
sub main {
my $userlist = getusers();
shift @$userlist;
foreach $u (@$userlist) {
print "User $u\n";
}
}
sub getusers {
my @users;
# Do something to get a list of users;
\@users; # Return reference to list.
}如果您在此处记忆 getusers，它将只运行一次。对用户列表的引用将存储在备忘表中。main 将从引用列表中丢弃第一个元素。下次调用 main 时，Memoize 不会调用 getusers；它只会返回上次获得的相同列表的相同引用。但这次列表的头部已被删除；main 将错误地从中删除另一个元素。每次调用 main 时，列表都会越来越短。
类似地，这
$u1 = getusers();
$u2 = getusers();
pop @$u1;将修改 $u2 和 $u1，因为这两个变量都是对同一数组的引用。如果 getusers 没有被记忆，$u1 和 $u2 将引用不同的数组。
不要记忆一个非常简单的函数。
最近有人告诉我，Memoize 模块使他的程序运行得更慢，而不是更快。事实证明，他正在记忆以下函数
sub square {
$_[0] * $_[0];
}我指出 Memoize 使用哈希，并且在哈希中查找数字势必比单次乘法花费更长的时间。实际上没有办法加速 square 函数。
记忆不是神奇的。
您可以将缓存表绑定到任何您想要的关联哈希，只要它支持 TIEHASH、FETCH、STORE 和 EXISTS。例如，
tie my %cache => 'GDBM_File', $filename, O_RDWR|O_CREAT, 0666;
memoize 'function', SCALAR_CACHE => [HASH => \%cache];工作正常。对于某些存储方法，您需要一点粘合剂。
SDBM_File 不提供 EXISTS 方法，因此此包中包含一个名为 Memoize::SDBM_File 的粘合剂模块，该模块确实提供了一个。使用它代替普通的 SDBM_File，将您的缓存表存储在 SDBM_File 数据库中的磁盘上
tie my %cache => 'Memoize::SDBM_File', $filename, O_RDWR|O_CREAT, 0666;
memoize 'function', SCALAR_CACHE => [HASH => \%cache];NDBM_File 有相同的问题和相同的解决方案。（使用 Memoize::NDBM_File 代替普通的 NDBM_File。）
Storable 根本不是关联哈希类。您可以使用它将哈希存储到磁盘并再次检索它，但您无法在哈希位于磁盘上时对其进行修改。因此，如果您想将缓存表存储在 Storable 数据库中，请使用 Memoize::Storable，它将类哈希的前端放在 Storable 上。哈希表实际上保存在内存中，并在您记忆函数时从 Storable 文件中加载，并在您取消记忆函数（或程序退出时）存储回
tie my %cache => 'Memoize::Storable', $filename;
memoize 'function', SCALAR_CACHE => [HASH => \%cache];
tie my %cache => 'Memoize::Storable', $filename, 'nstore';
memoize 'function', SCALAR_CACHE => [HASH => \%cache];包含 nstore 选项以使 Storable 数据库以网络顺序写入。（有关此内容的更多详细信息，请参阅 Storable。）
除非绑定的程序包提供 CLEAR 方法，否则 flush_cache() 函数将引发运行时错误。
请参阅 Memoize::Expire，这是一个插件模块，它为 Memoize 添加了到期功能。如果您不喜欢 Memoize::Expire 实施的策略类型，则可以轻松编写自己的插件模块来实施您想要的任何策略。Memoize 带有几个示例。在 CPAN 上提供了一个实现 LRU 策略的到期管理器，即 Memoize::ExpireLRU。
测试套件有了很大改善，但始终需要改进。
goto &f 在多线程 Perl 下的工作方式存在一些问题，这可能是由于 @_ 的词法作用域。这是 Perl 中的一个错误，在解决此错误之前，已记忆函数将看到略有不同的 caller()，并且在多线程 Perl 上执行的速度比在非多线程 Perl 上稍慢。
某些版本的 DB_File 不允许您存储长度为 0 的键下的数据。这意味着，如果您有一个已记忆的函数 f，并且缓存位于 DB_File 数据库中，则 f()（f 在没有参数的情况下调用）的值将不会被记忆。如果这是一个大问题，您可以提供一个将 "x" 前置到每个键的归一化函数。
在 https://perl.plover.com/MiniMemoize/ 上有一篇关于记忆和 Memoize 内部原理的文章，该文章发表在 The Perl Journal 第 13 期。
Mark-Jason Dominus 的书Higher-Order Perl（2005 年，ISBN 1558607013，由 Morgan Kaufmann 出版）非常详细地讨论了记忆（以及许多其他主题）。它可以在线免费获得。有关更多信息，请访问 https://hop.perl.plover.com/。
非常感谢 Florian Ragwitz 提供的管理和打包帮助，感谢 John Tromp 提供的错误报告，感谢 Jonathan Roy 提供的错误报告和建议，感谢 Michael Schwern 提供的其他错误报告和补丁，感谢 Mike Cariaso 帮助我弄清楚关于到期应采取的正确措施，感谢 Joshua Gerth、Joshua Chamas、Jonathan Roy（再次）、Mark D. Anderson 和 Andrew Johnson 提供的更多关于到期的建议，感谢 Brent Powers 提供的 Memoize::ExpireLRU 模块，感谢 Ariel Scolnicov 提供的关于 Fibonacci 函数的令人愉快的消息，感谢 Dion Almaer 提供的关于默认归一化的发人深省的建议，感谢 Walt Mankowski 和 Kurt Starsinic 在调查多线程 Perl 下的问题时提供的很多帮助，感谢 Alex Dudkevich 报告原型函数中的错误并检查我的补丁，感谢 Tony Bass 提供的许多有用的建议，感谢 Jonathan Roy（再次）找到 unmemoize() 的用途，感谢 Philippe Verdret 对 Hook::PrePostCall 的启发性讨论，感谢 Nat Torkington 提出我忽略的建议，感谢 Chris Nandor 提供的可移植性建议，感谢 Randal Schwartz 建议使用 flush_cache 函数，感谢 Jenda Krynicky 为世界带来光明。
特别感谢 Jarkko Hietaniemi，5.8.0 的核心开发者，他将此模块纳入核心，并在集成过程中提供了耐心而有帮助的指导。
Mark Jason Dominus
此软件的版权归 Mark Jason Dominus 所有 (c) 2012。
这是免费软件；您可以在与 Perl 5 编程语言系统本身相同的条款下重新分发或修改它。