Javascript Memoization

Question

Can someone please provide a simple function with memorization using only Javascript. I found a few articles online when googling, but I didn't see a lot on it. The best article that I found was this one:

http://alivedise.github.io/blog/2012/12/22/javascript-memorization/

I understand what caching is but, the example was way too complex for me. I was hoping that anyone here could please provide a simple function and call so that I can take that and begin to understand this more in depth.

Thanks

Answer 1

I think what you're looking for is memoization.

From Wikipedia:

memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs

There's a nice article here and another SO question here.

You'd normally use memoization to reduce the cost of repeatedly computing a result that will always be the same. Any performance improvement comes at the expense of allocating memory for the cached results.

A simple example in code:

var cachedResult;
function doHeavyCalculation()
{
    if (typeof(cachedResult) !== 'undefined')
        return cachedResult;

    // no cached result available. calculate it, and store it.
    cachedResult = /* do your computation */;
    return cachedResult;
}

There are JavaScript frameworks that support memoizing any function, and they basically provide this boilerplate code for you in a reusable fashion by decorating a function.

Answer 2

I think you mean memoization, which basically means remembering what you have already calculated. The following is an algorithm for Fibonacci which uses memoization.

var cache = {1:1, 2:1};
function fib(n) {
    if(!cache[n]) // Have we already calculated this value?
       cache[n] = fib(n - 1) + fib(n - 2)  // Calculate and store it

    return cache[n]
}

Answer 3

I’m afraid all other answers use global variable, which is wrong. JavaScript offers better solution. Please notice the parentheses () after the function expression. It means that the function is fired immediately, and the result returned by the function (and assigned to the memo constant) Is another function, which make the computing itself, but which can use the cache as a variable from the context of the already fired function. The cache is accessible by the memo function only.

const memo = function () {
  let cache = [];
  return function (n) {
    if (cache.includes(n)) { console.log("already in memory") }
    else { console.log("first"); cache.push(n); }
  }
}();

memo(7) //first
memo(7) //already in memory
memo(7) //already in memory
memo(1) //first
memo(1) //already in memory

Answer 4

keslert's Fibonacci example is a good one, here's one more for your understanding using edit distance as an example.

// Map<string, Map<string, number>>
const cache = new Map();

// a: string, b: string
function editDistance(a, b) {
    if (a.length === 0) {
        return b.length;
    }
    if (b.length === 0) {
        return a.length;
    }
    let res = cache.getMap(a).get(b);
    if (res !== undefined) {
        return res;
    }
    res = Math.min(
        editDistance(pop(a), pop(b)) + (last(a) === last(b) ? 1 : 0)
        , editDistance(pop(a), b) + 1
        , editDistance(a, pop(b)) + 1
    );
    cache.getMap(a).set(b, res);
    return res;
}

It is worth to mention that for some cases, doing the computation directly is less costly than looking up the memory (cache). For example basic logical operation or a few step math.

To determine the exact case in detail, you need to know the mechanism used by the cache (the data structure, complexity of operation, even the medium of storage (i.e. are you using fast RAM or swapped to slow harddisk?)) which is implementation dependent on the browser / JavaScript engine.

source: https://github.com/beenotung/programming-class/blob/3f678ac48511d829149fb06c139e53cc2680ae82/edit-distance/edit-distance.ts

-- edit 2018 Mar 06, 13:56

In the example, the call to pop/1 function can also be cached as well.