CODEWITHSUNDEEP
javascriptdictionaryecmascript-6hashtablememoization
John Abraham
John Abraham

Reputation: 18801

Can a memoize function use a ES6 Map vs a hashtable?

Preface: Trying to learn ES6 Maps through converting a simple memoize that leverages a hash table instead.

Question:

Can the starting Object be replaced with a new Map(), if so, how? And are there any advantages? if not, why?

Description:

Here's a memoize that takes function (add) and a starting object({}). On call of the memoized add (mAdd) the parameters are spread. Finally, the hash index is tested/sets and value is returned.

LINK TO CODE

const memo = (fn, hash) => (...a) => {
  return hash[a] === void 0 ?  hash[a] = fn(...a) : `${hash[a]} memo`;
};

const add = (x, y) =>  x + y;

const mAdd = memo(add, {});


console.log(mAdd(2,2));
console.log(mAdd(2,2));

Not working with maps:

const memo = (fn, map) => (...a) => {
  return map.get(a) === void 0 ?  map.set(a, fn(...a)) : `${map.get(a)} memo`;
};

const add = (x, y) =>  x + y;

const mAdd = memo(add, new Map());


console.log(mAdd(2,2));
console.log(mAdd(2,2));

Upvotes: 4

Views: 2323

Answers (2)

Ara Yeressian
Ara Yeressian

Reputation: 4045

The problem is Map uses reference of an object to identify as a key (if the provided key is an object and not a primitive type). In this case a variable is an array and even if it has the same values on each call but the reference of that variable is not the same thus Map understands it as a new key. Have a look at bottom code.

const test = new Map();
const a = ['bla'];
test.set(a, 'b');
console.log(test.get(a));
const f = ['bla'];
console.log(test.get(f));

One workaround to this issue is to stringify the a variable.

const memo = (fn, hash) => (...a) => {
  const key = JSON.stringify(a);
  if (hash.has(key)) {
    return `${hash.get(key)} memo`;        
  }
  const val = fn(...a);
  hash.set(key, val);
  return val;
};

const add = (x, y) =>  x + y;

const mAdd = memo(add, new Map());


console.log(mAdd(2,2));
console.log(mAdd(2,2));

Note: your code is not readable at all. So I had to edit it a bit to make it more understandable.

Upvotes: 0

Me.Name
Me.Name

Reputation: 12544

The main problem is that the parameters do not represent the same object. Their contents do, which is why stringifying would work.

Using an object as a hash, also performs a kind of stringify: a property 2,2 is created. (As a side note: this is not full proof, because the contents are flattened. Parameters [1,[2,3]] and [1,2,3] would both create the property [1,2,3] )

However since the Map is actually smarter in a way, the object itself is used as a key and for each call a new object is created for the parameters.

Calling with the same parameters would work, but of course that would make the function less useful:

var pars = [2,2];
console.log(mAdd(pars));
console.log(mAdd(pars));

(the method signature would have to be changed to const memo = (fn, map) => (a) => { for the above to work. Also note that Map.set returns the map object itself and not the value that is being set).

The easiest implementation is to stringify the key. Safest is JSON.stringify to handle all situations, but if you're relatively sure of the contents, you could do something like join instead: 

const memo = (fn, map) => (...a) => {
    const key = a.join(',');
  if(map.has(key))
        return `${map.get(key)} memo`;
    let res = fn(...a);
  map.set(key, res );
  return res;
};

Creating the key can be done several ways. stringify is possible, perhaps even const key = uneval(a); Some sort of hash integer could be created based on length and contents, but its reliability depends on the possible contents. e.g. if it is known that values never exceed 100 and the number of parameters is not overly long, a helper as const createKey = ([a1,...a]) => a.length ? a1 + 100 * createKey(a) : a1; can be called with const key =createKey(a);

Of course for the example directly adding would be always faster than the key creation and key lookup, but for general purposes the method for creating the key is the defining factor.

I realize I'm probably not saying anything new in all of this, but the bottom line is that the passed parameters do not represent the same object. That said, I'd like to suggest another option: create a branched map. The base map containing child-maps (with the first parameter as key) to either the results (with the second parameter as key) or subsequent maps to second elements.

edit An example of said branching (a single map can be used for different functions to reduce the memory footprint):

const memoMap = new Map(); //use a general map for branches for all memoized functions, because result is stored in the child function as the key

const memo = (fn) => (...a) => {
  let key, r = a, map = memoMap;
  while(r.length){
      [key,...r] = r;      
      if(map.has(key))
      	map = map.get(key);
      else
      	map.set(key, map = new Map());
  }
  let res = map.get(fn); //get result for this specific function
  if(res===undefined)
  	map.set(fn, res = fn(...a));
 	else return `${res} memo`; //<-- line for testing purposes
  return res;
};


const add = (x, y) =>  x + y,
  subtr = (x,y) => x - y,
  mAdd = memo(add);

console.log(mAdd(2,2));
console.log(mAdd(2,2));
console.log(memo(subtr)(2,2));
console.log(memo(subtr)(2,2));

Upvotes: 3

Related Questions