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

The name of the technique is actually "memoization". Googling that might bring more results. — Martin Smith, Nov 20 '13 at 18:18

score 9 · Accepted Answer · edited May 23 '17 at 12:15

9

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.

edited May 23 '17 at 12:15

Community

1
1

answered Nov 20 '13 at 18:19

Drew Noakes

300,895
165
679
742

Hey Drew, I saw that article. Thanks for the SO example, this one helps a lot! – Nov 20 '13 at 18:22
I think this answer can be improved. To me, right now it looks like you are assuming the function returns the same value each time (if cachedResult is undefined, assign the value to the var, if not, get it from the var), and the `/*do your computation*/` leaves a lot to the imagination. – Aug 22 '19 at 08:33
@ArturTagisow memoization is exactly that though: returning the same result for a given argument list. In this example, there are no arguments, so the cache is just a single value. If you have an argument list then the memory/cache will need to take that into account. – Drew Noakes Aug 26 '19 at 23:59

score 5 · Answer 2 · answered Nov 20 '13 at 18:24

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]
}

score 3 · Answer 3 · answered Jul 17 '19 at 22:40

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

Beeno Tung · Answer 4 · 2018-03-06T05:58:40.553

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.

Javascript Memoization

4 Answers4

Linked