Memorization در جاوااسکریپت

حافظه‌سازی (Memoization) به ما اجازه می‌دهد که نتیجه محاسبات قبلی یک تابع را ذخیره کنیم تا در محاسبات بعدی به جای محاسبه دوباره، از نتیجه ذخیره‌شده استفاده کنیم. برای این کار، تابعی را تعریف می‌کنیم که یک تابع دیگر را گرفته و آن را با قابلیت حافظه‌سازی برمی‌گرداند. اینجا از call برای فراخوانی تابع اصلی استفاده می‌کنیم، که می‌تواند با یک this مشخص فراخوانی شود.

در مثال زیر، تابع memoize برای حافظه‌سازی تعریف شده و تابع fibonacci به کمک آن بهینه‌سازی می‌شود:

const memoize = (fn) => {  const cache = {};  return function (...args) {    const key = args.toString();    if (cache[key]) {      return cache[key];    }    const result = fn.call(this, ...args);    cache[key] = result;    return result;  };};const fibonacci = memoize(function (n) {  if (n <= 1) return n;  return fibonacci(n - 1) + fibonacci(n - 2);});console.log(fibonacci(10));

در جاوااسکریپت، زمانی که از call استفاده می‌کنیم، می‌توانیم مشخص کنیم که this در داخل تابع چه چیزی باشد. در کد بالا، fn.call(this, ...args) در حال فراخوانی fn است و این امکان را فراهم می‌کند که this در تابع fn با this تابع بیرونی مقداردهی شود.

اما اینجا یک نکته وجود دارد: چون تابع fibonacci در این مثال به هیچ شیء خاصی وابسته نیست، this مقدار خاصی را نمایندگی نمی‌کند. در این حالت:

اگر کد در حالت عادی (غیر strict) اجرا شود، this به شیء global (window در مرورگرها یا global در Node.js) اشاره خواهد کرد. در حالت strict، this برابر با undefined خواهد بود، زیرا context خاصی تنظیم نشده است. بنابراین، در این مثال خاص، حتی اگر this مقدار خاصی را نشان ندهد، کد به‌درستی کار می‌کند. اگر بخواهیم به‌طور واضح مشخص کنیم که this در اینجا به چیزی اشاره ندارد، می‌توانیم مقدار null را برای this به call بدهیم:

const result = fn.call(null, ...args);

یا حتی به سادگی می‌توانیم از call استفاده نکنیم و fn را مستقیماً فراخوانی کنیم:

const result = fn(...args);

در این صورت، this در تابع fn به چیزی اشاره نخواهد کرد و به صورت خودکار در حالت global تعریف نمی‌شود. در این مقاله، بهینه‌سازی توابع بازگشتی مثل فیبوناچی با استفاده از روش حافظه‌سازی و به کمک call و this را بررسی کردیم. متوجه شدیم که چطور می‌توان از call برای تنظیم مقدار this در فراخوانی توابع استفاده کرد، اما در مواردی که نیاز به this نداریم، می‌توانیم آن را null در نظر بگیریم یا کلاً call را حذف کنیم.

حافظه‌سازی یک روش عالی برای بهبود عملکرد توابع بازگشتی سنگین مثل فیبوناچی است و به کمک آن می‌توانیم زمان اجرای تابع را از حالت نمایی به خطی کاهش دهیم. برای این که ببینم چقدر این تکنیک میتونه کمک کننده باشه میتونیم از کد زیر استفاده کنیم، توی این کد از فانکشن time برای اندازه گیری زمان اجرای تابع استفاده می کنیم:

const fibonacciNaive = (n) => {  if (n <= 1) return n;  return fibonacciNaive(n - 1) + fibonacciNaive(n - 2);};const memoize = (fn) => {  const cache = {};  return function (...args) {    const key = args.toString();    if (cache[key]) {      return cache[key];    }    const result = fn.call(this, ...args);    cache[key] = result;    return result;  };};const fibonacciMemoized = memoize(function (n) {  if (n <= 1) return n;  return fibonacciMemoized(n - 1) + fibonacciMemoized(n - 2);});const n = 40; console.time("Naive Fibonacci");console.log(fibonacciNaive(n));console.timeEnd("Naive Fibonacci");console.time("Memoized Fibonacci");console.log(fibonacciMemoized(n));console.timeEnd("Memoized Fibonacci");

خروجی:

102334155Naive Fibonacci: 994ms102334155Memoized Fibonacci: 0.10000002384185791ms

همانطور که می بینیم تکنیک memoization فقط یک میلی ثانیه طول کشید در صورتی که بدون اون 994 میلی ثانیه حساب کردن 40 عدد اول فیبوناچی 994 میلی ثانیه طول میکشه.