Memoization javascript

Question

I'm studying JavaScript from the book JavaScript: The Good Parts, in the memoization section there is an example about using memoize technique to do Fibonacci problem

We create a general function call memoizer, it takes an memo array and the fundamental function, returns a shell function that manages the memo and calls fundamental function

 var memoizer = function(memo, fundamental) {
  var shell = function(n) {
    var result = memo[n];
    if (typeof result !== 'number') {
      result = fundamental(shell, n);
      memo[n] = result;
    }
    return result;
  };
  return shell;
};

And then create fibonacci like this:

var fibonacci = memoizer([0, 1], function(shell, n) {
    return shell(n-1) + shell(n-2);
});

If I run fibonacci(10), the result will be displayed exactly.

But the thing that makes me confused is the n parameter shell function in memoizer function. I know that it is the value that we want to compute. But where is it come from? How can I call fibonacci(10), for example, can pass the value 10 to n? And what is exactly the var fibonacci? Is it a function or points to a function object as memoizer?

Thanks for any help!

You mean `fibonacci` is the function `shell` which is returned by `memoizer`? So the value we pass to `fibonacci` is also passed to n in `shell` function? — xHOIx, Dec 04 '17 at 10:14
The argument to `fibonacci`, or the argument to `shell`, is passed through to the `fundamental` callback — Bergi, Dec 04 '17 at 10:53
Btw: the naïve implementation returns for fib(100) 354224848179262000000, although the correct value would be 354224848179261915075. Floating point numbers are quite sub-optimal to calculate Fibonacci numbers. The benefit of memoization, to be able to calculate really big numbers, is obsolete, if the number type is not able to handle even the small values. — ceving, Dec 04 '17 at 12:06

moon · Answer 1 · 2017-12-04T11:14:53.643

0

So, to understand this fully, you need to understand things below as fundamental pieces.

Closure How do JavaScript closures work?
Scope What is the scope of variables in JavaScript?
First class object What is meant by 'first class object'?

So, now look at the code.
var memoizer is assigned as a function that returns an another function inside.

var memoizer = function(memo, fundamental) {
  var shell = function(n) {
    ... do some works ...
  };
  return shell;
};

Can you see it? var shell is returned at the end of the line in memoizer

And whatever the inner logic is in memoizer, the result of it is assigned to var fibonacci

var fibonacci = memoizer([0, 1], function(shell, n) {
    return shell(n-1) + shell(n-2);
});

So, it means fibonacci equals the result of memoizer (Since we excuted it), and the result of memoizer equals shell function. If you read those links given to you by me well, you can understand what is going on behind the scenes.

By the way, the code you've given isn't the best way. Because anyway closure makes an activated object alive that isn't necessary.

This code below is an another way of making fibonacci, this isn't the absolute best way, however, I recommend you to compare this code with your code, and figure the differences out.

var result = [];
result[0] = 1;
result[1] = 1;

function fibonacci(n){
    var i;
    
    for(i = 2; i < n; i++){
      if(!result[i]){
        result[i] = result[i-1] + result[i-2];
      }
    }
    return result[i-1];
}

console.log(fibonacci(10));

edited Dec 04 '17 at 11:14

answered Dec 04 '17 at 10:54

moon

640
6
14

"*anyway closure makes an activated object alive that isn't necessary.*" - what? – Bergi Dec 04 '17 at 10:57
When you use a closure, an outer activated object has to be alive because the inner still refers to it – moon Dec 04 '17 at 11:03
Sure, but what is the problem with that? It's pretty much necessary to close over the memoisation map to get the benefits of memoisation. – Bergi Dec 04 '17 at 11:06
@Bergi Oh, I meant, in that case, there's another also good way to make that logic with not using a closure. I've quite expanded my thought. I've wanted to tell the person asking that using a closure without a clear purpose would cause memory leak. Like the code I've offered, it's also using memoization without a closure. So if you should make that logic by using memoization anyway, shouldn't it be better to avoid a closure – moon Dec 04 '17 at 11:10
@Bergi And I also know my code is NOT the best, so I also want to know about your suggestion, please. Is there something I've missed? If you give me your own advice, it would be a huge favor to me :) – moon Dec 04 '17 at 11:11
No, your code does not do memoisation. If I call your `fibonacci` multiple times, it needs to compute a complete new `results` array every time. – Bergi Dec 04 '17 at 11:12
@Bergi Oh, right. Thank you. I've editted my code. What about that? What if the `result` object is set by a global variable. – moon Dec 04 '17 at 11:15
1

@Bergi Well, calling `result` in that code is also kind of a closure :( Yeah, then maybe the code that is from the person who asked would be better – moon Dec 04 '17 at 11:17
@Bergi But anyway, thank you. I could also have a thought of my code and knowledge again. Glad to discuss on stackoverflow. It's how this website is supposed to be – moon Dec 04 '17 at 11:18
Reading all this thread to me was not still able to explain to others what memoization means. It's a quite advance programming concept( in term that is not the one study at the beginning ), after reading this resulted much easier to explain to somonelse what the concept is about and how to implement it https://stackoverflow.com/questions/6184869/what-is-the-difference-between-memoization-and-dynamic-programming – Carmine Tambascia Nov 12 '19 at 12:36

Memoization javascript

1 Answers1