Could someone give me an example of to use this code

Discussion in 'Javascript' started by lorlarz, Feb 26, 2010.

  1. lorlarz

    lorlarz Guest

    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);
    });
     
    lorlarz, Feb 26, 2010
    #1
    1. Advertisements

  2. lorlarz

    lorlarz Guest

    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)
     
    lorlarz, Feb 26, 2010
    #2
    1. Advertisements

  3. 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.
     
    Martin Honnen, Feb 26, 2010
    #3
  4. lorlarz

    Scott Sauyet Guest

    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
     
    Scott Sauyet, Feb 26, 2010
    #4
  5. lorlarz

    lorlarz Guest


    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?
     
    lorlarz, Feb 26, 2010
    #5
  6. lorlarz

    lorlarz Guest

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

    return function (n)
     
    lorlarz, Feb 26, 2010
    #6
  7. lorlarz

    Scott Sauyet Guest

    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
     
    Scott Sauyet, Feb 26, 2010
    #7
  8. lorlarz

    Scott Sauyet Guest

    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
     
    Scott Sauyet, Feb 26, 2010
    #8
  9. lorlarz

    lorlarz Guest

    [snip]

    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)
     
    lorlarz, Feb 26, 2010
    #9
  10. lorlarz

    Scott Sauyet Guest

    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
     
    Scott Sauyet, Feb 26, 2010
    #10
  11. lorlarz

    lorlarz Guest

    [snip]

    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));
     
    lorlarz, Feb 26, 2010
    #11
  12. lorlarz

    lorlarz Guest

    Scott wrote:

    [snip]





    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));
     
    lorlarz, Feb 26, 2010
    #12
  13. lorlarz

    Scott Sauyet Guest

    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
     
    Scott Sauyet, Feb 26, 2010
    #13
  14. lorlarz

    lorlarz Guest

    [snip]
    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);
     
    lorlarz, Feb 26, 2010
    #14
  15. lorlarz

    lorlarz Guest

    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
     
    lorlarz, Feb 26, 2010
    #15
  16. lorlarz

    lorlarz Guest

    [snip]
    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.
     
    lorlarz, Feb 27, 2010
    #16
  17. In comp.lang.javascript message <4b87f8c3$0$6720$
    or-online.net>, Fri, 26 Feb 2010 17:37:19, Martin Honnen
    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.
     
    Dr J R Stockton, Feb 28, 2010
    #17
    1. Advertisements

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 (here). After that, you can post your question and our members will help you out.