Classic issues: Memoization

This article analyses the approach that lodash used in it's memoization function

The issue

In different frameworks, we have a lot of techniques to optimize our computations. It might be reselect for Redux, computed of Vue, useMemo of React etc. - all of them serves for purpose to save your computational and memory resources somehow.

let's assume that I have set of arguments that will communicate somehow to provide me resulting number (arg1 + arg2 * arg3 % arg4 sth like that) - and if this certain computation might be fast enough - firstly, there might be arguments of 100000 and more values, and secondly we may use more and more arguments to make it slow anyway.

function somefunction(a1, a2, a3, .....a100, b1, b2, ...) {
  //Here probably goes science
}

To prevent additional computations, there is an existing technique called memoization, which watches like 'Hey, did you already tried to do somethin like that? I just saved a result, give it, no need another computations';

Implementation

The solution will build on two important terms

High Order Function

Simply, it's a function that takes another function as an argument - and the resulting output also will be a function.

const memoizedComputation = memoize(somefunc);
memoizedComputation(someArg);

So let's write the function body:

function memoize(func) {
   return function(value) {
   }
}

Closure

This is when some function binded with references to lexical environment of it; Simply - talking, it is a function with access to external data.

We will need to use caching object to store some results of function calls, but it can't be inside of returning function cause it will recreate itself and we won't access to previously computed results

function memoize(func) {
   const cache = {};

   return function(value) {
   }
}

The body of returning function is very simple - either we computed something before and we return the result saved in cache - or we just compute and then save it:

return function(value) {
    if (cache[value] !== undefined) {
      return cache[value];
    }

    const result = func(value);

    cache[value] = result;

    return result;
}

The major part is done, next is only refactoring

As usual - typecheck of an argument

if (typeof func !== 'function') {
    throw new TypeError('Expected a function')
}

Object cache doesn't store correctly

I have a limitation there, cause object can only use keys as strings, so if I wanna say

cache[someObj] = value

it stores

[object Object]: value

I'm going to

• change it to Map for better storing
• provide a possibility to change it by function user

function memoize(func) {
  if (typeof func !== 'function') {
    throw new TypeError('Expected a function');
  }

  const memoized = function(value) {
    const cache = memoized.cache;

    if (cache.has(value)) {
      return cache.get(value)
    }

    const result = func(value);

    memoized.cache = cache.set(value, result) || cache;

    return result;
  }

  memoized.cache = new (memoize.Cache || Map);

  return memoized
}

memoize.Cache = Map

export default memoize;

So the code user is able to use

memoize.Cache = WeakMap

In case he awares that it will help to use the function in certain case more effectively

Arguments refactoring

So far, returning function accepts only one argument - this is totally incorrect, and to improve this part we will need:

1. use args from function
2. define a resolver as memoization param - to allow user to specify, how to calculate the key for cache in case of multiple params

function memoize(func, resolver) {
  if (
    typeof func !== 'function'
    || (resolver != null && typeof resolver !== 'function')
  ) {
    throw new TypeError('Expected a function');
  }

  const memoized = function(...args) {
    const key = resolver
      ? resolver.apply(this, args)
      : args[0];
    const cache = memoized.cache;

    if (cache.has(key)) {
      return cache.get(key)
    }

    const result = func.apply(this, args);

    memoized.cache = cache.set(key, result) || cache;

    return result;
  }

  memoized.cache = new (memoize.Cache || Map);

  return memoized;
}

That should be it, thank you for reading, gonna write more function divings like that in future so feel free to watch