Melaksanakan Memoisasi dalam JavaScript

mata teras

Hafalan

adalah teknik pengaturcaraan yang meningkatkan prestasi fungsi dengan caching hasil pengiraan sebelumnya fungsi. Ini amat berguna untuk fungsi rekursif dan matematik yang sering menggunakan parameter yang sama.
Melaksanakan memori melibatkan menggunakan cache yang diindeks oleh parameter input oleh fungsi. Jika parameter wujud dalam cache, nilai cache dikembalikan;
Apabila menghafal digunakan untuk fungsi dengan pelbagai parameter, cache multidimensi boleh digunakan, atau semua parameter boleh digabungkan untuk membentuk satu indeks. Parameter objek perlu dibentangkan sebelum digunakan sebagai indeks.
• Hafalan
mempunyai batasan tertentu. Ia meningkatkan penggunaan memori dan mungkin tidak sesuai untuk fungsi yang dilaksanakan dengan cepat atau memanggil frekuensi rendah. Ia hanya boleh automatik dengan rujukan kepada fungsi telus, iaitu outputnya hanya bergantung pada inputnya dan tidak menghasilkan sebarang kesan sampingan.

Program sering membuang masa memanggil fungsi yang mengira semula hasil yang sama berulang kali. Hal ini terutama berlaku untuk fungsi rekursif dan matematik. Penjana nombor Fibonacci adalah contoh yang sempurna. Urutan Fibonacci adalah satu siri bilangan bulat yang bermula dengan jumlah sifar, di mana setiap nilai adalah jumlah dua nombor pertama dalam urutan. Menurut definisi ini, sepuluh nombor Fibonacci pertama adalah: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Dari perspektif pengaturcaraan, nombor Fibonacci biasanya dikira secara rekursif menggunakan fungsi berikut.

^{Fungsi ini berfungsi dengan baik untuk nilai "n" yang lebih kecil. Walau bagaimanapun, apabila "N" meningkat, prestasi jatuh dengan cepat. Ini kerana kedua -dua panggilan rekursif mengulangi kerja yang sama. Sebagai contoh, untuk mengira nombor Fibonacci ke -50, fungsi rekursif mesti dipanggil lebih daripada 40 bilion kali (40,730,022,147 tepat)! Untuk membuat keadaan lebih teruk, mengira angka ke -51 memerlukan mengulangi kerja hampir dua kali ganda. Jika fungsi itu mengingati apa yang dikira sebelum ini, ia dapat mengurangkan masalah kerja berulang.}

Asas Hafalan

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Hafalan

adalah teknik pengaturcaraan yang cuba meningkatkan prestasi fungsi dengan caching hasil pengiraan sebelumnya fungsi. Kerana objek JavaScript berkelakuan seperti array bersekutu, mereka sesuai untuk bertindak sebagai cache. Setiap kali fungsi memori dipanggil, parameternya digunakan untuk cache indeks. Jika data wujud, ia boleh dikembalikan tanpa melaksanakan keseluruhan fungsi. Walau bagaimanapun, jika data tidak di -cache, fungsi dilaksanakan dan hasilnya ditambah ke cache.

Dalam contoh berikut, fungsi Fibonacci asal ditulis semula untuk memasukkan memori. Dalam contoh ini, fungsi tanpa nama yang dilaksanakan sendiri mengembalikan fungsi dalaman f () yang digunakan sebagai fungsi Fibonacci. Apabila f () dikembalikan, penutupannya membolehkannya terus mengakses objek "Memo", yang menyimpan semua hasil sebelumnya. Setiap kali f () dilaksanakan, ia mula -mula memeriksa sama ada hasil daripada nilai "n" semasa wujud. Jika ada, nilai cache dikembalikan. Jika tidak, laksanakan kod Fibonacci asal. Perhatikan bahawa "memo" ditakrifkan di luar f () supaya ia dapat mengekalkan nilainya dalam pelbagai fungsi panggilan. Ingatlah bahawa fungsi rekursif asal dipanggil lebih daripada 40 bilion kali sebelum ia dapat mengira nombor Fibonacci ke -50. Dengan melaksanakan memori, nombor ini jatuh ke 99.

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

memproses pelbagai parameter

Dalam contoh sebelumnya, fungsi menerima parameter tunggal. Ini menjadikan pelaksanaan caching agak mudah. Malangnya, kebanyakan fungsi memerlukan pelbagai parameter, yang merumitkan indeks cache. Untuk menghafal fungsi dengan pelbagai parameter, cache mesti menjadi multidimensi, atau semua parameter mesti digabungkan untuk membentuk satu indeks.

Dalam kaedah multidimensi, cache menjadi hierarki objek, bukan satu objek. Setiap dimensi kemudian diindeks oleh parameter tunggal. Contoh berikut melaksanakan cache multidimensi untuk fungsi Fibonacci. Dalam contoh ini, fungsi menerima parameter tambahan "x" dan tidak ada apa -apa. Setiap kali fungsi dipanggil, kod memeriksa sama ada dimensi "x" wujud dan memulakannya jika tidak wujud. Sejak itu, dimensi "X" digunakan untuk cache nilai "n". Hasilnya ialah fungsi memanggil Fibonacci ("Foo", 3) dan Fibonacci ("Bar", 3) tidak dianggap sebagai hasil yang sama.

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;
})();

Alternatif kepada cache multidimensi adalah objek cache tunggal, yang diindeks oleh gabungan semua parameter fungsi. Dalam kaedah ini, parameter ditukar kepada array dan kemudian digunakan untuk cache indeks. Setiap fungsi mempunyai objek terbina dalam yang dinamakan "Argumen" yang mengandungi parameter yang diluluskan. "Argumen" adalah objek jenis yang dipanggil objek kelas. Ia sama dengan array, tetapi tidak boleh digunakan untuk cache indeks. Oleh itu, ia mesti terlebih dahulu ditukar kepada array sebenar. Ini boleh dilakukan menggunakan kaedah slice array (). Cache kemudiannya boleh diindeks menggunakan perwakilan array, seperti yang ditunjukkan sebelum ini. Contoh berikut menunjukkan bagaimana untuk mencapai matlamat ini. Perhatikan bahawa pembolehubah tambahan "kepingan" ditakrifkan sebagai rujukan kepada kaedah slice array (). Dengan menyimpan rujukan ini, anda boleh mengelakkan pengiraan berulang array.prototype.slice () overhead. Kemudian gunakan kaedah panggilan () untuk memohon slice () ke "argumen".

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;
})();

Parameter objek cache

Skim memori yang diperkenalkan di sini tidak mengendalikan parameter objek dengan baik. Apabila objek digunakan sebagai indeks, mereka mula -mula ditukar kepada perwakilan rentetan, seperti "[objek objek]". Ini menyebabkan pelbagai objek tidak dipetakan ke lokasi cache yang sama. Tingkah laku ini boleh diperbetulkan dengan merentasi parameter objek sebelum pengindeksan. Malangnya, ini juga melambatkan proses memori. Contoh berikut mewujudkan fungsi memori umum yang mengambil objek sebagai hujah. Ambil perhatian bahawa parameter objek dibentangkan menggunakan json.stringify () untuk membuat indeks cache.

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Memori automatik

Dalam semua contoh terdahulu, fungsi ini diubahsuai secara eksplisit untuk menambah memori. Infrastruktur menghafal juga boleh dilaksanakan tanpa mengubahsuai fungsi sama sekali. Ini berguna kerana ia membolehkan logik fungsi dilaksanakan secara berasingan daripada logik yang diingati. Ini dilakukan dengan mewujudkan fungsi utiliti yang mengambil fungsi sebagai input dan memohon untuk menghafalnya. Fungsi memoize () berikut mengambil fungsi "func" sebagai input. Memoize () mengembalikan fungsi baru yang membungkus mekanisme cache di sekitar "func". Perhatikan bahawa fungsi ini tidak mengendalikan parameter objek. Untuk memproses objek, gelung diperlukan yang akan memeriksa setiap parameter secara individu dan merentasi seperti yang diperlukan.

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;
})();

Had

Apabila merealisasikan ingatan, perkara berikut mesti diingat. Pertama, dengan menyimpan hasil lama, fungsi hafalan menggunakan memori tambahan. Dalam contoh Fibonacci, penggunaan memori tambahan tidak terhad. Jika penggunaan memori adalah masalah, cache saiz tetap harus digunakan. Overhead yang berkaitan dengan ingatan juga boleh menjadikannya tidak sesuai untuk fungsi yang dilaksanakan dengan cepat atau mempunyai frekuensi yang rendah.

Batasan memori terbesar adalah bahawa ia hanya boleh digunakan secara automatik untuk fungsi

rujukan telus

. Jika output fungsi hanya bergantung pada inputnya dan tidak menghasilkan sebarang kesan sampingan, fungsi dianggap rujukan-telus. Panggilan bahawa fungsi telus rujukan boleh digantikan dengan nilai pulangan mereka tanpa mengubah semantik program. Fungsi Fibonacci dirujuk telus kerana ia bergantung sepenuhnya pada nilai "n". Dalam contoh berikut, fungsi foo () tidak dirujuk telus kerana ia menggunakan pembolehubah global "bar". Oleh kerana "bar" boleh diubah suai di luar Foo (), tidak ada jaminan bahawa nilai pulangan akan tetap tidak berubah untuk setiap nilai input. Dalam contoh ini, kedua -dua panggilan ke Foo () mengembalikan nilai 2 dan 3, walaupun parameter yang diserahkan kepada kedua -dua panggilan adalah sama.

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;
})();

Perkara yang perlu diingat

Hafalan
• berpotensi dapat meningkatkan prestasi dengan caching hasil panggilan fungsi sebelumnya.
• Fungsi memori menyimpan cache yang diindeks oleh parameter inputnya. Jika parameter wujud dalam cache, nilai cache dikembalikan. Jika tidak, laksanakan fungsi dan tambahkan nilai yang baru dikira ke cache.
• Parameter objek perlu dibentangkan sebelum digunakan sebagai indeks.
• Hafalan boleh digunakan secara automatik untuk fungsi rujukan telus.
Hafalan
• mungkin tidak sesuai untuk fungsi yang tidak dipanggil dengan kerap atau dilaksanakan dengan cepat.

Soalan Lazim Mengenai Menghafal di JavaScript (FAQ)

Apakah tujuan utama menggunakan memori dalam JavaScript?

Hafalan adalah teknik pengaturcaraan yang digunakan untuk mengoptimumkan program komputer dalam bahasa JavaScript dan bahasa lain. Teknik ini melibatkan menyimpan hasil panggilan fungsi mahal dan menggunakannya semula apabila input yang sama muncul lagi. Ini dapat meningkatkan prestasi program dengan mengelakkan pengiraan yang tidak perlu. Ia amat berguna dalam situasi di mana fungsi atau fungsi rekursif yang berulang kali dipanggil dengan parameter yang sama.

Bagaimana memori berfungsi dalam JavaScript?

Dalam JavaScript, memori berfungsi dengan membuat cache untuk menyimpan hasil panggilan fungsi. Apabila memanggil fungsi, fungsi pertama memeriksa sama ada hasil input yang diberikan sudah ada dalam cache. Jika ya, fungsi mengembalikan hasil cache dan bukannya melakukan pengiraan lagi. Sekiranya hasilnya tidak berada di dalam cache, fungsi melakukan pengiraan, menyimpan hasil dalam cache, dan mengembalikan hasilnya.

Bolehkah anda memberikan contoh fungsi hafalan dalam JavaScript?

Sudah tentu, mari kita pertimbangkan contoh fungsi mudah yang mengira faktorial angka. Tanpa ingatan, fungsi kelihatan seperti ini:

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Menggunakan memori, kita dapat mengoptimumkan fungsi ini dengan menyimpan hasil panggilan fungsi sebelumnya:

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;
})();

Adakah terdapat batasan atau kekurangan menggunakan memori dalam JavaScript?

Walaupun hafalan dapat meningkatkan prestasi program JavaScript dengan ketara, ia bukan tanpa batasannya. Kelemahan utama memori adalah bahawa ia boleh mengambil banyak ingatan, terutamanya apabila menyimpan banyak data dalam cache. Jika tidak diuruskan dengan betul, ini boleh membawa kepada isu -isu prestasi. Tambahan pula, ingatan hanya sah apabila fungsi dipanggil dengan parameter yang sama beberapa kali. Hafalan tidak memberikan manfaat prestasi jika input fungsi sentiasa berbeza.

Bolehkah saya menggunakan hafalan untuk semua jenis fungsi dalam JavaScript?

Hafalan adalah yang paling berkesan apabila digunakan dengan fungsi tulen. Fungsi tulen adalah fungsi yang selalu mengembalikan hasil yang sama dari input yang sama dan tidak menghasilkan sebarang kesan sampingan. Menghafal fungsi boleh menyebabkan hasil yang tidak dijangka jika ia bergantung kepada keadaan luaran atau mempunyai kesan sampingan. Oleh itu, semasa anda boleh menggunakan hafalan secara teknikal untuk sebarang jenis fungsi dalam JavaScript, ia adalah yang terbaik untuk fungsi tulen.

Bagaimana untuk menghafal fungsi dengan pelbagai parameter dalam JavaScript?

Melaksanakan memori untuk fungsi dengan pelbagai parameter boleh menjadi agak rumit, tetapi ini pasti mungkin. Salah satu cara adalah untuk menukar argumen ke dalam rentetan yang boleh digunakan sebagai kunci dalam cache. Berikut adalah contoh:

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Adakah ada perpustakaan atau alat yang dapat membantu menghafal dalam JavaScript?

Ya, ada perpustakaan dan alat yang dapat membantu menghafal dalam JavaScript. Sebagai contoh, Lodash Perpustakaan Utiliti JavaScript yang popular menyediakan fungsi _.memoize yang dapat menghafal fungsi dengan mudah. Begitu juga, Perpustakaan Ramda menyediakan fungsi R.memoizeWith yang membolehkan anda menentukan fungsi kunci cache tersuai.

Bagaimana untuk membersihkan cache dalam fungsi memori?

Cache dalam fungsi memori boleh dibersihkan dengan hanya menetapkan semula objek cache. Berikut adalah contoh:

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;
})();

Bolehkah memori digunakan dalam kerangka JavaScript seperti React?

Ya, ingatan sangat berguna dalam kerangka JavaScript seperti React. Sebagai contoh, React menyediakan fungsi React.memo yang boleh digunakan untuk menghafal komponen. Ini dapat membantu meningkatkan prestasi dengan mencegah komponen yang tidak perlu.

Bagaimana memori dalam JavaScript berbanding teknik pengoptimuman lain?

Hafalan

adalah teknik pengoptimuman yang kuat, tetapi ia tidak selalu menjadi penyelesaian terbaik. Dalam sesetengah kes, teknik pengoptimuman lain seperti dejitter dan pendikit mungkin lebih sesuai. Kuncinya adalah untuk memahami keperluan khusus dan kekangan program dan memilih teknologi pengoptimuman yang betul.

Atas ialah kandungan terperinci Melaksanakan Memoisasi dalam JavaScript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!