Implement a memoize function

Basic implementation

import generateCacheKey from './src/utils.js';

function memoize(fn) {
  const cache = new Map();

  function memoizedFnImpl(...args) {
    const cacheKey = generateCacheKey(args);

    if (!cache.has(cacheKey)) {
      const result = fn.call(this, ...args);
      cache.set(cacheKey, result);
    }

    return cache.get(cacheKey);
  }

  return memoizedFnImpl;
}

// assuming this is the function which we want to memoize
function expensiveOperation(a, b) {
  console.log('I am called');

  // creating artificial delay to make function call expensive
  for (let i = 0; i < 10000000; i++) {}
  return a * b;
}

// Usage of memoize function
const memoizedExpensiveOperation = memoize(expensiveOperation);

console.log(memoizedExpensiveOperation(1, 2)); // yields the logs
console.log(memoizedExpensiveOperation(3, 4)); // yields the logs
console.log(memoizedExpensiveOperation(1, 2)); // yields cache result directly

Although the implementation of the memoize function in itself in quite straight forward, the most crucial part which might not seem obvious at first is generation of the cache keys, i.e, implementation of the generateCacheKey method.

Generating effective cache keys

Working and creating an effective cache is always a tricky business. As it’s beyond the scope of the blog, I’ll only cover details which one might need to consider to discuss in an interview setting.

On first thought, one might approach generating keys using the join method on arrays like :
const cacheKey=args.join('_'), but that fails to consider two cases we can run into:

1. Cache keys must be able to differentiate between strings and numbers, i.e, if the function could operate with both type of arguments, we want to treat the two inputs const input=['Mike', 27] and const input=['Mike', '27'], differently. Using the join methods would yield same key which is 'Mike_27'.
2. If the seperator used comes as argument, there can be a cache key collision, i.e, ['Hello', '_Mike'] and ['Hello_', 'Mike'], would yield the same cache key which is 'Hello__Mike'.

Surprisingly, the most easiest solution that handles both the cases is the good old JSON.stringify(args).

function generateCacheKey(input) {
  return JSON.stringify(input);
}

Note: JSON.stringify(args), although is quite effective to solve the problem of generate unique keys based on the arguments, one might need to consider that it is effectively slower on larger data sets. In cases like these, a more robust and fast solution can be created using the Trie data structure.

I found this article by Christopher Alvear on Medium a very good starting point to learn about the same.

The implementation would be along the lines of:

function memoize(fn) {
  const cache = new Trie();

  function memoizedFnImpl(...args) {
    if (!cache.has(args)) {
      const result = fn.call(this, ...args);
      cache.set(args, result);
    }

    return cache.get(args);
  }

  return memoizedFnImpl;
}