What means Memoization?

The definintion of memoization from the wikipedia is the following:

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

Memoization is a programming techique which allows reduce the function's time cost for space cost. That is, the functions which are memoized gains speed for a higher use of memory space.

The memoization only can be used in pure functions, so the first point is known that is a pure function

In the following animation you can see the final result of applied memoization in our code.

What is a pure function?

A pure function is a function that meets the following criteria:

1. It is a function that always returns the same result when the arguments are the same. For example, the following functions are impure:

• Functions which use random numbers.
• Functions which use datetime as seed to generate the result.

2. It is a function that does not produce side effects in the application:

• Data mutation or change application state.
• Network request.
• Database or file request.
• Obtaining user input.
• Querying the DOM

Benefits

The pure functions are being used in the web develop due to several benefits. Although, the pure functions are not only use in the web develop. Well, the main pure function's benefits are:

1. Your code is more declarative which is focus in what must to do and doest not in how must to do. Also, the functions are focus in how different inputs are related to outputs.
2. The code is more testability, and find bugs is more easy that in impure functions.

But, in the real life there are side-effects and it is a good part of the code (for example, when you access to the database or communicate different servers to request information about the system). So, pure functions are a part of your code, and you need to know when you can use a pure functions and when you can use memoization in your code.

Pure functions example

Recursive functions frequently use the pure functions, the most classical recursive problem is the factorial.

function factorial(num){
  return num === 0 ? 1 : (num * factorial(num - 1));
}

But the imperative version of the function factorial is pure too, because the pure functions is related with inputs and outputs. In both case when the input is the same the output will be the same.

function factorial(num) {
	let total = 1; 
	for (i = 1; i <= num; ++i) {
		total = total * i; 
	}
	return total; 
}

Another interesting examples of pure functions are the following:

const add = (x, y) => x + y 
const calculateBill = (sumOfCart, tax) => sumOfCart * tax

Memoization in recursive functions

The memoization is the programming technique which allows doesn't recalculated the value of the pure function. I.e, the pure functions returns the same value when have the same inputs. So, the value return can be store in the system using any cache system (for example a map or array). So, if you calculate the value of factorial(1) you can store the return value 1 and the same action can be done in each execution. So, when you run the factorial(100) you take a while the first time but the second and more times the time will be reduced!

In this case, if you note the recursive factorial version, you can note that this version execute several times the function factorial which can be cache in our system (using memoization) but if you use the imperative factorial version your performance will be worse. For this reason, memoization is a good known technique in declarative languages.

Memoization Example! - Live code!

In this section I'm going to show you how implement memoization using closure and the decorator pattern using JavaScript.

The decorator pattern allows add new features to any object in runtime using composition instead of hierarchy. The pattern goal is avoid create a class hierarchy of our features.

A good example to understand this pattern can be found in the Addy Osmany's Blog.

So, a basic implementation of memoize decorator in JavaScript is the following:

const memoize = fn => {
  const cache = {}; // 1
  return (...args) => { // 2
    const stringifiedArgs = JSON.stringify(args); // 3
    const result = (cache[stringifiedArgs] =
      typeof cache[stringifiedArgs] === 'undefined' 
        ? fn(...args)
        : cache[stringifiedArgs]); // 4
    return result; // 5
  };
};

1. Define the cache in which the execution's result will be store. We use a object as map to store this results.
2. The decorator returns a new function which has the same behaviour that original function but memoization is implemented.
3. The key of the key-value map is generated using the stringify and args from the original function.
4. The result of the new function will be
   1. The execution of the original function (fn(...args)) whether there is not store in the cache.
   2. The value stored in the cache (whether there is pre-calculated previously).
5. The result is returned.

How to used our memoized decorator ?

The way to used this decorator using JavaScript is very easy:

const add = (x, y) => x + y;
const addMemoized = memoize(add); //Decorator Pattern

In this case the add function is the original function without memoization and the addMemoized function is the new function which has the new feature (memoization) using the decorator pattern.

A real demo using memoization!

Now, I'm going to show you a real deam using memoization. Imagine a complex algorithm that indicate you if an array has a unique value (as the Array.prototype.some) but horribly programmed.

const isUniqueExponential = arr => {
  let result = true;
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (i !== j && arr[i] === arr[j]) {
        result = false;
      }
    }
  }
  return result;
};

The following step is run the original code and the code using memoization and compare the time use in each function. It is very important remember that the original code is not modified but the memoization feature is added.

The following function is used to measure the time used in each execution.

const measureTime = (cb, args) => {
  const t0 = performance.now();
  cb(args);
  const t1 = performance.now();
  console.log('Call to doSomething took ' + (t1 - t0) + ' milliseconds.');
};

The array are generated at the begin of the script:

const randomArray = len =>
  Array.from({ length: len }, () => Math.floor(Math.random() * len));

const params = [
  randomArray(19000),
  randomArray(19000),
  randomArray(19000),
  randomArray(19000)
];

And finally, when the user click in a button the functions are execute.

1. No Memoization

buttonNoMemoization.addEventListener('click', () => {
  console.clear();
  const times = inputTimes.value;

  console.log('NOT USING MEMOIZATION');
  console.log('first execution');
  for (let i = times; i > 0; i--) {
    params.forEach(param => measureTime(isUniqueExponential, param));
  }
  console.log('---- FINISHED ----');
});

2. Memoization

buttonMemoization.addEventListener('click', () => {
  console.clear();
  const times = inputTimes.value;
  const isUniqueExponentialMemoized = memoize(isUniqueExponential); //Decorator Pattern
  console.log('USING MEMOIZATION');
  console.log('first execution');
  for (let i = times; i > 0; i--) {
    params.forEach(param => measureTime(isUniqueExponentialMemoized, param));
  }
  console.log('---- FINISHED ----');
});

The result is shown in the following animation:

Conclusions

The memoization has been widely developed in web development using TypeScript or JavaScript. The following list of resources must be the starting point to use them in your projects.

• Fast Memoize.
• Moize.
• Memoizee
• Lodash-Decorators

Fast-Memoize use this graph to compare different implementations of memoize:

More Theory:

• https://medium.com/@reallygordon/implementing-memoization-in-javascript-5d140bb04166
• https://blog.bitsrc.io/understanding-memoization-in-javascript-to-improve-performance-2763ab107092

• The GitHub project is https://github.com/Caballerog/blog/memoization