JavaScript - Memoization(记忆化)

随着系统规模不断扩大，计算也越来越复杂，对速度的需求也随之增长，流程优化也变得势在必行。忽略这个问题会导致应用程序占用大量系统资源，运行缓慢。

本章将讨论记忆化技术，如果使用得当，它可以显著缩短处理时间。

什么是记忆化?

记忆化是一种通过存储高开销函数调用结果并在再次使用相同输入时提供结果来加速应用程序的技术。

让我们尝试将这个术语分解成更小的部分来理解它 -

• 高开销函数调用:在计算机应用程序中，内存和时间是两种主要资源。因此，由于执行大量计算而大量使用这两种资源的函数调用被认为是昂贵的。

• 缓存:缓存只是一个短期数据存储系统，它保存信息以便更快地处理未来对该信息的请求。

记忆化的好处

在接收输入后，函数会进行必要的计算，缓存结果，然后返回值。如果将来再次收到相同的输入，则无需重复该过程。它只会返回保存在内存中的响应。因此，代码的执行时间将大大减少。

何时使用记忆化?

以下是一些应该使用记忆化的要点:

• 当函数调用自身时。例如，考虑递归函数。

• 当函数是纯函数(每次调用都返回相同的值)时。如果该值随着每次函数调用而变化，则没有必要保存它。因此，当函数不纯时，我们不能在 JavaScript 中使用记忆化。

• 当函数具有很高的时间复杂度时。在这种情况下，将结果保存在缓存中可以通过避免函数的重复计算来降低时间复杂度，从而提高效率。

JavaScript 中的记忆化

JavaScript 记忆化是一种优化技术，用于最大限度地减少应用程序的运行时间、复杂度以及时间和内存的合理使用。该过程涉及通过使用额外的空间(缓存)来减少昂贵的函数调用次数(递归调用自身并存在一些重叠问题的函数)。

我们使用记忆化存储在先前子问题中计算的值。如果出现相同的子问题，则再次使用保存的值，从而通过减少重复执行相同计算的需要来降低时间复杂度。

记忆化如何工作?

JavaScript 记忆化纯粹基于以下两个概念 -

• 闭包

• 高阶函数

闭包

闭包由一个函数组成，该函数被指向状态的引用所包围。闭包允许从内部函数访问外部函数的作用域。在 JavaScript 中，闭包是在创建函数时形成的。

let greeting = "Welcome";
function welcomeMessage() { 
   let user = "Rahul"; 
   console.log(`${greeting} to the program, ${user}!`); 
}
welcomeMessage();

输出

这将生成以下结果 -

Welcome to the program, Rahul!

在上述 JavaScript 代码中 -

• 变量 greet 是一个全局变量。它可以从任何地方访问，包括welcomeMessage() 函数。

• 变量 user 是一个局部变量，只能在welcomeMessage() 函数中使用。

词法作用域允许嵌套作用域，内部函数可以访问外部作用域中指定的变量。因此，在下面的代码中，内部函数welcome() 可以访问变量 user。

function welcomeMessage() { 
   let user = "Rahul";
   function welcome() {
      console.log(`Greetings, ${user}!`);
   }
   welcome(); 
}
welcomeMessage();

输出

这将处理以下输出 -

Greetings Rahul!

现在我们将修改welcomeMessage()函数，而不是调用函数welcome()，而是返回welcome()函数对象。

function welcomeMessage() {
   let user = 'Rahul';   
   function welcome() {
      console.log(`Greetings ${user}!`);
   }
   return welcome;
}
let greet = welcomeMessage();
greet();

输出

运行这段代码，我们将获得与之前相同的结果。但需要注意的是，局部变量通常仅在函数执行期间存在。

这意味着在执行welcomeMessage()之后，user变量将不再可用。在这种情况下，当我们调用gree()时，对welcome()的引用仍然存在，user变量也是如此。闭包是一个将外部作用域保持在内部作用域中的函数。

Greetings Rahul!

高阶函数

高阶函数通过将其他函数作为参数传递或返回来作用于其他函数。在上面的代码中，welcomeMessage()就是一个高阶函数的示例。

现在，我们将使用著名的斐波那契数列，来了解记忆化是如何运用这些概念的。

斐波那契数列:斐波那契数列是一组以 1 开头和结尾的数字，其规则是每个数字(称为斐波那契数)等于它前面两个数字的和。

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

因此，这个问题的一个简单递归函数如下 -

function fibonacciSeq(n) {
   if (n < 2)
      return 1;
   return fibonacciSeq(n - 1) + fibonacciSeq(n - 2);
}

如果我们绘制上述函数在 n=4 时的递归树，它将如下所示。如您所见，其中有太多不必要的计算。让我们尝试通过 memoization 来解决这个问题。

function memoizedFibSeq(num, memo) {
    // 如果未提供 memo 数组，则初始化 memo 数组
    memo = memo || [1, 1];
    
    // 如果 num 小于或等于 1，则直接返回结果
    if (num <= 1) return memo[num];
    
    // 如果 result 已经计算出来，则从 memo 中返回
    if (memo[num])
    return memo[num];
    
    // 计算并将结果存储在 memo 中
   	memo[num] = memoizedFibSeq(num - 1, memo) + memoizedFibSeq(num - 2, memo);
   	return memo[num];
}

// 计算第 10 个斐波那契数
console.log(memoizedFibSeq(10));  

输出

以上代码的结果如下:-

89

我们修改了上述代码示例中的函数，使其接受一个名为 memo 的可选输入。我们使用缓存对象作为临时内存，将斐波那契数列及其对应的索引作为键存储，以便在后续执行过程中检索这些键。