Kas yra memoizacija?

Memosacija — tai optimizacijos technika, naudojama programavime, siekiant pagreitinti funkcijų vykdymą jų iškvietimo rezultatų kaupimu tam tikrais įėjimo parametrais.

Vėliau, iškviečiant tą pačią funkciją su tais pačiais argumentais, funkcija neperskaičiuoja rezultato iš naujo, o grąžina išsaugotą (atmintyje įsimintą) reikšmę.

Tai ypač naudinga resursų reikalaujančioms funkcijoms su deterministiniu elgesiu (funkcijos, kurios visada grąžina tą patį rezultatą su tais pačiais įėjimo duomenimis).

Privalumai:

• pagreitina resursų reikalaujančių funkcijų vykdymą;
• sumažina procesoriaus apkrovą, išvengiant pakartotinių skaičiavimų;

Trūkumai:

• padidina atminties naudojimą saugant kaupiklį;
• gali būti neefektyvu funkcijoms, kurios dažnai kviečiamos su skirtingais argumentais arba keičia savo elgesį.

JavaScript pavyzdys:

function fibonacci(n) { // Fibonacci skaičių funkcijos apibrėžimas
  if (n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2); // Rekursinis iškvietimas
}

// Memosizuota funkcijos versija
function memoizedFibonacci(n, cache = {}) {
  if (n in cache) { // Patikriname, ar rezultatas yra kaupiklyje
    return cache[n];
  }

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

  // Apskaičiuojame ir išsaugome kaupiklyje
  cache[n] = memoizedFibonacci(n - 1, cache) + memoizedFibonacci(n - 2, cache);
  return cache[n];
}

// Greičio palyginimas:
console.time('Be memoizacijos');
fibonacci(40);
console.timeEnd('Be memoizacijos'); // Žymiai ilgiau

console.time('Su memoizacija');
memoizedFibonacci(40);
console.timeEnd('Su memoizacija'); // Žymiai trumpiau

Šiame pavyzdyje, be memoizacijos, funkcija fibonacci kartotinai skaičiuoja tas pačias reikšmes. Memosizuota versija memoizedFibonacci saugo apskaičiuotas reikšmes cache objekte, žymiai pagreitindama vėlesnius iškvietimus su tais pačiais argumentais.