Bagaimana untuk menulis kod fungsi Memoization mudah dalam JavaScript?-tutorial js-php.cn

Bagaimana untuk menulis kod fungsi Memoization mudah dalam JavaScript?

PHPz

Lepaskan： 2023-08-25 08:17:02

ke hadapan

869 orang telah melayarinya

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

Memori ialah teknologi pengoptimuman untuk meningkatkan prestasi fungsi. Sebelum kita mulakan dengan teknik hafalan, mari kita gunakan contoh berikut untuk memahami mengapa kita memerlukannya.

Contoh (Cara mudah untuk mencari nombor Fibonacci)

Dalam contoh di bawah, kami telah melaksanakan kaedah mudah untuk mencari nombor Fibonacci ke-. Kami menggunakan kaedah rekursif untuk mencari nombor Fibonacci ke-.

<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>

Salin selepas log masuk

Contoh di atas berfungsi dengan baik untuk nilai input kecil kurang daripada 1000, tetapi apabila kita memasukkan nilai input dalam julat 10⁴, ia mengambil lebih banyak masa daripada biasa, dan untuk input dalam julat 10⁶, Pelayar ranap kerana memori di luar had.

Kami boleh mengoptimumkan kod di atas menggunakan teknologi memori, yang membolehkan kami menyimpan hasil pengiraan sebelumnya. Sebagai contoh, untuk mencari nombor Fibonacci ke-4, kita perlu mencari nombor Fibonacci ke-3 dan ke-2. Begitu juga, untuk mencari nombor Fibonacci ketiga, kita mesti mencari nombor Fibonacci kedua dan pertama. Jadi di sini kita mengira nombor Fibonacci kedua dua kali.

Sekarang, andaikan anda ingin mencari nilai ke-n terbesar bagi jujukan Fibonacci, anda boleh fikirkan berapa kali ia perlu diulang. Jadi untuk tujuan pengoptimuman kita boleh mengira nombor Fibonacci kedua untuk kali pertama dan menyimpannya dalam pembolehubah sementara. Kemudian, apabila kita perlu mengira nombor Fibonacci kedua sekali lagi, kita boleh mengaksesnya daripada tatasusunan, menjadikan kod itu lebih cekap.

Selain itu, menyimpan hasil yang dikira sebelumnya dalam tatasusunan untuk kegunaan kemudian juga merupakan penghafalan.

Tatabahasa

Pengguna boleh mengikuti sintaks di bawah untuk menghafal nombor Fibonacci ke-1.

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

Salin selepas log masuk

Dalam sintaks di atas, kami mula-mula menyemak sama ada nombor Fibonacci ke-1 telah wujud dalam objek 'temp' dan kemudian mengembalikan nilai jika tidak, kami mengira nilainya dan menambah bijih ke objek sementara.

Kaedah

Langkah 1 – Gunakan pernyataan if untuk menyemak sama ada hasil n wujud dalam objek sementara. Jika ya, nilai yang dikira sebelum ini dikembalikan.

Langkah 2 – Jika n kurang daripada atau sama dengan 1, kembalikan 1 sebagai huruf asas bagi fungsi rekursif.

Langkah 3 – Kira nombor Fibonacci n-1 dan n-2, tambahkannya dan simpan dalam objek sementara untuk kegunaan kemudian.

Langkah 4 – Simpan nombor Fibonacci ke-1 dan kembalikan kepada objek sementara.

Contoh (mencari nombor Fibonacci ke-n menggunakan memori)

Menggunakan teknik memoisasi, kami mengoptimumkan kod untuk contoh pertama dalam contoh di bawah. Kami menggunakan objek temp untuk menyimpan hasil pengiraan sebelumnya. Dalam output, pengguna boleh melihat bahawa kod di bawah adalah lebih cekap daripada kod dalam contoh pertama.

<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>

Salin selepas log masuk

Kaedah: Gunakan memori tanpa menggunakan ruang tambahan

Langkah 1 – Mulakan a kepada 0 dan b kepada 1.

Langkah 2 – Gunakan gelung for untuk n lelaran untuk mencari nombor Fibonacci ke-n.

Langkah 3 – Di sini, c ialah pembolehubah sementara yang menyimpan nombor Fibonacci (i-1).

Langkah 4 – Simpan nilai pembolehubah b dalam a.

Langkah 5 – Simpan nilai pembolehubah c dalam pembolehubah b.

Contoh

Contoh di bawah juga merupakan varian yang dioptimumkan bagi contoh pertama. Dalam contoh kedua, kami menggunakan objek temp untuk menyimpan hasil pengiraan sebelumnya, tetapi dalam kod di bawah, kami menggunakan pembolehubah sementara tunggal bernama c.

Kod di bawah ialah cara paling berkesan untuk mencari jujukan Fibonacci kerana kerumitan masanya ialah O(n) dan kerumitan ruang ialah 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>

Salin selepas log masuk

Dalam tutorial ini, kami belajar tentang teknik ingatan untuk mengoptimumkan kod untuk menjadikannya lebih cekap masa dan ruang. Pengguna boleh melihat cara kami mengoptimumkan kod contoh pertama menggunakan algoritma yang berbeza dalam contoh kedua dan ketiga.

Atas ialah kandungan terperinci Bagaimana untuk menulis kod fungsi Memoization mudah dalam JavaScript?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!