Not to be confused with memorization, memoization is a specific term for retaining a number of previously calculated values from a function.
As we saw earlier, side-effect-free functions can be called multiple times without causing problems. The corollary to this is that a function can also be called fewer times than needed. Consider an expensive function which does some complex or, at least, time-consuming math. We know that the result of the function is entirely predicated on the inputs to the function. So the same inputs will always produce the same outputs. Why, then, would we need to call the function multiple times? If we saved the output of the function, we could retrieve that instead of redoing the time-consuming math.
Trading off space for time is a classic computing science problem. By caching the result, we make the application faster but we will consume more memory. Deciding when to perform caching and when to simply recalculate the result is a difficult problem.
In the land of Westeros, learned men, known as Maesters, have long had a fascination with a sequence of numbers which seems to reappear a great deal in the natural world. In a strange coincidence they call this sequence the Fibonacci sequence. It is defined by adding the two previous terms in the sequence to get the next one. The sequence is bootstrapped by defining the first few terms as 0, 1, 1. So to get the next term we would simply add 1 and 1 to get 2. The next term would add 2 and 1 to get 3 and so forth. Finding an arbitrary member of the sequence requires finding the two previous members, so it can end up being a bit of calculation.
In our world we have discovered a closed form that avoids much of this calculation but in Westeros no such discovery has been made.
A naïve approach is to simply calculate every term like so:
let Fibonacci = (function () {
function Fibonacci() {
}
Fibonacci.prototype.NaieveFib = function (n) {
if (n == 0)
return 0;
if (n <= 2)
return 1;
return this.NaieveFib(n - 1) + this.NaieveFib(n - 2);
};
return Fibonacci;
})();This solution works very quickly for small numbers such as 10. However, for larger numbers, say greater than 40, there is a substantial slow-down. This is because the base case is called 102,334,155 times.
Let's see if we can improve things by memoizing some values:
let Fibonacci = (function () {
function Fibonacci() {
this.memoizedValues = [];
}
Fibonacci.prototype.MemetoFib = function (n) {
if (n == 0)
return 0;
if (n <= 2)
return 1;
if (!this. memoizedValues[n])
this. memoizedValues[n] = this.MemetoFib(n - 1) + this.MemetoFib(n - 2);
return this. memoizedValues[n];
};
return Fibonacci;
})();We have just memoized every item we encounter. As it turns out for this algorithm we store n+1 items, which is a pretty good trade-off. Without memoization, calculating the 40th fibonacci number took 963ms while the memoization version took only 11ms. The difference is far more pronounced when the functions become more complex to calculate. Fibonacci of 140 took 12 ms for the memoization version while the naïve version took… well, it is has been a day and it is still running.
The best part of this memoization is that subsequent calls to the function with the same parameter will be lightning-fast as the result is already computed.
In our example only a very small cache was needed. In more complex examples it is difficult to know how large a cache should be or how frequently a value will need to be recomputed. Ideally your cache will be large enough that there will always be room to put more results in. However, this may not be realistic and tough decisions will need to be made about which members of the cache should be removed to save space. There is a plethora of methods for performing cache invalidation. It has been said that cache invalidation is one of the toughest problems in computing science, the reason being that we're effectively trying to predict the future. If anybody has perfected a method of telling the future, it is likely they are applying their skills in a more important domain than cache invalidation. Two options are to prey on the least recently used member of the cache or the least frequently used member. It is possible that the shape of the problem may dictate a better strategy.
Memoization is a fantastic tool for speeding up calculations which need to be performed multiple times or even calculations which have common sub-calculations. One can consider memoization as just a special case of caching, which is a commonly used technique when building web servers or browsers. It is certainly worthwhile exploring in more complex JavaScript applications.