Memoization

01_fibonacci_no_memo.js

// fibonacci function without memoization
function fib(n) {
  if (n === 0) return 0;
  if (n === 1) return 1;
  return fib(n - 2) + fib(n - 1);
}
const start =  Date.now();
console.log(fib(42));
console.log(`Time consumed ${Date.now() - start} ms`);

02_fibonacci_with_memo.js

// fibonacci function with memoization
function fib(n) {
  if (!fib.memo) fib.memo = {};
  if (!fib.memo[n]) {
    if (n === 0) return (fib.memo[n] = 0);
    if (n === 1) return (fib.memo[n] = 1);
    fib.memo[n] = fib(n - 2) + fib(n - 1);
  }
  return fib.memo[n];
}
const start =  Date.now();
console.log(fib(42));
console.log(`Time consumed ${Date.now() - start} ms`);

033_fct_obj_memo_pattern.js.js

// function object memoization for multiple args

// const memoiseFct = function (arg1, arg2) {
const memoiseFct = function (...args) {
  if (memoiseFct.memo) memoiseFct.memo = {};

  // const key = JSON.stringify(Array.prototype.slice.call(arguments));
  const key = JSON.stringify(args);

  if (!memoiseFct.memo[key]) {
    let result = {};
    // result = someCalculations;
    memoiseFct.memo[key] = result;
  }
  return memoiseFct.memo[key];
};

03_fct_obj_memo_pattern.js

const memoiseFct = function (arg) {
  if (memoiseFct.memo) memoiseFct.memo = {};

  if (!memoiseFct.memo[arg]) {
    let result = {};
    // result = someCalculations; // insert calculation to be memoized
    memoiseFct.memo[arg] = result;
  }
  
  return memoiseFct.memo[arg];
};

04_fct_ obj_memo.js

const memoiseFct = function (arg) {
  if (!memoiseFct.memo) memoiseFct.memo = {};

  if (!memoiseFct.memo[arg]) {
    memoiseFct.memo[arg] = Date.now();
  }
  return memoiseFct.memo[arg];
};

console.log('fst call ', memoiseFct(4));
setTimeout(()=>{
    console.log('scd call ', memoiseFct(4));
}, 1000);

console.log('trd call ', memoiseFct(4));

05_fib_fct_obj_memo.js

const memoiseFct = function (arg) {
  if (!memoiseFct.memo) memoiseFct.memo = {};

  if (!memoiseFct.memo[arg]) {
    const fib = function (n) {
      if (n === 0) return 0;
      if (n === 1) return 1;
      return fib(n - 2) + fib(n - 1);
    };
    memoiseFct.memo[arg] = fib(arg);
  }
  return memoiseFct.memo[arg];
};

// first execution
const start1 =  Date.now();
console.log(memoiseFct(42));
console.log(`Time consumed for first execution ${Date.now() - start1} ms`);

// second execution
const start2 =  Date.now();
console.log(memoiseFct(42));
console.log(`Time consumed for second execution ${Date.now() - start2} ms`);

06_hof_memo.js

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

// higher order function memoisation
function memoiseFct(fn) {
  const cacheObj = {};  // initialise cache object
  return function (...args) {  // ...args get whatever args passed to our memoised function
    const key = JSON.stringify(args);  // get strigified args '[x]' to make it as key inside our cacheObj
    if (!cacheObj[key]) {
      cacheObj[key] = fn(args);
    }
    return cacheObj[key];
  };
}

// memoise the fibonacci function
const mfib = memoiseFct(fib);

// first execution
const start1 =  Date.now();
console.log(mfib(42)); // 267914296
console.log(`Time consumed for first execution ${Date.now() - start1} ms`); // Time consumed for first execution 4740 ms

// second execution
const start2 =  Date.now();
console.log(mfib(42)); // 267914296
console.log(`Time consumed for second execution ${Date.now() - start2} ms`); // Time consumed for first execution 0 ms

07_closure_memo.js

const memoiseFib = (function () {
  // outer scope
  const cache = [0, 1]; // this array is updated by the inner function

  // inner function that has a closure
  const fib = function (n) {
    if (cache[n] === undefined) { // 
      cache[n] = fib(n - 2) + fib(n - 1);
    }
    return cache[n];
  };
  return fib;
})(); // self invoked function help us access inner function to benefit from the closure

const start1 =  Date.now();
console.log(memoiseFib(900)); // 5.487710883947999e+187
console.log(`Time consumed for first execution ${Date.now() - start1} ms`); // Time consumed for first execution 1 ms