Could someone give me an example of to use this code

L

lorlarz

Could someone give me an example of to use this code?:

function memoizer(memo, formula) {
var recur = function (n) {
var result = memo[n];
if (typeof result !== 'number') {
result = formula(recur, n);
memo[n] = result;
}
return result;
};
return recur;
};
var factorial = memoizer([1, 1], function (recur, n) {
return n * recur(n -1);
});
var fibonacci = memoizer([0, 1], function (recur, n) {
return recur(n -1) + recur(n -2);
});
 
L

lorlarz

Here (AGAIN) is the code (for which I need a sample (example) of its
use:

(Some of the previous post got posted as quoted material wrongly
last time. HERE is the whole script):

function memoizer(memo, formula) {
var recur = function (n) {
var result = memo[n];
if (typeof result !== 'number') {
result = formula(recur, n);
memo[n] = result;
}
return result;
};
return recur;
};
var factorial = memoizer([1, 1], function (recur, n) {
return n * recur(n -1);
});
var fibonacci = memoizer([0, 1], function (recur, n) {
return recur(n -1) + recur(n -2);
});

(end of script)
 
M

Martin Honnen

lorlarz said:
Here (AGAIN) is the code (for which I need a sample (example) of its
use:
function memoizer(memo, formula) {
var recur = function (n) {
var result = memo[n];
if (typeof result !== 'number') {
result = formula(recur, n);
memo[n] = result;
}
return result;
};
return recur;
};
var factorial = memoizer([1, 1], function (recur, n) {
return n * recur(n -1);
});

You can call that function like this:
var fact5 = factorial(5);
That computes 1 * 2 * 3 * 4 * 5 and stores ("memorizes") the results so
that on the next call of "factorial" with arguments less than 6 no
recursion is needed.
 
S

Scott Sauyet

Here (AGAIN) is the code (for which I need a sample (example) of its
use:

function memoizer(memo, formula) {
    var recur = function (n) {
        var result = memo[n];
        if (typeof result !== 'number') {
            result = formula(recur, n);
            memo[n] = result;
        }
        return result;
    };
    return recur;};
// [ ... ]
var fibonacci = memoizer([0, 1], function (recur, n) {
    return recur(n -1) + recur(n -2);
});

As Martin pointed out, this memoizes the function so that when it's
called again with the same parameter, it just looks up and returns a
stored value; this is useful for any function that takes significant
calculation and might be called often with the same parameter,
including via recursive calls.

There are many different versions out there, but some of them are
simpler to understand than that one. One simple one for functions of
a single parameter is this:

function memoize(f) {
var cache = {};
return function (n) {
return (n in cache)? cache[n] : cache[n] = f(n);
};
}

It can then be used like this:

function fibonacci (x) {
if(x < 2) return 1; else return fibonacci (x-1) + fibonacci
(x-2);
}

fibonacci = memoize(fibonacci)

This should be useful for any single-valued function for which the
distinct inputs have distinct String-valued representations (because
"n in cache" will do a String conversion of "n".)

Cheers,

-- Scott
 
L

lorlarz

lorlarz said:
Here (AGAIN) is the code (for which I need a sample (example) of its
use:
function memoizer(memo, formula) {
    var recur = function (n) {
        var result = memo[n];
        if (typeof result !== 'number') {
            result = formula(recur, n);
            memo[n] = result;
        }
        return result;
    };
    return recur;
};
var factorial = memoizer([1, 1], function (recur, n) {
    return n * recur(n -1);
});

You can call that function like this:
   var fact5 = factorial(5);
That computes 1 * 2 * 3 * 4 * 5 and stores ("memorizes") the results so
that on the next call of "factorial" with arguments less than 6 no
recursion is needed.


I see that it does work and that you can get the result at the end of
each recursion,
but I still do not understand the way n (when factorial(x); is called)
gets to where
it needs to get. Could someone elaborate on the details of how the n
value "travels"
through this routine?
 
L

lorlarz

[snip]
There are many different versions out there, but some of them are
simpler to understand than that one.  One simple one for functions of
a single parameter is this:

    function memoize(f) {
        var cache = {};
        return function (n) {
            return (n in cache)? cache[n] : cache[n] = f(n);
        };
    }

It can then be used like this:

    function fibonacci (x) {
        if(x < 2) return 1; else return fibonacci (x-1) + fibonacci
(x-2);
    }

    fibonacci  = memoize(fibonacci)

This should be useful for any single-valued function for which the
distinct inputs have distinct String-valued representations (because
"n in cache" will do a String conversion of "n".)

Cheers,

  -- Scott- Hide quoted text -

Ecen in your clearer version I have trouble understanding how the
value
gets to n in:

return function (n)
 
S

Scott Sauyet

lorlarz said:
Scott Sauyet wrote:
There are many different versions out there, but some of them are
simpler to understand than that one.  One simple one for functions of
a single parameter is this:
    function memoize(f) {
        var cache = {};
        return function (n) {
            return (n in cache)? cache[n] : cache[n] = f(n);
        };
    }
Ecen in your clearer version I have trouble understanding how the
value gets to n in:

return function (n)

memoize is a function that accepts a function as a parameter and
returns another function.

Remember that functions are first-class items in Javascript. They can
be supplied as parameters, assigned to variables, returned from
functions, etc.

A somewhat more verbose version of the same idea is this:

function memoize(f) {
var cache = {};
function result(n) {
return (n in cache)? cache[n] : cache[n] = f(n);
};
return result;
}

The input parameter is a function, "f". "memoize" returns the
function internally named "result". That function takes a single
parameter, called "n". The only difference in the earlier version is
that instead of naming the returning function, it uses an anonymous
one.

So the "n" gets called when you do this:

var fib = memoize(function fib(n) {
if (n < 2) return 1;
return fib(n-1) + fib(n-2);
});

alert(fib(30));

or if you want to break it down, like this:

function fib(n) {
if (n < 2) return 1;
return fib(n-1) + fib(n-2);
}

fib = memoize(fib);

alert(fib(30));

Does that make sense?

-- Scott
 
S

Scott Sauyet

Stefan said:
Is anybody here actively using memoization for something a little more
relevant to our day-to-day projects?

I've only once used it for DOM-related code. But I've done some
mathematics-heavy work, and it helped a lot. On one occasion, it sped
up a process from the 20-30 second range down to below 100ms.

The DOM bit was a few years back. I had a collection of deeply-nested
lists representing parent-child relationships, and needed to highlight
on click of one node all those nodes of certain degrees of
consanguinity (equivalent, say, to "second-cousin, once removed".) I
generated functions for each degree of relatedness I cared about,
functions accepting a node and returning an array of related nodes,
and then memoized the result of that function. Although I never timed
it, it made for a much snappier interface, as the users regularly
clicked on only a few nodes per visit, but would hit them many times
each.

I do think that it's a rare case to need this for normal DOM work, but
as the ES engines get more powerful, they might become better vehicles
for computation-intensive work, and these techniques might become more
powerful.

-- Scott
 
L

lorlarz

[snip]
memoize is a function that accepts a function as a parameter and
returns another function.

Remember that functions are first-class items in Javascript.  They can
be supplied as parameters, assigned to variables, returned from
functions, etc.

A somewhat more verbose version of the same idea is this:

    function memoize(f) {
        var cache = {};
        function result(n) {
            return (n in cache)? cache[n] : cache[n] = f(n);
        };
        return result;
    }

The input parameter is a function, "f".  "memoize" returns the
function internally named "result".  That function takes a single
parameter, called "n".  The only difference in the earlier version is
that instead of naming the returning function, it uses an anonymous
one.

So the "n" gets called when you do this:

    var fib = memoize(function fib(n) {
        if (n < 2) return 1;
        return fib(n-1) + fib(n-2);
    });

    alert(fib(30));

or if you want to break it down, like this:

    function fib(n) {
        if (n < 2) return 1;
        return fib(n-1) + fib(n-2);
    }

    fib = memoize(fib);

    alert(fib(30));

Does that make sense?


Scott, thanks. That just about makes sense. It is kinda like the
passed-in function is
a local contained function within some same outer function. But THEN
it seems to me
the parameter name (n) would have to be the same name (that is: n) any
other time a parameter is
needed. Above you use n in both the parameter locations YET, in a
previous post you
cited this example: (and one place you use x and the other n and still
it works!!??):

function memoize(f) {
var cache = {};
return function (n) {
return (n in cache)? cache[n] : cache[n] = f(n);
};
}




function fibonacci (x) {
if(x < 2) return 1; else return fibonacci (x-1) + fibonacci
(x-2);
}


fibonacci = memoize(fibonacci);

// AND YET THE FOLLOWING WORKS!!??? when it starts x
// but the other internal function uses n !!!

alert(fibonacci(5));

Obviously my understanding is still not clear (or quite right)
 
S

Scott Sauyet

Scott, thanks.  That just about makes sense.  It is kinda like the
passed-in function is a local contained function within some same
outer function.  But THEN it seems to me the parameter name (n)
would have to be the same name (that is: n) any other time a
parameter is needed.  Above you use n in both the parameter
locations YET, in a previous post you cited this example: (and
one place you use x and the other n and still it works!!??):
[ ... ]

Obviously my understanding is still not clear (or quite right)

Javascript does not have named parameters; they are interpreted by
position. It simply doesn't matter what you call them.

For instance, if you have this:

function addOne(x) {
return x + 1;
}

function nthOdd(n) {
var temp = 2 * n;
return addOne(temp);
}

alert(nthOdd(7));

it doesn't matter that the outer function, "nthOdd", calls the inner
one, "addOne" using a parameter named "temp". When the inner one is
processed, the value of the first parameter is assigned to "x".

This may or may not be helpful, but you could think of the value of
memoize(fibonacci) to be the following function:

function(n) {
return (n in cache)
? cache[n]
: cache[n] = (function fibonacci (x) {
if(x < 2) return 1;
return fibonacci (x-1) + fibonacci(x-2);
})(n);
};

where cache has been defined in such a way as to be available when the
function is called. The following syntax means that the internal
function should have the value stored in "n" assigned to its parameter
"x":

(function internal(x) {
// return result of calculations involving x
})(n); // with the value of "n" assigned to "x"

Cheers,

-- Scott
 
L

lorlarz

[snip]

    function(n) {
        return (n in cache)
            ? cache[n]
            : cache[n] = (function fibonacci (x) {
                if(x < 2) return 1;
                return fibonacci (x-1) + fibonacci(x-2);
             })(n);
    };

where cache has been defined in such a way as to be available when the
function is called.  The following syntax means that the internal
function should have the value stored in "n" assigned to its parameter
"x":

    (function internal(x) {
        // return result of calculations involving x
    })(n);  // with the value of "n" assigned to "x"

Cheers,

  -- Scott

I can make sense of it only by looking at it 2 ways. (1) the
way you describe it above -- and I am taking that quite a lot on
faith, since the n parameter is being passed not only to the
function it was sent to but by to the anonymous function which
is outside where the passed function is actually used.

(2) it semms fine to me that the function along with its parameter,
however named
is plopped in IN FULL as sent (with filled parameter) to the spot
where it is used (fully appreciating the name of the parameter
does not matter).

To reiterate:
Really, the only strange part of the situation is that the
outer anonymous function being returned using
the function that was sent has access to the parameter,
whatever it is called, and that is what you claim -- which
I again must take on faith just because it is what
you say with your code translation happens.
But I hate to take things
on faith and how that happens is still not clear.

So, it is still weird to me that in the following, the return function
(n) { ...}
the outer anon function is given THAT param. It is not strange that
the f(x) in the inner function can get f(x):

function memoize(f) {
var cache = {};
return function (n) {
return (n in cache)? cache[n] : cache[n] = f(n);
};
}


function fibonacci (x) {
if(x < 2) return 1; else return fibonacci (x-1) + fibonacci
(x-2);
}


fibonacci = memoize(fibonacci);



alert(fibonacci(5));
 
L

lorlarz

Scott wrote:

[snip]



function(n) {
return (n in cache)
? cache[n]
: cache[n] = (function fibonacci (x) {
if(x < 2) return 1;
return fibonacci (x-1) + fibonacci(x-2);
})(n);
};
where cache has been defined in such a way as to be available when the
function is called. The following syntax means that the internal
function should have the value stored in "n" assigned to its parameter
"x":

(function internal(x) {
// return result of calculations involving x
})(n); // with the value of "n" assigned to "x"



-- Scott



I can make sense of it only by looking at it 2 ways. (1) the
way you describe it above -- and I am taking that quite a lot on
faith, since the n parameter is being passed not only to the
function it was sent to but by to the anonymous function which
is outside where the passed function is actually used.

(2) it semms fine to me that the function along with its parameter,
however named
is plopped in IN FULL as sent (with filled parameter) to the spot
where it is used (fully appreciating the name of the parameter
does not matter).


To reiterate:
Really, the only strange part of the situation is that the
outer anonymous function being returned using
the function that was sent has access to the parameter,
whatever it is called, and that is what you claim -- which
I again must take on faith just because it is what
you say with your code translation happens.
But I hate to take things
on faith and how that happens is still not clear.


So, it is still weird to me that in the following, the return
function
(n) { ...}
the outer anon function is given THAT param. It is not strange that
the f(n) in the inner function can get f(x):


function memoize(f) {
var cache = {};
return function (n) {
return (n in cache)? cache[n] : cache[n] = f(n);
};
}


function fibonacci (x) {
if(x < 2) return 1; else return fibonacci (x-1) + fibonacci
(x-2);
}


fibonacci = memoize(fibonacci);


alert(fibonacci(5));
 
S

Scott Sauyet

lorlarz said:
Really, the only strange part of the situation is that the
outer anonymous function being returned  using
the function that was sent has access to the parameter,
whatever it is called, and that is what you claim -- which
I again must take on faith just because it is what
you say with your code translation happens.
But I hate to take things
on faith and how that happens is still not clear.

I think I'm getting confused by your confusion. :)

Perhaps a simpler function-returning-function would help:

function addN(n) {
return function(x) {
return n + x;
};
}

var addSeven = addN(7);
// equivalent to function(x) {return 7 + x;}

alert(addSeven(5)); // alerts 12;

If you listened to the Crockford talk you discussed in another thread,
you'll know that there was a fair bit about closures. The fact that
an invocation of addSeven(5) has access to the value 5 isn't
concerning you, right? That's just the parameter supplied. The fact
that it has access to the value 7 might be a little more surprising.
To understand that more fully, you might want to look at the FAQ notes
on closures [1].

Cheers,

-- Scott
____________________
[1] http://jibbering.com/faq/faq_notes/closures.html
 
L

lorlarz

[snip]
I think I'm getting confused by your confusion. :)

Perhaps a simpler function-returning-function would help:

function addN(n) {
return function(x) {
return n + x;
};
}

var addSeven = addN(7);
// equivalent to function(x) {return 7 + x;}

alert(addSeven(5)); // alerts 12;

If you listened to the Crockford talk you discussed in another thread,
you'll know that there was a fair bit about closures. The fact that
an invocation of addSeven(5) has access to the value 5 isn't
concerning you, right? That's just the parameter supplied. The fact
that it has access to the value 7 might be a little more surprising.
To understand that more fully, you might want to look at the FAQ notes
on closures [1].

Cheers,

-- Scott
____________________
[1]http://jibbering.com/faq/faq_notes/closures.html

I did some experiments:

As long as there is a function returned where a parameter is used in
any function,
it knows the parameter passed to
memoize IN the function passed and uses it: Here are some
experiments:




function memoize(f) {
var cache = {};
//alert(n); // <- n is not known here
return function(n) {alert(n);} // this works even though
// passed in function not used

}



function fibonacci (x) {

}


fibonacci = memoize(fibonacci)

fibonacci(5);
 
L

lorlarz

Perhaps a simpler function-returning-function would help:

    function addN(n) {
        return function(x) {
            return n + x;
        };
    }

    var addSeven = addN(7);
    // equivalent to function(x) {return 7 + x;}

    alert(addSeven(5)); // alerts 12;

If you listened to the Crockford talk you discussed in another thread,
you'll know that there was a fair bit about closures.  The fact that
an invocation of addSeven(5) has access to the value 5 isn't
concerning you, right?  That's just the parameter supplied.  The fact
that it has access to the value 7 might be a little more surprising.
To understand that more fully, you might want to look at the FAQ notes
on closures [1].

Cheers,

  -- Scott
____________________
[1]http://jibbering.com/faq/faq_notes/closures.html

I got it now. Remembering the function passed in the more complex
example, is simply like remembering the 7 in your simple example.

I usually understand closures. Somehow I got confused when a function
was involved. At this moment, I too, do not even understand my
confusion.

Perhaps, the fact that recursion was also involved in the somewhat
more
complex example (as well as a closure) freaked me out.

Thanks for your help Scott. You really did help. Regards, Larz
 
L

lorlarz

[snip]
I got it now.  Remembering the function passed in the more complex
example, is simply like remembering the 7 in your simple example.

I usually understand closures.  Somehow I got confused when a function
was involved.  At this moment, I too, do not even understand my
confusion.

Perhaps, the fact that recursion was also involved in the somewhat
more
complex example (as well as a closure) freaked me out.

Thanks for your help Scott.  You really did help.  Regards, Larz- Hide quoted text -

- Show quoted text -

As a P.S. to my own reply, let me state that what is really neat
about the routine other than closure and other than recursion
is the ability to mutate functions or add onto them when you
pass in a function and return that function (mutated in any way you
want or not) _and_/_or_ with whatever else you want to return in the
return statement that can also use whatever the numbers of
parameter(s)
you have set up to be sent in when you finally use that which is
returned.

Indeed all that provides for exciting possibilities. Perhaps my over
excitement about all this before nnt-clearly-seen feature resulted in
the confusion. It is a lot more than setting a function for
systematic
reuse with modification (and thus is good fdr many situations other
than
recursion).

Thanks again, Scott, and thanks to Stefan for his kindly submitted
perspectives and useful inputs.
 
D

Dr J R Stockton

In comp.lang.javascript message <[email protected]
or-online.net>, Fri, 26 Feb 2010 17:37:19, Martin Honnen
You can call that function like this:
var fact5 = factorial(5);
That computes 1 * 2 * 3 * 4 * 5 and stores ("memorizes") the results so
that on the next call of "factorial" with arguments less than 6 no
recursion is needed.

Examples of cacheing, of varying potency, can be seen in
<URL:http://www.merlyn.demon.co.uk/js-misc0.htm#Cash>. That may partly
answer Stefan Weiss.

If it is known that the result can never be equivalent to false, the
test-or-call can be somewhat simplified.

As coded, the OP's memoizer only works if the answers are numbers. If
the rest were against "undefined" the restriction would be effectively
removed.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top