Månadsarkiv: maj 2017

Memoization

This blog post is also available on the Fortnox developer blog.

As developers we have a large selection of design patterns and techniques at our disposal when we design and implement our solutions. This is especially true in object oriented code; patterns such as decorators, builders and factory methods are just some of the patterns you probably see during your workday if you are coding with that paradigm.

Most of these design patterns have names that reveal their purpose. If we take the three patterns mentioned in the previous paragraph, the decorator pattern decorates an object with additional behaviour. The purpose of the builder and factory patterns are also reflected in their names; the builder pattern lets you construct an instance of a class using a fluent interface, while the factory method pattern is used to separate the construction of a complex object so that it resides in its own distinct method.

But then there are other techniques whose names do not convey their purpose as clearly. One example I would like to mention here is memoization, which is a concept I have stumbled upon several times during my days and figured that it must be something very mysterious. With a name like that it must be something really hard to understand, right?

Well not really. Memoization is basically an optimization technique in which a cache is used to store previous results of expensive computations. If the computation has occurred once, the following calls to the same routine will return the cached value instead of redoing all that work again.

In my attempt to understand how the technique works I decided to implement memoization in JavaScript, and this implementation can be seen below. The code defines a function called memoization, which closes over an initial numeric value. This value will then be used as the first operand for simple addition calculations. When you call memoization with a numeric value, that value will be used as the other operand and the result is returned. Previous results are cached according to the memoization technique.

let memoization = (val) => {
  let cache = {};

  return (other) => {
    if (!cache[other]) {
      // replace assignment below with your expensive computation
      cache[other] = val + other;
      console.log('Cached new value');
    }

    return cache[other];
  }
}

let plusFive = memoization(5);

// first call caches the result and outputs "Cached new value".
plusFive(10);

// second call reuses the cached result, i.e. no console output this time.
plusFive(10);

Now you’re probably thinking that a simple addition is not a very costly computation, and that’s true. The whole idea of this example was just to show how an implementation of the technique can look like. Apparently, the technique is useful for purposes other than optimization, but that is for you to dig into if you want to know more. :)

That’s all for now. Until next time!