首页 >web前端 >js教程 >如何用 JavaScript 编写简单的 Memoization 函数代码？

如何用 JavaScript 编写简单的 Memoization 函数代码？

PHPz转载: 2023-08-25 08:17:02873浏览

记忆化是提高函数性能的优化技术。在我们开始记忆技术之前，让我们使用下面的示例来了解为什么我们需要它。

示例（查找斐波那契数的简单方法）

在下面的示例中，我们实现了简单的方法来查找第 n 个斐波那契数。我们使用递归方法来找到第 n 个斐波那契数列。

<html>
<body>
   <h3>Finding the nth Fibonacci using recursive approach number in JavaScript</h3>
   <p>Enter the number to find the nth Fibonacci number.</p>
   <input type = "number" id = "fib"> <br>
   <div id = "content"> </div> <br>
   <button onclick = "executeFunc()"> Submit </button>
   <script>
      let content = document.getElementById('content');
      
      // function to write the fibonacci series
      function findFib(n) {
         if (n <= 1) return n;
         return findFib(n - 1) + findFib(n - 2);
      }
      function executeFunc() {
         let n = document.getElementById('fib').value;
         content.innerHTML = "The " + n + "th fibonacci number is " + findFib(n);
      } 
   </script>
</body>
</html>

上面的例子对于小于 1000 的小输入值来说效果很好，但是当我们输入范围 10⁴ 的输入值时，它需要比平常更多的时间，并且对于范围 10 的输入⁶，由于内存越界导致浏览器崩溃。

我们可以使用记忆技术来优化上面的代码，它允许我们存储之前计算的结果。例如，要找到第 4 个斐波那契数，我们需要找到第 3 个和第 2 个斐波那契数。同样，要找到第三个斐波那契数，我们必须找到第二个和第一个斐波那契数。因此，这里我们计算了第二个斐波那契数两次。

现在，假设您想要找到第 n 个大值的斐波那契数列，您可以想想它需要多少次重复。因此，出于优化目的，我们可以第一次计算第二个斐波那契数并将其存储在临时变量中。之后，当我们需要再次计算第二个斐波那契数时，我们可以从数组中访问它，从而使代码更加高效。

此外，将先前计算的结果存储在数组中以供以后使用也是记忆化。

语法

用户可以按照下面的语法来实现记忆第n个斐波那契数。

if (temp[n]) return temp[n];
if (n <= 1) return n;
return temp[n] = findFib(n - 1, temp) + findFib(n - 2, temp);

在上面的语法中，我们首先检查‘temp’对象中是否已经存在第n个斐波那契数，然后返回该值；否则，我们计算它的值并将矿石添加到临时对象中。

方法

步骤 1 – 使用 if 语句检查临时对象中是否存在 n 的结果。如果是，则返回之前计算的值。

步骤 2 – 如果 n 小于或等于 1，则返回 1 作为递归函数的基本情况。

第 3 步 – 计算 n-1 和 n-2 斐波那契数，将它们相加并将它们存储在临时对象中以供以后使用。

第 4 步 – 将第 n 个斐波那契数存储后返回到临时对象。

示例（使用记忆查找第 n 个斐波那契数）

使用记忆技术，我们优化了下面示例中第一个示例的代码。我们使用 temp 对象来存储之前计算的结果。在输出中，用户可以观察到下面的代码比第一个示例的代码更高效。

<html>
<body>
   <h3>Finding the nth Fibonacci number using memoization using extra space in JavaScript</h3>
   <p>Enter the number to find the nth Fibonacci number.</p>
   <input type = "number" id = "fib"> <br>
   <div id = "content"> </div> <br>
   <button onclick = "start()"> Submit </button>
   <script>
      let content = document.getElementById('content');
      function findFib(n, temp) {
         if (temp[n]) return temp[n];
         if (n <= 1) return n;
         return temp[n] = findFib(n - 1, temp) + findFib(n - 2, temp);
      } 
      function start() {
         let n = document.getElementById('fib').value;
         content.innerHTML = "The " + n + "th fibonacci number using memoization is " + findFib(n, {}) + "<br>";
      }
   </script>
</body>
</html>

方法：使用记忆而不使用额外空间

第 1 步 – 将 a 初始化为 0，将 b 初始化为 1。

第 2 步 – 使用 for 循环进行 n 次迭代来查找第 n 个斐波那契数。

第 3 步 – 这里，c 是一个临时变量，存储第 (i-1) 个斐波那契数。

第 4 步 – 将 b 变量的值存储在 a 中。

第 5 步 – 将变量 c 的值存储在变量 b 中。

示例

下面的示例也是第一个示例的优化变体。在第二个示例中，我们使用 temp 对象来存储先前计算的结果，但在下面的代码中，我们使用名为 c 的单个临时变量。

下面的代码是查找斐波那契数列的最有效方法，因为其时间复杂度为 O(n)，空间复杂度为 O(1)。

<html>
<body>
   <h3>Finding the nth Fibonacci number using memoization in JavaScript</h3>
   <p>Enter the number to find the nth Fibonacci number:</p>
   <input type = "number" id = "fib"> <br>
   <div id = "content"> </div> <br>
   <button onclick = "findFib()"> Submit </button>
   <script>
      let content = document.getElementById('content');
      
      // function to write the fibonacci series
      function findFib() {
         let n = document.getElementById('fib').value;
         let a = 0, b = 1, c;
         if (n == 0) {
            return a;
         }
         for (let i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
         }
         content.innerHTML += "The " + n + "th Fibonacci number using memoization is " + b;
      }
   </script>
</body>
</html>

在本教程中，我们学习了优化代码的记忆技术，使其更加节省时间和空间。用户可以在第二个和第三个示例中使用不同的算法看到我们如何优化第一个示例的代码。

以上是如何用 JavaScript 编写简单的 Memoization 函数代码？的详细内容。更多信息请关注PHP中文网其他相关文章！

声明：

本文转载于：tutorialspoint.com。如有侵权，请联系admin@php.cn删除

上一篇：Node.js 中的 decipher.update() 方法下一篇：如何使用 FabricJS 计算文本中给定位置的字符高度？

查看更多