Memoization is a form of caching. It’s a way of storing a value for easy access for later use.
Dynamic programming has been around for a decade. According to Wikipedia, Dynamic programming is both a
By the end of this article, you will understand what memoization is and why memoization is very useful for optimizing your application.
In this article, we are going to cover the following main topics.
- What is Memoization?
- The Main Concepts of Memoization
- Comparing Memoized Function and Unmemoized Function
- The Significance of Memoization
What is Memoization?
Memoization is a form of caching. It’s a way of storing a value for easy access for later use. Memoization is a way to remember a solution to a solved problem so that you don’t have to recalculate it when next you ever need to perform the same action again. For a function to be memoized though, there need to be some conditions met -is it must be referentially transparent - that is, only if calling the function has exactly the same effect as replacing that function call with its return value.
Memoization exists in most programming languages, like Ruby, C++, Python, there are even lots of libraries across some of these languages that make things even easier. In the cause of this article, our focus will be on Javascript. But the concept and idea are the same.
The Main Concepts of Memoization
To understand what memoization is, we need to look at the main concepts of memoization. There are two concepts that memoization follows and they are:
- Referential transparent
- Lookup table
1. Refrential transparent
An expression is called referentially transparent if it can be replaced with its corresponding value (and vice-versa) without changing the program's behavior. This requires that the expression be pure - that is to say, the expression value must be the same for the same inputs and its evaluation must have no side effects. An expression that is not referentially transparent is called referentially opaque.
With the above explanation, we can quickly start to relate it to the behavior of memoization, this concept makes it possible for us to write a memoized function.
2. Lookup table
A lookup table (LUT) is an array that replaces runtime computation with a simpler array indexing operation. The process is termed "direct addressing" and LUTs differ from hash tables in a way that, retrieves a value.
Comparing Memoized Function and Unmemoized Function
Take the canonical definition of the Fibonacci sequence, for instance:
function Fibo(n) {
if (n < 2) {
return n;
}
return Fibo(n - 1) + Fibo(n - 2);
}
As you can guess, this quickly becomes quite slow once you start using numbers greater than around 20. Once you’re dealing with numbers in the mid-thirties range, it crashes the computer.
The solution is to memoize the function
var IterMemoFib = function() {
var cache = [1, 1];
var fib = function(n) {
if (n >= cache.length) {
for (var i = cache.length; i <= n; i++) {
cache[i] = cache[i - 2] + cache[i - 1];
}
}
return cache[n];
}
return fib;
}();
Which is a wee bit of a pain and not exactly readable; or you can get the computer to do it for you:
Fib = Fib.memoize();
Due to technical (browser security) constraints, the arguments for memoized functions can only be arrays or scalar values. No objects.
The code extends the Function object to add the memoization functionality. If the function is a method, then you can pass the object into memoize().
Function.prototype.memoize = function () {
var pad = {};
var self = this;
var obj = arguments.length > 0 ? arguments[i] : null;
var memoizedFn = function () {
// Copy the arguments object into an array: allows it to be used as
// a cache key.
var args = [];
for (var i = 0; i < arguments.length; i++) {
args[i] = arguments[i];
}
// Evaluate the memoized function if it hasn't been evaluated with
// these arguments before.
if (!(args in pad)) {
pad[args] = self.apply(obj, arguments);
}
return pad[args];
};
memoizedFn.unmemoize = function () {
return self;
};
return memoizedFn;
};
Function.prototype.unmemoize = function () {
alert("Attempt to unmemoize an unmemoized function.");
return null;
};
The Significance of Memoization
- "remembers" results corresponding to some set of specific inputs
- Memoization lowers a function's time cost in exchange for space cost;
- Memoization is more machine-independent.
Conclusion: What is Memoization?
Let’s quickly review what we have been up to so far. We talked about memoization, alongside its two major concepts which are referentially transparent and lookup table. We also considered how important it is to our Javascript code, made a comparison between an unmemoized code and a memoized code, and learned about the technique used in caching values.
Additionally, I have included down below some helpful memoization libraries for Javascript:
**
**
Alright, that’s it guys catch you on the next one…