Мемоизатсия чист?

Техникаи мемоизация — ин техникаи оптимизатсия мебошад, ки дар барномасозӣ барои суръат бахшидани иҷрои функсияҳо тавассути нигоҳ доштани натиҷаҳои даъватҳои онҳо бо параметрҳои муайян истифода мешавад.

Ҳангоми даъвати баъдӣ ба функсия бо ҳамон аргументҳо, ки қаблан истифода шудаанд, функсия натиҷаро дубора ҳисоб намекунад, балки арзиши захирашуда (запомшуда) аз кеш бармегардонад.

Ин махсусан барои функсияҳои сарфакорона бо рафторе, ки муайян аст, муассир аст (функсияҳое, ки ҳамеша натиҷаи якхела барои маълумоти воридотӣ медиҳанд).

Фоидаҳо:

• суръат бахшидани иҷрои функсияҳои сарфакорона;
• кам кардани бор дар коркардкунанда бо пешгирӣ аз ҳисобҳои такрорӣ.

Норасоиҳо:

• афзоиши истифодаи хотира барои нигоҳдории кеш;
• метавонад барои функсияҳое, ки бо аргументҳои гуногун даъват мешаванд ё рафторро тағйир медиҳанд, муассир набошад.

Масалан дар JavaScript:

function fibonacci(n) { // Тарзи функсионалӣ барои ҳисоб кардани рақамҳои Фибоначи
  if (n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2); // Даъвати рекурсивӣ
}

// Нусхаи мемоизатсияшудаи функсияи fibonacci
function memoizedFibonacci(n, cache = {}) {
  if (n in cache) { // Санҷед, ки натиҷа дар кеш ҳаст
    return cache[n];
  }

  if (n <= 1) {
    return n;
  }

  // Ҳисоб кардан ва нигоҳ доштани натиҷа дар кеш
  cache[n] = memoizedFibonacci(n - 1, cache) + memoizedFibonacci(n - 2, cache);
  return cache[n];
}

// Муайян кардани суръат:
console.time('Бе мемоизация');
fibonacci(40);
console.timeEnd('Бе мемоизация'); // Вақти хеле зиёдтар

console.time('Бо мемоизация');
memoizedFibonacci(40);
console.timeEnd('Бо мемоизация'); // Вақти хеле камиратар

Дар ин мисол, бе мемоизация, функсияи fibonacci арзишҳои якхелаеро бисёр такрор мекунад. Нусхаи мемоизатсияшудаи memoizedFibonacci арзишҳои ҳисобшударо дар объект cache нигоҳ медорад, ки ба таври назаррас даъватҳои минбаъдаро бо аргументҳои ҳамонро суръат мебахшад.