javascriptunderscore.jsmemoization

How to create a memoize function


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.


Solution

  • 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);
    });