javascript - How to create a memoize function - Stack Overflow

admin管理员组

文章数量:1197786

I am stumped with this memoize problem. I need to create a function that will check to see if a value has already been calculated for a given argument, return the previous result, or run the calculation and return that value.

I have spent hours on this and while I am new to JS. I cannot get my head around how to do this. I cannot use any built in functions and would really like to understand what I need to do.

Here is what I have so far, which is so wrong it feels like pseudo-code at this point. I have searched existing memoize questions out here but I cannot seem to make any solution work yet. Any help is much appreciated.

  myMemoizeFunc = function(passedFunc) {
  var firstRun = passedFunc;
  function check(passedFunc){
    if(firstRun === undefined){
        return passedFunc;
    }else{return firstRun;}
  }
  };

Sorry, I should have been more clear. Here are my specific requirements: myMemoizeFunc must return a function that will check if the calculation has already been calculated for the given arg and return that val if possible. The passedFunc is a function that holds the result of a calculation. I understand this may seem like a duplicate, but I am marking as not so, as I am having some serious difficulty understanding what I should do here, and need further help than is given in other posts. This is what my thought process is bringing me towards but again, I am way off.

myMemoizeFunc = function(passedFunc) {
var allValues = [];
return function(){
    for(var i = 0; i < myValues.length; i++){
        if(myValues[i] === passedFunc){
            return i;
        }
        else{
            myValues.push(passedFunc);
            return passedFunc;
        }
    }
  }
};

I should not be returning i or passedFunc here, but what else could I do within the if/else while checking for a value? I have been looking at this problem for so long, I am starting to implement code that is ridiculous and need some fresh advice.

I am stumped with this memoize problem. I need to create a function that will check to see if a value has already been calculated for a given argument, return the previous result, or run the calculation and return that value.

I have spent hours on this and while I am new to JS. I cannot get my head around how to do this. I cannot use any built in functions and would really like to understand what I need to do.

Here is what I have so far, which is so wrong it feels like pseudo-code at this point. I have searched existing memoize questions out here but I cannot seem to make any solution work yet. Any help is much appreciated.

  myMemoizeFunc = function(passedFunc) {
  var firstRun = passedFunc;
  function check(passedFunc){
    if(firstRun === undefined){
        return passedFunc;
    }else{return firstRun;}
  }
  };

Sorry, I should have been more clear. Here are my specific requirements: myMemoizeFunc must return a function that will check if the calculation has already been calculated for the given arg and return that val if possible. The passedFunc is a function that holds the result of a calculation. I understand this may seem like a duplicate, but I am marking as not so, as I am having some serious difficulty understanding what I should do here, and need further help than is given in other posts. This is what my thought process is bringing me towards but again, I am way off.

myMemoizeFunc = function(passedFunc) {
var allValues = [];
return function(){
    for(var i = 0; i < myValues.length; i++){
        if(myValues[i] === passedFunc){
            return i;
        }
        else{
            myValues.push(passedFunc);
            return passedFunc;
        }
    }
  }
};

I should not be returning i or passedFunc here, but what else could I do within the if/else while checking for a value? I have been looking at this problem for so long, I am starting to implement code that is ridiculous and need some fresh advice.

• javascript
• underscore.js
• memoization

Share Improve this question Follow edited May 22, 2015 at 2:01 asked May 22, 2015 at 1:22 user4774635user4774635 5

• possible duplicate of How underscore memoize is implemented in javascript – b4hand Commented May 22, 2015 at 1:26
• Create an object and use the value you want to calculate as the key. Check the object to see if the value exists in the object, if it does use it. If not calculate it, store the value, and return it. – epascarello Commented May 22, 2015 at 1:27
• You are missing the "run the calculation step" and also need to devise a method to access "the previous result" so that it can be returned again later. – Bergi Commented May 22, 2015 at 1:46
• @epascarello: Whether an object is needed to store results by argument(s) depends on the arity of the function. OP seems to aim for nullary ones. – Bergi Commented May 22, 2015 at 1:47
• This is just tortured. Because you assign the parameter "passedFunc" from the outer function to the variable firstRun, they both hold a reference to the same object, thus the whole if clause of the inner function makes no sense because ther're the same thing, firstRun === passedFunc. And you never show any actual calculation. I feel your pain. – SeanOlson Commented May 22, 2015 at 1:59

Add a comment  | 

6 Answers 6

Sorted by: Reset to default 17

I think the main trick for this is to make an object that stores arguments that have been passed in before as keys with the result of the function as the value.

For memoizing functions of a single argument, I would implement it like so:

var myMemoizeFunc = function (passedFunc) {
    var cache = {};
    return function (x) {
        if (x in cache) return cache[x];
        return cache[x] = passedFunc(x);
    };
};

Then you could use this to memoize any function that takes a single argument, say for example, a recursive function for calculating factorials:

var factorial = myMemoizeFunc(function(n) {
    if(n < 2) return 1;
    return n * factorial(n-1);
});

Consider this an extension on the answer of Peter Olson.

For a variable number of arguments you could use something like this.

Note: This example is not optimal if you intent to pass complex arguments (arrays, objects, functions). Be sure to read further and not copy/paste blindly.

function memo(fn) {
  const cache = {};

  function get(args) {
    let node = cache;
    for (const arg of args) {
      if (!("next" in node)) node.next = new Map();
      if (!node.next.has(arg)) node.next.set(arg, {});
      node = node.next.get(arg);
    }
    return node;
  }
  
  return function (...args) {
    const cache = get(args);
    if ("item" in cache) return cache.item;
    cache.item = fn(...args);
    return cache.item;
  }
}

This builds the following cache tree structure:

const memoizedFn = memo(fn);
memoizedFn();
memoizedFn(1);
memoizedFn(1, 2);
memoizedFn(2, 1);

cache = {
  item: fn(),
  next: Map{ // <- Map contents depicted as object
    1: {
      item: fn(1),
      next: Map{
        2: { item: fn(1, 2) }
      }
    },
    2: {
      next: Map{
        1: { item: fn(2, 1) }
      }
    }
  }
}

This solution leaks memory when passing complex arguments (arrays, object, functions) that are no longer referenced afterwards.

memoizedFn({ a: 1 })

Because { a: 1 } is not referenced after the memoizedFn call it would normally be garbage collected. However now it can't be because cache still holds a reference. It can only be garbage collected once memoizedFn itself is garbage collected.

I showed the above first because it shows the base concept and demonstrates the cache structure in a somewhat simple form. To clean up cache that would normally be garbage collected we should use a WeakMap instead of a Map for complex objects.

For those unfamiliar with WeakMap, the keys are a "weak" reference. This means that the keys do not count towards active references towards an object. Once an object is no longer referenced (not counting weak references) it will be garbage collected. This will in turn remove the key/value pair from the WeakMap instance.

const memo = (function () {
  const primitives = new Set([
    "undefined",
    "boolean",
    "number",
    "bigint",
    "string",
    "symbol"
  ]);
  
  function typeOf(item) {
    const type = typeof item;
    if (primitives.has(type)) return "primitive";
    return item === null ? "primitive" : "complex";
  }

  const map = {
    "primitive": Map,
    "complex": WeakMap
  };

  return function (fn) {
    const cache = {};

    function get(args) {
      let node = cache;
      for (const arg of args) {
        const type = typeOf(arg);
        if (!(type in node)) node[type] = new map[type];
        if (!node[type].has(arg)) node[type].set(arg, {});
        node = node[type].get(arg);
      }
      return node;
    }

    return function (...args) {
      const cache = get(args);
      if ("item" in cache) return cache.item;
      cache.item = fn(...args);
      return cache.item;
    }
  }
})();


const fib = memo((n) => {
  console.log("fib called with", n);
  if (n == 0) return 0;
  if (n == 1) return 1;
  return fib(n - 1) + fib(n - 2);
});

// heavy operation with complex object
const heavyFn = memo((obj) => {
  console.log("heavyFn called with", obj);
  // heavy operation
  return obj.value * 2;
});

// multiple complex arguments
const map = memo((iterable, mapFn) => {
  console.log("map called with", iterable, mapFn);
  const result = [];
  for (const item of iterable) result.push(mapFn(item));
  return result;
});

console.log("### simple argument demonstration ###");
console.log("fib(3)", "//=>", fib(3));
console.log("fib(6)", "//=>", fib(6));
console.log("fib(5)", "//=>", fib(5));

console.log("### exlanation of when cache is garbage collected ###");
(function () {
  const item = { value: 7 };
  
  // item stays in memo cache until it is garbade collected
  console.log("heavyFn(item)", "//=>", heavyFn(item));
  console.log("heavyFn(item)", "//=>", heavyFn(item));
  
  // Does not use the cached item. Although the object has the same contents
  // it is a different instance, so not considdered the same.
  console.log("heavyFn({ value: 7 })", "//=>", heavyFn({ value: 7 }));
  // { value: 7 } is garbade collected (and removed from the memo cache)
})();
// item is garbade collected (and removed from memo cache) it is no longer in scope

console.log("### multiple complex arguments demonstration ###");
console.log("map([1], n => n * 2)", "//=>", map([1], n => n * 2));
// Does not use cache. Although the array and function have the same contents
// they are new instances, so not considdered the same.
console.log("map([1], n => n * 2)", "//=>", map([1], n => n * 2));

const ns = [1, 2];
const double = n => n * 2;
console.log("map(ns, double)", "//=>", map(ns, double));
// Does use cache, same instances are passed.
console.log("map(ns, double)", "//=>", map(ns, double));
// Does use cache, same instances are passed.
ns.push(3);
console.log("mutated ns", ns);
console.log("map(ns, double)", "//=>", map(ns, double));

The structure stays essentially the same, but depending on the type of the argument it will look in either the primitive: Map{} or complex: WeakMap{} object.

const memoizedFn = memo(fn);
memoizedFn();
memoizedFn(1);
memoizedFn(1, 2);
memoizedFn({ value: 2 }, 1);

cache = {
  item: fn(),
  primitive: Map{
    1: {
      item: fn(1),
      primitive: Map{
        2: { item: fn(1, 2) }
      }
    }
  },
  complex: WeakMap{
    { value: 2 }: { // <- cleared if { value: 2 } is garbage collected
      primitive: Map{
        1: { item: fn({ value: 2 }, 1) }
      }
    }
  }
}

This solution does not memoize any errors thrown. Arguments are considered equal based on Map key equality. If you also need to memoize any errors thrown I hope that this answer gave you the building blocks to do so.

There are a number of memoization libraries available. Doing memoization efficiently is not as straight forward as it seems. I suggest a library be used. Two of the fastest are:

https://github.com/anywhichway/iMemoized

https://github.com/planttheidea/moize

See here for a comprehensive(-ish) list of memoization libraries: https://stackoverflow.com/a/61402805/2441655

This version is correct for any situation (multiple arguments)

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)

const memoize = (func) => {
    const results = {};
    return (...args) => {
        const argsKey = JSON.stringify(args);
        if (!results[argsKey]) {
            results[argsKey] = func(...args);
        }
        return results[argsKey];
    };
};

const clumsysquare = memoize((num) => {
    let result = 0;
    for (let i = 1; i <= num; i++) {
        for (let j = 1; j <= num; j++) {
            result++;
        }
    }
    return result;
});


console.log(clumsysquare(9467));
console.log(clumsysquare(9467));

console.log(clumsysquare(9467)); console.log(clumsysquare(9467));

Importance to use memorization and execution time drastically reduces

本文标签： javascriptHow to create a memoize functionStack Overflow