记忆化(Memoization)

Memoization 是一种优化技术，我们可以存储之前昂贵操作的结果，并在不重复操作的情况下使用它们。它能帮助我们大大加快解决问题的速度。当我们遇到可能有重复子问题的问题时，我们可以很容易地应用这种技术来存储这些结果，并在以后使用它们，而无需重复步骤。由于 PHP 支持关联数组和动态数组属性，我们可以毫无问题地缓存结果。我们必须记住的一点是，虽然缓存结果可以节省时间，但在缓存中存储这些结果需要更多内存。因此，我们必须在空间和内存之间做出权衡。

现在，让我们重温第 5 章 "应用递归算法—​递归"，看看生成斐波那契数字的递归示例。我们只需用一个计数器修改该函数，就能知道函数被调用的次数和函数的运行时间，从而得到第 30 个斐波那契数。下面是相关代码：

命令行输出如下。请注意，时间和结果可能因系统或 PHP 版本而异。这完全取决于程序运行的位置：

第一个数字 1346269 是第 30 个斐波那契数字，下一行显示在生成第 30 个数字的过程中，斐波那契函数被调用了 2692537 次。整个过程耗时 0.5 秒（我们使用的是 PHP 的 microtime 函数）。如果我们生成的是第 50 个斐波那契数字，函数调用次数将超过 400 亿次。这是一个很大的数字。但是，我们从斐波那契公式中知道，当我们计算 n 时，我们是通过 n-1 和 n-2 来计算的；这些已经在前面的步骤中计算过了。因此，我们在重复这些步骤，既浪费时间又降低了效率。现在，让我们将斐波那契结果存储在一个索引数组中，然后检查我们要找的斐波那契数字是否已经计算过。如果已经计算，我们就使用它；否则，我们将计算并存储结果。

下面是经过修改的代码，使用相同的递归过程生成斐波那契数字，但需要借助记忆：

从前面的代码中可以看出，我们引入了一个名为 $fibCache 的新全局变量，用于存储计算出的斐波那契数字。我们还会检查我们要找的数字是否已经在数组中。如果数字已经存储在缓存数组中，我们就不会计算斐波那契。如果现在运行这段代码，我们将看到以下输出：

现在，让我们来看看结果。第 30 个斐波那契数字与上次的相同。不过，看看函数调用次数。只有 31 次，而不是 270 万次。现在，让我们看看时间。我们只用了 0.00005299 秒，比未备忘录化的版本快了 1 万倍。

通过这个简单的例子，我们可以看到，在适用的情况下，我们可以利用备忘录化来优化我们的解决方案。我们必须记住的一点是，如果我们有重复的子问题，或者我们必须考虑之前的计算来计算当前或未来的计算，那么记忆化的效果会更好。虽然 memoization 会占用额外空间来存储部分计算数据，但利用 memoization 可以大大提高性能。