Lisa Ever Lisa Ever - 1 month ago 8
Javascript Question

Memoize function passes function and returns function JavaScript

I am having multiple problems with this function. It's part of a bonus question for a Data Structures and Algorithms class and I've invested so much time in this one problem, that I'd really like to get it to work and understand what's going on.

There is one main problem, which has caused several little ones...this problem's name is JavaScript. We've never programmed in JavaScript before, but for some reason we have to use it.

The function has to pass tests (this one and fibonacci), which are structured like this:

var fn = (n) => 2 * n
var m_fn = memoize(fn)
expect(m_fn(18)).to.equal(fn(18))


So I have to pass the function I want to memoize as a parameter of the memoize function and the memoize function has to return a function. I am not allowed to do it any other way.

I did all of the reading and researched the memoize function, but all of the implementations take a different approach.

Basically, I understand what I have to do, but I don't quite understand HOW. I know what the memoize function should do, but I don't understand how to adjust the original function using my memoize function. This is what I have so far/what I don't have:

I know it's wrong. But I think I'm missing something major. I am supposed to return a function, but I am returning values...

In the test, it's writen var m_fn = memoize(fn), so the memoize function passes fn, then returns a new function, but in my memoize, I am returning values for fn(n), so I AM doing something wrong...

/**
* Creates a memoized version of the function fn. It is assumed that fn is a referentially transparent
* function.
* @param {function} fn Some referentially transparent function that takes a basic datatype (i.e. number / string)
* @returns {function} A new function that is the memoized version of fn. It never calculates the result of
* a function twice.
*/
memoize: (fn) => { //here we enter the function that we want to memoize
var memory = []; //we need to create an array to hold the previously calculated values, length n (parameter of fn)

if(this.n > memory.length){ //Check to see if this particular value is in the array already.
return memory[this.n]; //How do I access the integer parameter that was passed through fn though? Is this correct?
} else{ // if not, we want to save it and return it
var result = fn(this.n);
memory.push(result);
return result;
}


}

Answer

Indeed, you need to return a function.

Secondly, an array is not the ideal structure for memory, because it takes linear time to find an argument value in it. I would suggest to use a Map for this, which is ideal for such purposes. It has has(), get() and set() methods which run in near-constant time:

function memoize(fn) {
    var memory = new Map();
    return function(arg) {
        if (memory.has(arg)) {
            console.log('using memory');
            return memory.get(arg);
        } else {
            var result = fn(arg);
            memory.set(arg, result);
            return result;
        }
    };
}

var fn = (n) => 2 * n
var m_fn = memoize(fn)

console.log(fn(18));
console.log(m_fn(18));
console.log(m_fn(18)); // outputs also "using memory"

Comments