5

I'm developing my own functional-programming library, and now referring the underscore.

memoize _.memoize(function, [hashFunction])

Memoizes a given function by caching the computed result. Useful for speeding up slow-running computations. If passed an optional hashFunction, it will be used to compute the hash key for storing the result, based on the arguments to the original function. The default hashFunction just uses the first argument to the memoized function as the key.

var fibonacci = _.memoize(function(n) {
  return n < 2 ? n: fibonacci(n - 1) + fibonacci(n - 2);
});

The above code that enables automatic memorisation without dealing array looks sort of magic, and I saw the source-code below, but still the inner design is not clear to me.

 // Memoize an expensive function by storing its results.
  _.memoize = function(func, hasher) {
    var memoize = function(key) {
      var cache = memoize.cache;
      var address = hasher ? hasher.apply(this, arguments) : key;
      if (!_.has(cache, address)) cache[address] = func.apply(this, arguments);
      return cache[key];
    };
    memoize.cache = {};
    return memoize;
  };

Can someone give me a brief idea of what is going on?

Appreciated.

2
  • 1
    What parts of it don't you understand or are struggling with?
    – Bergi
    Jun 30, 2014 at 12:03
  • 1
    Why aren't you looking at the most recent version of Underscore? That's not the current implementation of _.memoize. Jun 30, 2014 at 17:39

2 Answers 2

9

memoize has a cache (memoize.cache = {}) that uses for storing the result of the function call. When it's called, it determines an address to store the result by two means: either a call to the hasher function, or the key parameter.

The hasher function works like this (from the underscore page):

If passed an optional hashFunction, it will be used to compute the hash key for storing the result, based on the arguments to the original function. The default hashFunction just uses the first argument to the memoized function as the key.

Then, it calls the function you passed func.apply(...), and stores the result at cache[address].

The second time you call the memoized function, the result will already be in cache (!_.has(..) will return false) and the computation won't be repeated.

I dont' understand why it returns cache[key] and not cache[address] tough...seems to me that cache[address] would be the correct choice.

Update

As pointed out in the comments, the code you present is not the latest implementation of memoize. This is the latest implementation (1.6.0):

_.memoize = function(func, hasher) {
    var memo = {};
    hasher || (hasher = _.identity);
    return function() {
      var key = hasher.apply(this, arguments);
      return _.has(memo, key) ? memo[key] : (memo[key] = func.apply(this, arguments));
    };
  }; 

It works the same way, except from the fact that it is a little more elegant; if an hasher function it's not provided, it uses _.identity as a key, that is a function that simply returns the value passed as an argument:

_.identity = function(value) { return value; }

Aside from this, cache is now called memo but works the same way.

5
  • Thanks link. Is this identical solution to stackoverflow.com/questions/7497914/… ?
    – user1028880
    Jun 30, 2014 at 10:13
  • Yes, the idea is very similar. The solution from that question includes also a check for the type of the argument passed to memoize (it makes sure it is a function), and a different method of computing the address for the cache (it takes callable.toString().hashCode()).
    – link
    Jun 30, 2014 at 11:28
  • 2
    It using _.identity is not elegant at all; _.identity is unary.
    – user1804599
    Mar 17, 2015 at 8:45
  • I can't get the point that when the cache is created it is localized to the function and should not be available to the outer scope then how it is a cache to the script? How it caches function and recalls afterward if called later called with the same argument?
    – Saqlain
    Jun 13, 2019 at 17:01
  • @Saqlain memoize returns a closure, so it keeps a reference to the outer memo, which will be the same for every invocation.
    – link
    Jun 14, 2019 at 8:00
0
const memorized = (fn) => {
  let cache = {}
  const makeKey = (...args) => {
    return args.map((o) => JSON.stringify(o)).join('_')
  }

  return function (...args) {
    const key = makeKey(args)

    if (cache[key]) {     
      console.log('return from cache')   
      return cache[key]
    } else {
      console.log('calculating')
      const newValue = fn(...args)
      cache[key] = newValue
      return newValue
    }
  }
}
const sum = (a, b, c)=> a + b + c
const square = a => a*a
const sumMemorized = memorized(sum)
const squareMemorized = memorized(square)
sumMemorized(1,2,3)
sumMemorized(1,2,3)
sumMemorized(1,2,3)
sumMemorized(1,2,3)
sumMemorized(1,2,3)
squareMemorized(2)
squareMemorized(3)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.