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

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

Memoization是一种优化技术,用于提高函数的性能。在我们开始学习记忆化技术之前,让我们通过下面的例子来理解为什么我们需要记忆化技术。

例子(寻找斐波那契数的Native方法)

在下面的例子中,我们已经实现了寻找第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的情况下可以正常工作,但是当我们输入范围为104 的输入值时,需要比平时更多的时间,而对于范围为106 的输入值,由于内存超限,浏览器崩溃了。

我们可以使用记忆化技术来优化上述代码,它允许我们存储之前的计算结果。例如,为了找到第 4个斐波那契数,我们需要找到第3和第2个斐波那契数。同样,为了找到第3个斐波那契数,我们必须找到第2个和第1个斐波那契数。所以,在这里我们已经计算了两次第 2个斐波那契数。

现在,想一想,你想找到大的第n个数值的斐波那契数,你可以想一想这需要多少次的重复。因此,为了优化,我们可以第一次计算第 2个斐波那契数,并将其存储在临时变量中。之后,当我们需要再次计算第 2个斐波那契数时,我们可以从数组中访问它,使代码更有效率。

另外,将之前计算的结果存储在数组中供以后使用,这就是备忘化。

语法

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

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

在上面的语法中,我们首先检查第n个斐波那契数是否已经存在于’Äòtemp’Äô对象中,然后我们返回这个值;否则,我们计算它的值并将其存放到temp对象中。

操作方法

第1步 – 使用if语句检查n的结果是否存在于temp对象中。如果存在,则返回之前计算的值。

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

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

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

例子 (使用记忆法找到第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>

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

JavaScript 教程