Memoize function incorrectly caching different arguments-CodePudding

I'm trying to write a memoize function that will differentiate between arguments. Specifically, if numbers are given versus an array of the same numbers. Right now, it doesn't matter if I enter (1,2) vs ([1,2]) vs ("1", 2). It will return the cache version for the others after the function is called on one of the other 1,2 options. Maybe it has something to do with the in operator for the if statement?

var memoize = function(func) {
  var cache = {};
  return function(...args) {
    if (args.toString() in cache) {
      console.log(args.toString())
      console.log('cached');
      return cache[args.toString()]
    }
    var result = func(...args);
    cache[args.toString()] = result;
      return result;
  }
}

var add = function(a, b) {
  return a;
};



var memoAdd = memoize(add);
console.log(memoAdd);
console.log(memoAdd([1,2]));
console.log(memoAdd(1,2));

CodePudding user response：

args.toString is a very loose and ineffective test. It won't consider the types of the arguments and can easily blend arguments together. You'll need another approach - perhaps by using JSON.stringify on the args array, which will produce a unique string for each different type of arguments used.

const memoize = (func) => {
  const cache = {};
  return (...args) => {
    const argsKey = JSON.stringify(args);
    if (argsKey in cache) {
      console.log('cached');
    } else {
      cache[argsKey] = func(...args);
    }
    return cache[argsKey];
  };
};


const add = function(a, b) {
  return a;
};
const memoAdd = memoize(add);
console.log(memoAdd([1,2]));
console.log(memoAdd(1,2));
console.log(memoAdd(1,2));

If you want to compare the arguments by identity instead, it'll get a lot more complicated. One possibility is to use nested Maps to represent the arguments passed in so far.

const memoize = (func) => {
  const cache = new Map();
  const resultKey = {};
  return (...args) => {
    const possibleResult = args.reduce((a, arg) => a?.get(arg), cache);
    if (possibleResult?.has(resultKey)) {
      console.log('cached');
      return possibleResult.get(resultKey);
    }
    const result = func(...args);
    const innerMap = args.reduce((a, arg) => {
      if (!a.has(arg)) {
        a.set(arg, new Map());
      }
      return a.get(arg);
    }, cache);
    innerMap.set(resultKey, result);
    return result;
  };
};


const add = function(a, b) {
  return a;
};
const memoAdd = memoize(add);
console.log(memoAdd([1,2]));
console.log(memoAdd(1,2));
console.log(memoAdd(1,2));
const obj = {};
console.log(memoAdd(obj));
console.log(memoAdd(obj));

CodePudding user response：

This will store each argument array in cache (and value of course). Then upon invoking function will search for a match of the entire args array. Should work for all kind of parameters.

const memoize = (func) => {
  const cache = []; // array of objects of {args,value}
  
  return (...args) => {
    for (var i = 0; i < cache.length; i  ) {
      var { argsStored, value } = cache[i];
      if (array_compare(argsStored, args)) {
        console.log('cached')
        return value;
      }
    }
    value = func(...args);
    cache.push({
      argsStored: args,
      value: value
    })
    return value;
  };
};

function array_compare(array1, array2) {
  return array1.length === array2.length && array1.every(function(value, index) {
    return value === array2[index]
  })
}

const add = function(a, b) {
  return a;
};
const memoAdd = memoize(add);
console.log(memoAdd([1, 2]));
console.log(memoAdd(1, 2));
console.log(memoAdd(1, 2));

var x = {}
x.prop = 12;
x.self = x;

console.log(memoAdd(x, 2));
console.log(memoAdd(x, 2));
console.log(memoAdd(x, 3));