javascriptnode.jsmemoization

Implementing Automatic Memoization (returns a closured function) in JavaScript


I've read

http://www.sitepoint.com/implementing-memoization-in-javascript/

Automatic Memoization

In all of the previous examples, the functions were explicitly modified to add memoization. It is also possible to implement a memoization infrastructure without modifying the functions at all. This is useful because it allows the function logic to be implemented separately from the memoization logic. This is done by creating a utility function which takes a function as input and applies memoization to it. The following memoize() function takes a function, “func”, as input. memoize() returns a new function which wraps a caching mechanism around “func”. Note that this function does not handle object arguments. In order to handle objects, a loop is required which would inspect each argument individually and stringify as needed.

function memoize(func) {
  var memo = {};
  var slice = Array.prototype.slice;

  return function() {
    var args = slice.call(arguments);

    if (args in memo)
      return memo[args];
    else
      return (memo[args] = func.apply(this, args));

  }
}

using this, I did

var fib = function(n)
{
  if (n <= 1)
  {
    return 1; // as the Fib definition in Math
  }
  else
  {
    return fib(n - 2) + fib(n - 1); // as the Fib definition in Math
  }
};

log(memoize(fib)(43));
log(fib(43));

However, I confirmed there's no effect.

I also tried a npm library for the same purpose,

https://github.com/medikoo/memoize

and

var memoize = require('memoizee');

log(memoize(fib)(43));
log(fib(43));

The result, same.

What do I miss, and how to fix and make it work?

Thanks!

EDIT

require('memoizee');

var fib = function(n)
{
  if (n <= 1)
  {
    return 1; // as the Fib definition in Math
  }
  else
  {
    return fib(n - 2) + fib(n - 1); // as the Fib definition in Math
  }
};

var generator = function(f)
{
  return memoize(f);
};

var _fib = generator(fib);
console.log(_fib(40)); //no effect

Solution

  • The memoize call does not alter the fib function, but returns its new, memoized counterpart. In your code, you're calling that one only once, and the original fib function the next time. You need to create one memoized "wrapper", and call that multiple times:

    var mFib = memoize(fib);
    log(mFib(43));
    log(mFib(43));
    

    You could also overwrite the original fib = memoize(fib);, which would have the additional benefit that the recursive calls (which are the interesting ones) will be memoized as well.