Never call the same function twice (with memoization)

So I've just discovered this interesting little concept of memoization.

I've started reading the article about it and stopped as soon as I caught the tail of the idea.

Then I decided to figure out the simple solution in my own and in the way I understand it.

If you've never hear of it, memoization is the process of storing the results of function execution, so you can pull it from a little (or not so) cache next time you run that function with the same arguments.

In reality this can be useful for a high resources consuming function. It comes with cost of using extra space as a cache. But it can improve the speed of your code and the experience of the users who use it.

I've played with JS code a bit and came with this solution:

const memoize = fn => {
  const cache = {}
  return (...args) => {
    const fnKey = `${fn.name}(${args})`;
    if(!cache[fnKey]) {
      cache[fnKey] = fn(...args);
    }

    return cache[fnKey]
  };
}

Then you can run it like that:

function _add(x, y) {
  console.log("function runs", x, y);
  return x + y;
}

const add = memoize(_add)

add(42, 69)
add(10, 15)
add(10, 15)

That leads to the execution of function twice (#1 and #2 'add' calls). Third 'add' call will use cache as it's the same as #2 call.

'function runs' 42 69
'function runs' 10 15

You can see that 'function runs' 10 15 is only called once. This is because the second time we call it, the cache is being used.

Now let's quickly break down what's going on here.

In this example we utilize closure mechanism to store the cache.

const memoize = fn => {
  const cache = {}
  return () => {

  };
}

This allows us to throw the "fn" argument, which is the king of the party as this is exactly the function we want to operate with, down the scopes and "listen" to each of its execution.

I really have written it in the most simplistic, naive way. So we are going to use function name with arguments as keys of the cache, and the results of its execution as values.

That means, that executing:

add(2, 2)

Results in

// Our cache
{
  'add(2, 2)': 4
}

Cache value.

I know that this is possibly not exactly how it should be done "the right way". But the idea of this exercise and the article isn't about the well tested safe and edge cases free solution.

It's about the learning and simple implementation. About the concept. So I'm not focusing on details of implementation right now.

Now, we first figure out the key for the function call:

const memoize = fn => {
  const cache = {}
  return (...args) => {
    const fnKey = `${fn.name}(${args})`;
  };
}

We will use it to store results of the function execution in the cache.

Then we check if this key (fnKey) already exists. If not, we set the key with its value as a result of the passed function execution.

In the end we always return the result from the cache. So really the execution of the function passed to memoize method always ends in the closure (in the "cache" object).

We only operate with this object now:

const memoize = fn => {
  const cache = {}
  return (...args) => {
    const fnKey = `${fn.name}(${args})`;
    if(!cache[fnKey]) {
      cache[fnKey] = fn(...args);
    }

    return cache[fnKey]
  };
}

And that's it.

Now I'm gonna go and look how it should be done "properly". But if you find this interesting, let me know. If something is unclear or wrong with this approach (for your taste), just drop the comment and let's talk about it.

Thanks, see you!

The above is the detailed content of Never call the same function twice (with memoization). For more information, please follow other related articles on the PHP Chinese website!