30 Days of Javascript 11 - Memoize

Given a function fn, return a memoized version of that function.

A memoized function is a function that will never be called twice with the same inputs. Instead it will return a cached value.

You can assume there are 3 possible input functions: sum, fib, and factorial.

sum accepts two integers a and b and returns a + b. fib accepts a single integer n and returns 1 if n <= 1 or fib(n - 1) + fib(n - 2) otherwise. factorial accepts a single integer n and returns 1 if n <= 1 or factorial(n - 1) * n otherwise.

Example 1:

Input “sum” [“call”,”call”,”getCallCount”,”call”,”getCallCount”] [[2,2],[2,2],[],[1,2],[]] Output [4,4,1,3,2]

Explanation const sum = (a, b) => a + b; const memoizedSum = memoize(sum); memoizedSum(2, 2); // Returns 4. sum() was called as (2, 2) was not seen before. memoizedSum(2, 2); // Returns 4. However sum() was not called because the same inputs were seen before. // Total call count: 1 memoizedSum(1, 2); // Returns 3. sum() was called as (1, 2) was not seen before. // Total call count: 2 Example 2:

Input “factorial” [“call”,”call”,”call”,”getCallCount”,”call”,”getCallCount”] [[2],[3],[2],[],[3],[]] Output [2,6,2,2,6,2]

Explanation const factorial = (n) => (n <= 1) ? 1 : (n * factorial(n - 1)); const memoFactorial = memoize(factorial); memoFactorial(2); // Returns 2. memoFactorial(3); // Returns 6. memoFactorial(2); // Returns 2. However factorial was not called because 2 was seen before. // Total call count: 2 memoFactorial(3); // Returns 6. However factorial was not called because 3 was seen before. // Total call count: 2 Example 3:

Input “fib” [“call”,”getCallCount”] [[5],[]] Output [8,1]

Explanation fib(5) = 8 // Total call count: 1

/**
 * @param {Function} fn
 */
function memoize(fn) {
  const cache = {};

  return function (...args) {
    const key = JSON.stringify(args);

    if (key in cache) {
      return cache[key];
    }

    const result = fn.apply(this, args);
    cache[key] = result;

    return result;
  };
}

/**
 * let callCount = 0;
 * const memoizedFn = memoize(function (a, b) {
 *	 callCount += 1;
 *   return a + b;
 * })
 * memoizedFn(2, 3) // 5
 * memoizedFn(2, 3) // 5
 * console.log(callCount) // 1
 */

The memoize function takes a function fn as a parameter. It initializes an empty cache object to store the computed results. The memoize function returns a new function that accepts any number of arguments using the rest parameter syntax (...args). Inside the new function, it converts the arguments array into a string key using JSON.stringify(args). It checks if the key exists in the cache object using the in operator. If it does, it returns the cached result. If the key doesn’t exist in the cache, it calls the original function fn.apply(this, args) to compute the result. The result is stored in the cache object using the key as the cache entry. Finally, it returns the result.