Dynamic Programming: Using Memoization to Improve Your Javascript Functions

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 mathematical optimization method and a computer programming method. There are two key attributes a problem must have if dynamic programming must really apply, they are optimal structure and overlapping sub-structure. We won’t go deeply into dynamic programming but will instead focus on how overlapping substructure is one of dynamic programming’s key attributes. This matters because it concerns storing solutions for the next problem. In this article, we will learn about what memoization is, what value memoization provides to Javascript developers, and how to use it to improve Javascript functions.

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:

1. Referential transparent
2. 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:

https://developer.yahoo.com/yui/3/cache/

https://github.com/planttheidea/micro-memoize

https://github.com/caiogondim/fast-memoize.js

https://lodash.com/docs/4.17.15#memoize

**
**

Alright, that’s it guys catch you on the next one…