核心要点
程序经常浪费时间调用反复重新计算相同结果的函数。对于递归函数和数学函数尤其如此。斐波那契数生成器就是一个完美的例子。斐波那契数列是一系列整数，从零和一开始，其中每个值都是数列中前两个数字的和。根据此定义，前十个斐波那契数是：0、1、1、2、3、5、8、13、21、34。从编程的角度来看，第 nth 个斐波那契数通常使用以下函数递归计算。
function fibonacci(n) {
if (n === 0 || n === 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}此函数对于较小的“n”值运行良好。但是，随着“n”的增加，性能会迅速下降。这是因为两次递归调用重复了相同的工作。例如，要计算第 50 个斐波那契数，必须调用递归函数超过 400 亿次（确切地说为 40,730,022,147 次）！更糟糕的是，计算第 51 个数字需要将这项工作几乎完全重复两次。如果函数记住它之前计算的内容，则可以减轻重复工作的问题。
记忆化基础
记忆化是一种编程技术，它试图通过缓存函数先前计算的结果来提高函数的性能。因为 JavaScript 对象的行为类似于关联数组，所以它们是充当缓存的理想选择。每次调用记忆化函数时，其参数都用于索引缓存。如果数据存在，则可以返回它，而无需执行整个函数。但是，如果数据未被缓存，则执行函数，并将结果添加到缓存中。
在下面的示例中，原始斐波那契函数被重写为包含记忆化。在此示例中，自执行匿名函数返回一个内部函数 f()，该函数用作斐波那契函数。当返回 f() 时，它的闭包允许它继续访问“memo”对象，该对象存储其所有先前结果。每次执行 f() 时，它首先检查是否存在当前“n”值的结果。如果存在，则返回缓存值。否则，执行原始斐波那契代码。请注意，“memo”是在 f() 之外定义的，以便它可以在多次函数调用中保留其值。回想一下，原始递归函数被调用了超过 400 亿次才能计算出第 50 个斐波那契数。通过实现记忆化，此数字下降到 99。
function fibonacci(n) {
if (n === 0 || n === 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}处理多个参数
在前面的示例中，函数接受单个参数。这使得实现缓存相当简单。不幸的是，大多数函数需要多个参数，这会使缓存的索引变得复杂。要记忆化具有多个参数的函数，缓存必须变成多维的，或者必须组合所有参数以形成单个索引。
在多维方法中，缓存成为对象的层次结构，而不是单个对象。然后，每个维度都由单个参数索引。以下示例为斐波那契函数实现了一个多维缓存。在此示例中，该函数接受一个附加参数“x”，它什么也不做。每次调用函数时，代码都会检查“x”维度是否存在，如果不存在则对其进行初始化。从那时起，“x”维度用于缓存“n”值。结果是函数调用 fibonacci(“foo”, 3) 和 fibonacci(“bar”, 3) 不被视为相同的结果。
var fibonacci = (function() {
var memo = {};
function f(n) {
var value;
if (n in memo) {
value = memo[n];
} else {
if (n === 0 || n === 1)
value = n;
else
value = f(n - 1) + f(n - 2);
memo[n] = value;
}
return value;
}
return f;
})();多维缓存的替代方法是单个缓存对象，该对象由函数所有参数的组合索引。在这种方法下，参数被转换为数组，然后用于索引缓存。每个函数都有一个名为“arguments”的内置对象，其中包含传入的参数。“arguments”是一种称为类数组对象的类型的对象。它类似于数组，但不能用于索引缓存。因此，它必须首先转换为实际数组。这可以使用数组 slice() 方法完成。然后可以使用数组表示来索引缓存，如前所示。以下示例显示了如何实现此目的。请注意，附加变量“slice”被定义为对数组 slice() 方法的引用。通过存储此引用，可以避免反复计算 Array.prototype.slice() 的开销。然后使用 call() 方法将 slice() 应用于“arguments”。
var fibonacci = (function() {
var memo = {};
function f(x, n) {
var value;
memo[x] = memo[x] || {};
if (x in memo && n in memo[x]) {
value = memo[x][n];
} else {
if (n === 0 || n === 1)
value = n;
else
value = f(x, n - 1) + f(x, n - 2);
memo[x][n] = value;
}
return value;
}
return f;
})();缓存对象参数
此处介绍的记忆化方案不能很好地处理对象参数。当对象用作索引时，它们首先被转换为字符串表示形式，例如“[object Object]”。这会导致多个对象错误地映射到同一个缓存位置。可以通过在索引之前对对象参数进行字符串化来纠正此行为。不幸的是，这也会减慢记忆化过程。以下示例创建一个通用记忆化函数，该函数将对象作为参数。请注意，对象参数使用 JSON.stringify() 进行字符串化，以便创建缓存的索引。
function fibonacci(n) {
if (n === 0 || n === 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}自动记忆化
在所有前面的示例中，函数都被显式修改以添加记忆化。也可以在根本不修改函数的情况下实现记忆化基础结构。这很有用，因为它允许函数逻辑与记忆化逻辑分开实现。这是通过创建一个实用程序函数来完成的，该函数将函数作为输入并对其应用记忆化。以下 memoize() 函数将函数“func”作为输入。memoize() 返回一个新函数，该函数在“func”周围包装缓存机制。请注意，此函数不处理对象参数。为了处理对象，需要一个循环，该循环将分别检查每个参数并根据需要进行字符串化。
var fibonacci = (function() {
var memo = {};
function f(n) {
var value;
if (n in memo) {
value = memo[n];
} else {
if (n === 0 || n === 1)
value = n;
else
value = f(n - 1) + f(n - 2);
memo[n] = value;
}
return value;
}
return f;
})();局限性
在实现记忆化时，必须记住以下几点。首先，通过存储旧结果，记忆化函数会消耗额外的内存。在斐波那契示例中，额外的内存消耗是无限的。如果内存使用量是一个问题，则应使用固定大小的缓存。与记忆化相关的开销也可能使它不适用于执行速度很快或执行频率低的函数。
记忆化最大的限制是它只能自动应用于引用透明函数。如果函数的输出仅取决于其输入，并且不会产生任何副作用，则该函数被认为是引用透明的。对引用透明函数的调用可以用其返回值替换，而不会改变程序的语义。斐波那契函数是引用透明的，因为它完全取决于“n”的值。在下面的示例中，函数 foo() 不是引用透明的，因为它使用全局变量“bar”。由于“bar”可以在 foo() 之外修改，因此无法保证返回值对于每个输入值都保持不变。在此示例中，对 foo() 的两次调用返回的值为 2 和 3，即使传递给两次调用的参数相同也是如此。
var fibonacci = (function() {
var memo = {};
function f(x, n) {
var value;
memo[x] = memo[x] || {};
if (x in memo && n in memo[x]) {
value = memo[x][n];
} else {
if (n === 0 || n === 1)
value = n;
else
value = f(x, n - 1) + f(x, n - 2);
memo[x][n] = value;
}
return value;
}
return f;
})();需要记住的事项
关于在 JavaScript 中实现记忆化的常见问题解答 (FAQ)
记忆化是一种在 JavaScript 和其他语言中用于优化计算机程序的编程技术。此技术涉及存储昂贵的函数调用的结果，并在再次出现相同的输入时重用它们。这可以通过避免不必要的计算来大大提高程序的性能。在处理递归函数或使用相同参数重复调用的函数的情况下，它特别有用。
在 JavaScript 中，记忆化通过创建缓存来存储函数调用的结果来工作。当调用函数时，该函数首先检查给定输入的结果是否已在缓存中。如果是，则函数返回缓存的结果，而不是再次执行计算。如果结果不在缓存中，则函数执行计算，将结果存储在缓存中，然后返回结果。
当然，让我们考虑一个计算数字阶乘的简单函数示例。如果没有记忆化，该函数看起来像这样：
function fibonacci(n) {
if (n === 0 || n === 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}使用记忆化，我们可以通过存储先前函数调用的结果来优化此函数：
var fibonacci = (function() {
var memo = {};
function f(n) {
var value;
if (n in memo) {
value = memo[n];
} else {
if (n === 0 || n === 1)
value = n;
else
value = f(n - 1) + f(n - 2);
memo[n] = value;
}
return value;
}
return f;
})();虽然记忆化可以显着提高 JavaScript 程序的性能，但它并非没有局限性。记忆化的一个主要缺点是它可能会消耗大量内存，尤其是在将大量数据存储在缓存中时。如果管理不当，这可能会导致性能问题。此外，仅当多次使用相同参数调用函数时，记忆化才有效。如果函数输入始终不同，则记忆化不会提供任何性能优势。
记忆化在与纯函数一起使用时最有效。纯函数是一个始终返回相同输入的相同结果并且不会产生任何副作用的函数。如果函数依赖于外部状态或产生副作用，则对其进行记忆化可能会导致意外结果。因此，虽然从技术上讲你可以在 JavaScript 中对任何类型的函数使用记忆化，但它最适合纯函数。
为具有多个参数的函数实现记忆化可能有点复杂，但这绝对是可能的。一种方法是将参数转换为可以用作缓存中键的字符串。这是一个例子：
function fibonacci(n) {
if (n === 0 || n === 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}是的，有一些库和工具可以帮助在 JavaScript 中进行记忆化。例如，流行的 JavaScript 实用程序库 Lodash 提供了一个 _.memoize 函数，可以轻松记忆化函数。同样，Ramda 库提供了一个 R.memoizeWith 函数，允许你指定自定义缓存键函数。
可以通过简单地重置缓存对象来清除记忆化函数中的缓存。这是一个例子：
var fibonacci = (function() {
var memo = {};
function f(n) {
var value;
if (n in memo) {
value = memo[n];
} else {
if (n === 0 || n === 1)
value = n;
else
value = f(n - 1) + f(n - 2);
memo[n] = value;
}
return value;
}
return f;
})();是的，记忆化在 React 等 JavaScript 框架中非常有用。例如，React 提供了一个 React.memo 函数，可用于记忆化组件。这可以通过防止不必要地重新渲染组件来帮助提高性能。
记忆化是一种强大的优化技术，但它并不总是最佳解决方案。在某些情况下，其他优化技术（例如去抖动和节流）可能更合适。关键是要了解程序的特定需求和约束，并选择合适的优化技术。
以上是在JavaScript中实施备忘录的详细内容。更多信息请关注PHP中文网其他相关文章！
