Looping through variable number of arrays variable times?

Discussion in 'Javascript' started by Mike P, Oct 22, 2005.

  1. Mike P

    Mike P Guest

    I will be passing my function a two dimensional array of varying length.
    Within that array is one data point, and the number of times it should loop
    through.

    So, for example, I might pass this to the function:

    example[0] = new Array("A",2);
    example[1] = new Array("Q",4);
    function loopIt(example);

    The function will then do the following:

    function loopIt(example) {
    for (x1 = 0; x1 < example[0][1]; x1++) {
    for (x2 = 0; x2 < example[1][1]; x2++) {
    calculateArray = new Array(example.length);
    calculateArray[0] = new Array(example[0][0],x1);
    calculateArray[1] = new Array(example[1][0],x2);
    calculate(calculateArray);
    }
    }
    }

    But loopIt() doesn't know what example.length will be. Here I showed
    example.length = 2. But if example.length = 41, this function wouldn't
    work. How can I create a loop like this when example.length will vary?

    Thanks!

    Mike
     
    Mike P, Oct 22, 2005
    #1
    1. Advertising

  2. Mike P

    VK Guest

    Mike P wrote:
    > example[0] = new Array("A",2);
    > example[1] = new Array("Q",4);
    > function loopIt(example);
    >
    > The function will then do the following:
    >
    > function loopIt(example) {
    > for (x1 = 0; x1 < example[0][1]; x1++) {
    > for (x2 = 0; x2 < example[1][1]; x2++) {
    > calculateArray = new Array(example.length);
    > calculateArray[0] = new Array(example[0][0],x1);
    > calculateArray[1] = new Array(example[1][0],x2);
    > calculate(calculateArray);
    > }
    > }
    > }
    >
    > But loopIt() doesn't know what example.length will be. Here I showed
    > example.length = 2. But if example.length = 41, this function wouldn't
    > work. How can I create a loop like this when example.length will vary?


    That means that your array elements are going by pairs: example[1]
    gives you the value for external loop, example[i+1][1] gives you the
    value for internal value. So there is no way your array may contain an
    odd amount of elements. Is it correct?
     
    VK, Oct 22, 2005
    #2
    1. Advertising

  3. Mike P

    Mike P Guest

    "VK" <> wrote in message
    news:...

    > That means that your array elements are going by pairs: example[1]
    > gives you the value for external loop, example[i+1][1] gives you the
    > value for internal value. So there is no way your array may contain an
    > odd amount of elements. Is it correct?


    With the code sample, the "example" array can contain 1 to 41 elements (even
    or odd), but each array within it will be 2 long.

    So:
    example.length = 0 to 41 elements, and any integer inbetween (even or odd)
    but example[x].length will always = 2 where
    example[x][0] will always contain a string and
    example[x][1] will contain an integer between 0 and 8

    If I were to code this a long and ugly way, I could create a switch based on
    example.length like this:

    function loopIt(example) {

    switch(example.length) {
    case 1:
    for (x1 = 0; x1 < example[0][1]; x1++) {
    calculateArray = new Array(example.length);
    calculateArray[0] = new Array(example[0][0],x1);
    calculate(calculateArray);
    }
    }
    break;
    case 2:
    for (x1 = 0; x1 < example[0][1]; x1++) {
    for (x2 = 0; x2 < example[1][1]; x2++) {
    calculateArray = new Array(example.length);
    calculateArray[0] = new Array(example[0][0],x1);
    calculateArray[1] = new Array(example[1][0],x2);
    calculate(calculateArray);
    }
    }
    }
    break;
    case 3:
    for (x1 = 0; x1 < example[0][1]; x1++) {
    for (x2 = 0; x2 < example[1][1]; x2++) {
    for (x3 = 0; x3 < example[2][1]; x3++) {
    calculateArray = new Array(example.length);
    calculateArray[0] = new Array(example[0][0],x1);
    calculateArray[1] = new Array(example[1][0],x2);
    calculateArray[2] = new Array(example[2][0],x3);
    calculate(calculateArray);
    }
    }
    }
    break;
    }
    }

    So on, and so forth up to case 41, but that seems excessively inefficient.
    I'm hoping there's a cleaner way to accomplish this.
    do you follow?

    I imagine there's some way to do this with a recursive array or dynamically
    creating the function (ala, new Function)... I just don't really understand
    how to go about it.

    Thanks for your help on this!

    Mike
     
    Mike P, Oct 22, 2005
    #3
  4. Mike P

    VK Guest

    > I imagine there's some way to do this with a recursive array or dynamically
    > creating the function (ala, new Function)... I just don't really understand
    > how to go about it.


    Well, using runtime generated function:

    <html>
    <head>
    <title>Test</title>
    <meta http-equiv="Content-Type" content="text/html;
    charset=iso-8859-1">
    <script type="text/javascript">
    var example = new Array();
    example[0] = new Array('Q',2);
    example[1] = new Array('A',4);
    example[2] = new Array('B',3);

    function test() {
    var fun = null;
    var funOpen = '';
    var funBody = '';
    var funEnd = '';
    var x = '';
    var space = '';
    var len = example.length;

    for (i=0; i<len; i++) {
    x = 'x'+(i+1);
    funOpen+= space+'for ('+x+'=0; '+x+'<arr['+i+'][1]; '+x+'++) {\n';
    funEnd += '}';
    space+= ' ';
    }

    funBody+= space+'calculateArray = new Array(arr.length);\n';
    for (i=0; i<len; i++) {
    x = 'x'+(i+1);
    funBody+= space+'calculateArray['+i+'] = new
    Array(arr['+i+'][0],'+x+');\n';
    }
    funBody+= space+'calculate(calculateArray);\n';
    fun = new Function('arr',funOpen.concat(funBody,funEnd));
    fun(example);
    }

    function calculate(foo) {
    alert(foo);
    }
    </script>
    </head>

    <body bgcolor="#FFFFFF" onload="test()">

    </body>
    </html>

    I would not say that it's any less ugly than 41 case, but definitely
    shorter. :)
    I guess any math prof would kill me for the above. The total amount of
    loops is factorial of [1] values in your array. It's a strong hint
    that the problem could be solved in some nice and profoundly academical
    way using recursions. But it requires good matrix math knowledge more
    than any JavaScript skills. The last of fine by me, the first is
    floating miserably :-(
    It works any way...
     
    VK, Oct 22, 2005
    #4
  5. Mike P

    Mike P Guest

    Wow... very cool! You rule!

    I'm going to have to study that a bit to figure out how you did it.

    Thanks again!

    Mike

    "VK" <> wrote in message
    news:...
    >> I imagine there's some way to do this with a recursive array or
    >> dynamically
    >> creating the function (ala, new Function)... I just don't really
    >> understand
    >> how to go about it.

    >
    > Well, using runtime generated function:
    >
    > <html>
    > <head>
    > <title>Test</title>
    > <meta http-equiv="Content-Type" content="text/html;
    > charset=iso-8859-1">
    > <script type="text/javascript">
    > var example = new Array();
    > example[0] = new Array('Q',2);
    > example[1] = new Array('A',4);
    > example[2] = new Array('B',3);
    >
    > function test() {
    > var fun = null;
    > var funOpen = '';
    > var funBody = '';
    > var funEnd = '';
    > var x = '';
    > var space = '';
    > var len = example.length;
    >
    > for (i=0; i<len; i++) {
    > x = 'x'+(i+1);
    > funOpen+= space+'for ('+x+'=0; '+x+'<arr['+i+'][1]; '+x+'++) {\n';
    > funEnd += '}';
    > space+= ' ';
    > }
    >
    > funBody+= space+'calculateArray = new Array(arr.length);\n';
    > for (i=0; i<len; i++) {
    > x = 'x'+(i+1);
    > funBody+= space+'calculateArray['+i+'] = new
    > Array(arr['+i+'][0],'+x+');\n';
    > }
    > funBody+= space+'calculate(calculateArray);\n';
    > fun = new Function('arr',funOpen.concat(funBody,funEnd));
    > fun(example);
    > }
    >
    > function calculate(foo) {
    > alert(foo);
    > }
    > </script>
    > </head>
    >
    > <body bgcolor="#FFFFFF" onload="test()">
    >
    > </body>
    > </html>
    >
    > I would not say that it's any less ugly than 41 case, but definitely
    > shorter. :)
    > I guess any math prof would kill me for the above. The total amount of
    > loops is factorial of [1] values in your array. It's a strong hint
    > that the problem could be solved in some nice and profoundly academical
    > way using recursions. But it requires good matrix math knowledge more
    > than any JavaScript skills. The last of fine by me, the first is
    > floating miserably :-(
    > It works any way...
    >
     
    Mike P, Oct 23, 2005
    #5
  6. Mike P

    RobG Guest

    VK wrote:
    >>I imagine there's some way to do this with a recursive array or dynamically
    >>creating the function (ala, new Function)... I just don't really understand
    >>how to go about it.

    >
    >
    > Well, using runtime generated function:


    [...]
    >
    > I would not say that it's any less ugly than 41 case, but definitely
    > shorter. :)
    > I guess any math prof would kill me for the above. The total amount of
    > loops is factorial of [1] values in your array. It's a strong hint
    > that the problem could be solved in some nice and profoundly academical
    > way using recursions. But it requires good matrix math knowledge more
    > than any JavaScript skills. The last of fine by me, the first is
    > floating miserably :-(
    > It works any way...
    >


    There *had* to be a better way. This bugged me for hours, here's one
    that may do the job better and could be considered 'better' - it
    iterates through the first array of arrays and keeps splicing in
    elements. I think the use of concat() and splice() may restrict it to
    JavaScript 1.2 browsers and newer.

    The function copyA() copies a 1D array, it shouldn't be used with 2D (or
    more) arrays.

    I can think of a faster way - go through the first set of loops for the
    first loop (A[0]), then just copy those for every subsequent loop. But
    I'll leave the implementation up to the OP.

    The result is a 2D array:

    <script type="text/javascript">
    var A = [
    ['Q',2]
    ,['A',4]
    ,['B',2]
    ,['C',2]
    ];

    // This does some setup
    function doLoops(A)
    {
    var B=[];
    for (var i=0, aLen=A.length; i<aLen; ++i){
    addElements(A, B, i)
    }
    alert(B.join('\n'));
    }

    // The real work happens here
    function addElements(A, B, i)
    {
    var c = A[0];

    if (0 == i){ // Do first case
    for (var j=0, aLen=A[1]; j<aLen; ++j){
    B[j]=[c, j];
    }
    return;
    } else { // All all others
    var root // root array
    var loops=A[1]; // Number of loops

    for (var k=0, bLen=B.length; k<bLen; ++k){
    root = copyA(B[k*loops]);

    for (var m=0; m<loops; ++m){
    if (0==m){
    B[k*loops] = root.concat(c, m);
    } else {
    B.splice((k*loops + m),0,root.concat(c, m));
    }
    }
    }
    }
    return;
    }

    // Return a copy of a 1 dimensional array (vector)
    // If a 2d array is passed, references are returned
    // not a proper copy.
    function copyA(A)
    {
    var x = [];
    var i = A.length;
    while( i--){ x = A; }
    return x;
    }
    </script>



    --
    Rob
     
    RobG, Oct 24, 2005
    #6
  7. Mike P

    RobG Guest

    RobG wrote:
    [...]

    > I can think of a faster way - go through the first set of loops for the
    > first loop (A[0]), then just copy those for every subsequent loop. But
    > I'll leave the implementation up to the OP.


    This one is a bit faster and a lot tidier, it uses concat to copy the
    array instead of copyA, everything is in one function.

    <html><head<title>Loopy stuff</title>

    <script type="text/javascript">

    var A = [['Q',2],['A',4],['B',3]];

    function doLoops(A)
    {
    var B=[];
    var c=A[0][0];
    var loops=A[0][1];

    // Seed B
    for (var j=0; j<loops; ++j){
    B[j] = [c, j];
    }

    // Add extras
    for (var i=1, aLen=A.length; i<aLen; ++i){
    c = A[0];
    loops = A[1];
    for (var k=0, bLen=B.length; k<bLen; ++k){
    var root = B[k*loops].concat(c);
    for (var m=0; m<loops; ++m){
    B.splice((k*loops + m),(!m),root.concat(m));
    }
    }
    }

    // For show
    document.getElementById('zz').innerHTML =
    'A: ' + A + '<br>' +
    'Elements: ' + B.length + '<br>' + B.join('<br>');

    return B;
    }

    </script>

    </head><body onload="doLoops(A);">
    <div id="zz"></div>
    </body></html>


    [...]


    --
    Rob
     
    RobG, Oct 24, 2005
    #7
  8. Mike P wrote:

    > I will be passing my function a two dimensional array of varying length.
    > Within that array is one data point, and the number of times it should loop
    > through.
    >
    > So, for example, I might pass this to the function:
    >
    > example[0] = new Array("A",2);
    > example[1] = new Array("Q",4);
    > function loopIt(example);
    >
    > The function will then do the following:
    >
    > function loopIt(example) {
    > for (x1 = 0; x1 < example[0][1]; x1++) {
    > for (x2 = 0; x2 < example[1][1]; x2++) {
    > calculateArray = new Array(example.length);
    > calculateArray[0] = new Array(example[0][0],x1);
    > calculateArray[1] = new Array(example[1][0],x2);
    > calculate(calculateArray);
    > }
    > }
    > }
    >
    > But loopIt() doesn't know what example.length will be. Here I showed
    > example.length = 2. But if example.length = 41, this function wouldn't
    > work. How can I create a loop like this when example.length will vary?
    >
    > Thanks!


    If I have understood the problem correctly, here is a further addition
    to all the other contributions - a method using recursion:-

    function LoopIt(e)
    {
    this.example=e;
    this.exampleLength=e.length;
    this.indexArray=[];

    this.recurse(0);
    }

    LoopIt.prototype.recurse=function(n)
    {
    if (n<this.exampleLength)
    {
    var m=n+1;

    for (var i=0; i<this.example[n][1]; i++)
    {
    this.indexArray[n]=i;
    this.recurse(m);
    }
    return;
    }

    var a=[];

    for (var i=0; i<this.exampleLength; i++)
    {
    a=new Array(this.example[0],this.indexArray);
    alert(a.join(","));
    }

    calculate(a);
    };

    var example=[];
    example[0] = new Array("A",2);
    example[1] = new Array("Q",4);

    var l=new LoopIt(example); // Constructs and calls


    Julian
     
    Julian Turner, Oct 24, 2005
    #8
  9. Mike P

    Mike P Guest

    "RobG" <> wrote in message
    news:JP%6f.1122$...

    > This one is a bit faster and a lot tidier, it uses concat to copy the
    > array instead of copyA, everything is in one function.


    RobG, et al,

    I'm glad to know this was an interesting intellectual challenge to even the
    pros... I was completely stumped. I'll play around with the different
    approaches (run time compile, join/concat, and recursive object function) to
    figure out, not only which I'll actually use, but to learn how they work.

    Thanks again, to all!

    Mike
     
    Mike P, Oct 24, 2005
    #9
  10. Mike P

    RobG Guest

    Mike P wrote:
    > "RobG" <> wrote in message
    > news:JP%6f.1122$...
    >
    > > This one is a bit faster and a lot tidier, it uses concat to copy the
    > > array instead of copyA, everything is in one function.

    >
    > RobG, et al,
    >
    > I'm glad to know this was an interesting intellectual challenge to even the
    > pros... I was completely stumped. I'll play around with the different
    > approaches (run time compile, join/concat, and recursive object function) to
    > figure out, not only which I'll actually use, but to learn how they work.
    >
    > Thanks again, to all!
    >
    > Mike


    Hey, just for the record, here's a recursive version (sorry, couldn't
    help myself, this just kept popping into my brain!).


    var A = [['Q',2],['A',4],['B',3]];

    function recA(X, i, B)
    {
    var i = i || 0;
    if (!B) B = [[]];
    var root = B[B.length-1].concat(X[0]);
    var loops = X[1];
    for (var j=0; j<loops; ++j){
    B.splice((B.length-1+j), (!j), root.concat(j));
    if ( X[i+1] ) recA(X, i+1, B);
    }
    return B;
    }

    alert( recA(A).join('\n') );


    --
    Rob
     
    RobG, Oct 26, 2005
    #10
  11. Mike P

    VK Guest

    RobG wrote:
    > Mike P wrote:
    > > "RobG" <> wrote in message
    > > news:JP%6f.1122$...
    > >
    > > > This one is a bit faster and a lot tidier, it uses concat to copy the
    > > > array instead of copyA, everything is in one function.

    > >
    > > RobG, et al,
    > >
    > > I'm glad to know this was an interesting intellectual challenge to even the
    > > pros... I was completely stumped. I'll play around with the different
    > > approaches (run time compile, join/concat, and recursive object function) to
    > > figure out, not only which I'll actually use, but to learn how they work.
    > >
    > > Thanks again, to all!
    > >
    > > Mike

    >
    > Hey, just for the record, here's a recursive version (sorry, couldn't
    > help myself, this just kept popping into my brain!).
    >
    >
    > var A = [['Q',2],['A',4],['B',3]];
    >
    > function recA(X, i, B)
    > {
    > var i = i || 0;
    > if (!B) B = [[]];
    > var root = B[B.length-1].concat(X[0]);
    > var loops = X[1];
    > for (var j=0; j<loops; ++j){
    > B.splice((B.length-1+j), (!j), root.concat(j));
    > if ( X[i+1] ) recA(X, i+1, B);
    > }
    > return B;
    > }
    >
    > alert( recA(A).join('\n') );
    >
    >
    > --
    > Rob



    Aha! Did I predict it? Leverrier - John Couch Adams case :))
     
    VK, Oct 26, 2005
    #11
  12. Mike P

    Mike P Guest

    "RobG" <> wrote in message
    news:...

    > Hey, just for the record, here's a recursive version (sorry, couldn't
    > help myself, this just kept popping into my brain!).
    >
    > var A = [['Q',2],['A',4],['B',3]];
    >
    > function recA(X, i, B)
    > {
    > var i = i || 0;
    > if (!B) B = [[]];
    > var root = B[B.length-1].concat(X[0]);
    > var loops = X[1];
    > for (var j=0; j<loops; ++j){
    > B.splice((B.length-1+j), (!j), root.concat(j));
    > if ( X[i+1] ) recA(X, i+1, B);
    > }
    > return B;
    > }
    >
    > alert( recA(A).join('\n') );


    It clearly works, though I'm still trying to wrap my mind around how it
    works. Each iteration (e.g., currentArray = [[Q,0],[A,0],[B,0]]) needs to
    be fed back through calculate( currentArray ). I'm not clear where, in your
    (very impressive) recursive function, that would take place.

    Thanks!

    Mike
     
    Mike P, Oct 26, 2005
    #12
  13. Mike P

    Mike P Guest

    "RobG" <> wrote in message
    news:...
    > Hey, just for the record, here's a recursive version (sorry, couldn't
    > help myself, this just kept popping into my brain!).
    > < snip >
    > Rob


    Wait, I think I got it:

    function test() {
    var n = 0;
    arrays = recA(A);
    for ( n = 0; n < arrays.length; n++ ) { calculate( arrays[n] ) }
    }

    .... I'm still stepping through a debug to try and figure it out :)

    Mike
     
    Mike P, Oct 26, 2005
    #13
  14. Mike P

    RobG Guest

    Mike P wrote:
    > "RobG" <> wrote in message
    > news:...
    > > Hey, just for the record, here's a recursive version (sorry, couldn't
    > > help myself, this just kept popping into my brain!).
    > > < snip >
    > > Rob

    >
    > Wait, I think I got it:
    >
    > function test() {
    > var n = 0;
    > arrays = recA(A);
    > for ( n = 0; n < arrays.length; n++ ) { calculate( arrays[n] ) }
    > }
    >
    > ... I'm still stepping through a debug to try and figure it out :)


    Here's the explanation (with a bit of cleaning up):

    var A = [['Q',2],['A',4],['B',3]];

    // A value is passed for X, but not for i or B
    function recA(X, i, B)
    {

    /* If i is undefined, set its value to zero. This will
    * only happen the first time recA() is called. When it calls
    * itself, it passes values for i and B.
    */
    var i = i || 0;

    /* If B is undefined, make it an array with one element which is
    * another empty array. The logic here is identical to that
    * above, only the code is a bit different. The same code
    * pattern could be use for both.
    */
    if (!B) B = [[]];

    // Both the above lines could be replaced with the following
    // It's a bit cryptic and so not great for maintenance

    !i && (B=[[]]) && (i=0);


    /* Get the last row of the result array, B
    * Make a copy of it and append the value at X[0]
    * 'A' will be appended the first time through,
    * 'B' the second, 'C' the third, etc.
    * The array concat method copies and appends in one go
    */
    var root = B[B.length-1].concat(X[0]);

    // For this iteration, get the number of loops.
    var loops = X[1];

    // Start doing the loops
    for (var j=0; j<loops; ++j){

    /* The original line here was:
    * B.splice((B.length-1+j), (!j), root.concat(j));
    * a better version is:
    */
    B.splice((B.length-!j), 1, root.concat(j));

    /* It calls the splice method, telling it to start at
    * B.length-1 when j=0 and B.length-0 when j>0.
    * slice modifies in place, so B is modified directly.
    * Its return value is whatever is deleted (if anything)
    * We don't need it so it's ignored.
    *
    * The number of lines to replace is always 1, when
    * j=0 the modified line (array) replaces the last, when
    * j>0 the modified line is appended. Telling splice
    * to replace lines after the end of the array
    * effectively does nothing.
    *
    * concat is used again to get a copy of root with the
    * value of j appended
    *
    * Lastly, if we aren't at the last element of X,
    * call recA() again and pass i+1 to i and B to B.
    * i is local to each instance of recA and so
    * doesn't affect the value of i in other instances.
    * All the B's are local too, but they all reference the
    * same array, so just one array keeps getting modified.
    */
    if ( X[i+1] ) recA(X, i+1, B);
    }

    /* The return value is ignored within the recursion
    * since it's just a reference to an array that we
    * already have a reference to.
    * Whatever called recA() should to assign the returned
    * reference to a variable or do something with it.
    */
    return B;
    }

    --
    Rob
     
    RobG, Oct 27, 2005
    #14
  15. Mike P

    Mike P Guest

    Re: Looping through variable number of arrays variable times? - RUNTIME???

    As a followup:

    I've been playing around with the various options, trying to learn them, and
    figure out which makes sense.

    I got an error @ this.recurse(0) on Julian's recursive function, and wasn't
    sure how to resolve it, so I skipped testing his. I was able to run a
    benchmark on both RobG's recursive function and VK's run-time compile
    version. Remember, worst case, I'll be running this using example.length =
    41. The numbers get pretty scary with larger arrays. I used example.length
    = 6, for the test. Specifically:

    example = [["A",7],["B",7],["C",7],["D",7],["E",7],["F",7]]

    While I'm running a pretty slow machine, I came up with the following
    runtimes:

    RobG's Recursive Function = 102958 ms
    VK's runtime compile = 9113 ms

    ....just thought you might be interested.

    Thanks!

    Mike
     
    Mike P, Oct 29, 2005
    #15
  16. Mike P

    VK Guest

    Re: Looping through variable number of arrays variable times? - RUNTIME???

    Mike P wrote:
    > As a followup:
    >
    > I've been playing around with the various options, trying to learn them, and
    > figure out which makes sense.
    >
    > I got an error @ this.recurse(0) on Julian's recursive function, and wasn't
    > sure how to resolve it, so I skipped testing his. I was able to run a
    > benchmark on both RobG's recursive function and VK's run-time compile
    > version. Remember, worst case, I'll be running this using example.length =
    > 41. The numbers get pretty scary with larger arrays. I used example.length
    > = 6, for the test. Specifically:
    >
    > example = [["A",7],["B",7],["C",7],["D",7],["E",7],["F",7]]
    >
    > While I'm running a pretty slow machine, I came up with the following
    > runtimes:
    >
    > RobG's Recursive Function = 102958 ms
    > VK's runtime compile = 9113 ms
    >
    > ...just thought you might be interested.



    Do you know *what* killed the cat?
    You've almost spelled a dark secret of JavaScript related with its
    interpreted (vs. compiled) nature; but your guardian angel stopped you
    on time.
    Search this newsgroup using keyword "evil". Look the posters' Names.
    You were aware...








    ;-)
     
    VK, Oct 29, 2005
    #16
  17. Re: Looping through variable number of arrays variable times? - RUNTIME???

    "Mike P" wrote:
    <snip>
    > example = [["A",7],["B",7],["C",7],["D",7],["E",7],["F",7]]
    >
    > While I'm running a pretty slow machine, I came up with
    >the following runtimes:
    >
    > RobG's Recursive Function = 102958 ms
    > VK's runtime compile = 9113 ms
    >
    > ...just thought you might be interested.


    If you were interested in speed you probably should have said so form
    the outset, and provided considerably more detail as to the real problem
    instead of just this one minor part of it.

    Recursion is inevitably slow, it lends itself to working with more
    complex structures than yours, such as trees. But there is no need for
    the 'meta scripting' (building new scripts as strings and having them
    dynamically interpreted) approach here either.

    Unfortunately, in not providing details of the wider problem, and
    particularly your - calculate - function, it is not possible to gauge
    whether all the Array creation inherent in your original code, and the
    suggested alternatives, is necessary. If the Arrays are just a way of
    passing parameters to the - calculate - function, and are effectively
    thrown away after the function call then there is no need to create a
    new array for each call at all. The result will be considerably quicker
    than all of the alternatives proposed so far:-

    function loopIt(ar){
    var len, c, o = [];
    if((len = ar.length)){
    c = --len;
    do{
    o[c] = [ar[c][0], 0];
    }while(c--);
    do{
    c = len;
    while((++o[c][1]) == ar[c][1]){
    o[c][1] = 0;
    if(--c == -1){
    break;
    }
    }
    calculate(o);
    }while(c != -1);
    }
    }

    But if the - calculate - function does preserve the Arrays in some way,
    so it does need to be passes a distinct array with each call, then:-

    function loopIt(ar){
    var len, t, c, a1 = [];
    var a3, a2 = [];
    if((len = ar.length)){
    c = --len;
    do{
    a1[c] = 0;
    a2[c] = ar[c][0];
    }while(c--);
    do{
    t = len;
    while((++a1[t]) == ar[t][1]){
    a1[t] = 0;
    if(--t == -1){
    break;
    }
    }
    a3 = [];
    c = len;
    do{
    a3[c] = [a2[c], a1[c]];
    }while(c--);
    calculate(a3);
    }while(t != -1);
    }
    }

    - gets the job done with direct code, and mostly quicker than the 'meta
    scripting' approach.

    In any case, the desire to pass such a complex structure to a function
    suggests that the whole problem would be amenable to better (certainly
    faster) solutions.

    Richard.
     
    Richard Cornford, Oct 30, 2005
    #17
  18. Mike P

    Mike P Guest

    Re: Looping through variable number of arrays variable times? - RUNTIME???

    "Richard Cornford" <> wrote in message
    news:dk3lem$k09$1$...

    > If you were interested in speed you probably should have said so form
    > the outset, and provided considerably more detail as to the real problem
    > instead of just this one minor part of it.

    <SNIP>

    Richard,

    Thanks for the feedback, and code on this one. Quite honestly, it didn't
    occur to me that speed would be an issue when I first approached this. Once
    I ran the code a few times, I realized that more complex arrays were taking
    HOURS to run, and started re-evaluating the code and my approach in general.

    Long-term, I'm working on an ajax-based Monopoly game. At the moment, I'm
    focusing on some basic AI for the game. I have relative values for each
    configuration of a property in the game of Monopoly. (e.g., what is
    Boardwalk with 2 houses worth, long term, as opposed to Park Place with two
    houses). In this project, I've created a form, where a player can enter all
    the properties they own, and their current state (e.g., mortgaged,
    unmortgaged, 3 houses, a hotel, etc.), and how much cash the player has on
    hand. I'm then running through all the various options they have available
    to them (e.g., mortgage one property to get cash, then build on another).
    I'm then calculating the relative value of that complete configuration and
    comparing them. So, yes, I'm actually running some calculations based on
    each array. At the end, I tell the player their best possible option.
    Pretty straightforward, but my approach had been to run through all the
    permutations. It's taking far too long, when a player owns more than one
    Monopoly, so I'm open to any ideas you may have.

    Let me see if I can follow your code samples, and see how it performs in the
    context of my script.

    Thanks again!

    Mike
     
    Mike P, Oct 31, 2005
    #18
  19. Re: Looping through variable number of arrays variable times? - RUNTIME???

    Mike P wrote:
    > I got an error @ this.recurse(0) on Julian's recursive function, and wasn't
    > sure how to resolve it, so I skipped testing his.


    Apologies for that. No doubt Richard's solutions are more effective,
    and recursion is not the best in terms of performance, but if you were
    still interested, here is a slightly adjusted version of my function to
    try.

    You could no doubt try speeding it up with use of "while" and "do
    while" loops, and reverse loops (i.e. length-1 --> 0)

    function LoopIt(e)
    {
    var L=e.length;
    var a=[];

    Recurse(0);

    function Recurse(n)
    {
    if (n<L)
    {
    var m=n+1;

    for (var i=0; i<e[n][1]; i++)
    {
    a[n]=i;
    Recurse(m);
    }
    return;
    }

    var c=[];

    for (var i=0; i<L; i++)
    {
    c=new Array(e[0],a);
    //alert(c.join(","));
    }

    calculate(c);
    }
    }

    var example=[];
    example[0] = new Array("A",2);
    example[1] = new Array("Q",4);

    LoopIt(example);


    Julian
     
    Julian Turner, Oct 31, 2005
    #19
  20. Re: Looping through variable number of arrays variable times? - RUNTIME???

    Julian Turner wrote:
    > No doubt Richard's solutions are more effective,
    > and recursion is not the best in terms of performance


    Here is another non-recursive version:-

    function LoopIt(e)
    {
    var L=e.length;
    var c=[];
    var t;

    var i=L;
    while(i--)
    {
    c=[e[0],0,e[1]];
    }

    Outer:
    while(1)
    {
    t=c[L-1];
    while(t[1]<t[2])
    {
    //alert(c);
    //calculate(c);
    t[1]++;
    }

    t[1]=0;

    var i=L-1;
    while(i--)
    {
    t=c;
    if (t[1]==t[2]-1)
    {
    t[1]=0;
    }
    else
    {
    t[1]++;
    continue Outer;
    }
    }

    break;
    }
    }

    Julian
     
    Julian Turner, Oct 31, 2005
    #20
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. VisionSet
    Replies:
    1
    Views:
    438
    Weasel
    Aug 5, 2003
  2. Frank
    Replies:
    1
    Views:
    2,483
    Neomorph
    Aug 5, 2003
  3. Bosconian
    Replies:
    11
    Views:
    163
    Bosconian
    Oct 16, 2006
  4. Mark Scott

    Looping through Arrays - variable undefined?

    Mark Scott, Feb 9, 2008, in forum: Javascript
    Replies:
    7
    Views:
    135
    Thomas 'PointedEars' Lahn
    Feb 13, 2008
  5. Aaron
    Replies:
    2
    Views:
    534
    dhtml
    Apr 10, 2011
Loading...

Share This Page