Improve an algorithme involving 6 loops

Discussion in 'C++' started by dphizler@gmail.com, May 8, 2006.

  1. Guest

    This is the basic concept of my code:

    #include <iostream.h>
    #include <math.h>
    #include <stdlib.h>

    int main() {
    double Gtotal, L, size, distance, theRandom;
    double Gi[ 50 ][ 50 ][ 50 ];
    int xi, xf, yi, yf, zi, zf;

    Gtotal = 0; size = 50; L = 2;

    // here every slot in the matrix has the same
    coordinates, to keep things simple
    // this code wasn't used to test this particular
    situation
    xi=2; xf=1; yi=2; yf=1; zi=2; zf=1;

    for(int x = 0; x < size; x++) {
    for(int y = 0; y < size; y++) {
    for(int z = 0; z < size; z++) {
    theRandom = (1 + rand()% 6 );
    if(theRandom <= 2) Gi[ x ][ y ][ z ] = 0;
    else Gi[ x ][ y ][ z ] = x - y + z;
    }}}

    for(int l = 0; l < size; l++) {
    for(int m = 0; m < size; m++) {
    for(int n = 0; n < size; n++) {
    for(int i = 0; i < size; i++) {
    for(int j = 0; j < size; j++) {
    for(int k = 0; k < size; k++) {
    if(Gi[ i ][ j ][ k ] != 0 || (i != l && j != m && k != n)) {
    distance = sqrt((xi - xf)^2 + (yi - yf)^2 + (zi - zf)^2);
    Gtotal = Gtotal + (((1/distance) * exp(-distance/L)) * Gi[ i ][ j ][
    k ]);
    }
    }}}

    // normally I would have another array
    here instead of the same one
    // I just wanted to keep things simple
    Gi[ l ][ m ][ n ] = Gi[ l ][ m ][ n ] + Gtotal;
    cout << Gi[ l ][ m ][ n ] << endl;
    }}}

    return 0;
    }

    Basic idea, I have a 3d array 50x50x50 that has some data in it.
    I'm trying to make a new 3d array based on the first one where each
    slot in the new array is generated from all 50x50x50 slots from the
    first 3d array.

    Now I know that
    (1/distance) * exp(-distance/L)
    will be redundant because the distance between two points in the array
    will be redundant.

    Try to imagine the 3d arrays being data in a cartesian graph where each
    slot has cartesian coordinates.

    Hopefully this is clear as to what I'm trying to do. I want to improve
    the the runtime.
     
    , May 8, 2006
    #1
    1. Advertising

  2. Puppet_Sock Guest

    wrote:
    > This is the basic concept of my code:

    [snip code that seems like it's intended to explain something, but that
    does not]

    There's a good chance you are off topic anyway. We mostly do
    language issues here. It's possible to tease us into "how to" things
    if they are interesting, or if you pose them as "how do I do this in
    C++?"

    > Basic idea, I have a 3d array 50x50x50 that has some data in it.
    > I'm trying to make a new 3d array based on the first one where each
    > slot in the new array is generated from all 50x50x50 slots from the
    > first 3d array.


    Ok, that was not very clear at all. And you should consider the wisdom
    of asking, in effect, "How do I do what this code does only better?"

    What is the formula that is supposed to determine the destination
    array from the origin array? What if it's not 50x50x50?

    > Now I know that
    > (1/distance) * exp(-distance/L)
    > will be redundant because the distance between two points in the array
    > will be redundant.
    >
    > Try to imagine the 3d arrays being data in a cartesian graph where each
    > slot has cartesian coordinates.
    >
    > Hopefully this is clear as to what I'm trying to do. I want to improve
    > the the runtime.


    Nope. Not clear at all. Sorry.

    If you could maybe explain in a way that does not involve "how can I
    do what these six loops do?" In other words, don't use source code
    as spec.
    Socks
     
    Puppet_Sock, May 8, 2006
    #2
    1. Advertising

  3. mlimber Guest

    wrote:
    > This is the basic concept of my code:
    >
    > #include <iostream.h>
    > #include <math.h>
    > #include <stdlib.h>


    The first header is deprecated. User <iostream> (and "using std
    namespace;"?). The latter two should usually be replaced with <cmath>
    and <cstdlib>.

    > int main() {
    > double Gtotal, L, size, distance, theRandom;
    > double Gi[ 50 ][ 50 ][ 50 ];
    > int xi, xf, yi, yf, zi, zf;


    Don't declare variables until you can initialize them, and then make
    those that don't need to change const and create the variables in as
    small of a scope as possible. You might also consider using a container
    instead of an array (see
    http://www.parashift.com/c -faq-lite/containers.html#faq-34.1 and
    http://www.parashift.com/c -faq-lite/operator-overloading.html#faq-13.10
    and
    http://www.parashift.com/c -faq-lite/operator-overloading.html#faq-13.11).

    >
    > Gtotal = 0; size = 50; L = 2;


    Avoid putting more than one executable statement per line, and
    initialize variables when you declare them.

    >
    > // here every slot in the matrix has the same
    > coordinates, to keep things simple
    > // this code wasn't used to test this particular
    > situation
    > xi=2; xf=1; yi=2; yf=1; zi=2; zf=1;
    >
    > for(int x = 0; x < size; x++) {
    > for(int y = 0; y < size; y++) {
    > for(int z = 0; z < size; z++) {
    > theRandom = (1 + rand()% 6 );
    > if(theRandom <= 2) Gi[ x ][ y ][ z ] = 0;
    > else Gi[ x ][ y ][ z ] = x - y + z;
    > }}}
    >
    > for(int l = 0; l < size; l++) {
    > for(int m = 0; m < size; m++) {
    > for(int n = 0; n < size; n++) {
    > for(int i = 0; i < size; i++) {
    > for(int j = 0; j < size; j++) {
    > for(int k = 0; k < size; k++) {
    > if(Gi[ i ][ j ][ k ] != 0 || (i != l && j != m && k != n)) {
    > distance = sqrt((xi - xf)^2 + (yi - yf)^2 + (zi - zf)^2);


    First, I don't think you meant to use the xor operator (^) here. You
    probably meant to use std::pow(). Second, since xi, xf, yi, yf, zi, and
    zf don't change, calculate this outside the loop and make it a const.

    > Gtotal = Gtotal + (((1/distance) * exp(-distance/L)) * Gi[ i ][ j ][
    > k ]);


    This is more concise and efficient:

    Gtotal += distanceConst * Gi[j][k];

    where the constant distanceConst is computed outside the loop.

    > }
    > }}}
    >
    > // normally I would have another array
    > here instead of the same one
    > // I just wanted to keep things simple
    > Gi[ l ][ m ][ n ] = Gi[ l ][ m ][ n ] + Gtotal;
    > cout << Gi[ l ][ m ][ n ] << endl;


    Don't use std::endl, which inserts a cr-lf and then flushes the buffer.
    Instead, use an ordinary '\n'.

    > }}}
    >
    > return 0;
    > }
    >
    > Basic idea, I have a 3d array 50x50x50 that has some data in it.
    > I'm trying to make a new 3d array based on the first one where each
    > slot in the new array is generated from all 50x50x50 slots from the
    > first 3d array.
    >
    > Now I know that
    > (1/distance) * exp(-distance/L)
    > will be redundant because the distance between two points in the array
    > will be redundant.
    >
    > Try to imagine the 3d arrays being data in a cartesian graph where each
    > slot has cartesian coordinates.
    >
    > Hopefully this is clear as to what I'm trying to do. I want to improve
    > the the runtime.


    Cheers! --M
     
    mlimber, May 8, 2006
    #3
  4. Daniel T. Guest

    In article <>,
    wrote:

    > Basic idea, I have a 3d array 50x50x50 that has some data in it.
    > I'm trying to make a new 3d array based on the first one where each
    > slot in the new array is generated from all 50x50x50 slots from the
    > first 3d array.


    You have a 125000 element array and you want to update the all the
    values. That's going to take some time no matter how you slice it O(n).

    The best way to speed it up would be lazy initialization. Only calculate
    the value of a slot when some other part of the code actually needs it.
    The whole program will probably not be any faster, but it will probably
    feel faster to the user.


    > Now I know that
    > (1/distance) * exp(-distance/L)
    > will be redundant because the distance between two points in the array
    > will be redundant.
    >
    > Try to imagine the 3d arrays being data in a cartesian graph where each
    > slot has cartesian coordinates.
    >
    > Hopefully this is clear as to what I'm trying to do. I want to improve
    > the the runtime.


    It is clear what your are doing, not what you are trying to do. :)
     
    Daniel T., May 8, 2006
    #4
  5. Guest

    thanks mlimber for the input

    I tried to explain that xi, xf, yi, yf, zi, and zf do change for each
    slot of Gi.

    Lots of the things you said were relavant. I bunched up the code when I
    was writing it to better see the loops but I do space my code normally.

    Anyways, I figured out a way to do this. Thanks for your time.
     
    , May 8, 2006
    #5
  6. Daniel T. Guest

    In article <>,
    wrote:

    > thanks mlimber for the input
    >
    > I tried to explain that xi, xf, yi, yf, zi, and zf do change for each
    > slot of Gi.
    >
    > Lots of the things you said were relavant. I bunched up the code when I
    > was writing it to better see the loops but I do space my code normally.
    >
    > Anyways, I figured out a way to do this. Thanks for your time.


    Please, share it with us...
     
    Daniel T., May 8, 2006
    #6
  7. Guest

    Daniel T. a écrit :

    > In article <>,
    > wrote:
    >
    > > thanks mlimber for the input
    > >
    > > I tried to explain that xi, xf, yi, yf, zi, and zf do change for each
    > > slot of Gi.
    > >
    > > Lots of the things you said were relavant. I bunched up the code when I
    > > was writing it to better see the loops but I do space my code normally.
    > >
    > > Anyways, I figured out a way to do this. Thanks for your time.

    >
    > Please, share it with us...


    Actually, I'm right back at square one now. Even though the runtime has
    greatly improved, it's still too long. The variable 'size' is set to 20
    in the code but ideally it should be set to 50.

    This is the code I came up with:

    #include <iostream.h>
    #include <math.h>
    #include <algorithm>
    #include <time.h>

    int main() {
    const int size = 20;
    const double L = 2;
    double distance, theRandom, Gtotal, temp, dif;
    int i_index, m_index, x, y, z;
    time_t start,end;

    void sortValues(int&, int&, int&);

    double *Gi;
    double *Gf;
    double *theMatrix;

    Gi = new double[size*size*size];
    Gf = new double[size*size*size];
    theMatrix = new double[size*size*size];

    for(x = 0; x < size*size*size; x++) {
    theMatrix[ x ] = 0;
    theRandom = (1 + rand()% 6 );

    if(theRandom <= 2)
    Gi[ x ] = 0;
    else
    Gi[ x ] = x * theRandom;
    }

    time (&start);

    //Algorithm starts here

    for(int l = 0; l < size; l++) {
    for(int m = 0; m < size; m++) {
    for(int n = 0; n < size; n++) {
    Gtotal = 0;

    for(int i = 0; i < size; i++) {
    for(int j = 0; j < size; j++) {
    for(int k = 0; k < size; k++) {
    i_index = i + j * size + k * size * size;

    if(Gi[ i_index ] != 0 ||
    (i != l && j != m && k != n)) {
    x = abs(i-l);
    y = abs(j-m);
    z = abs(k-n);

    sortValues(x, y, z);
    m_index = x + y * size + z * size * size;

    if(theMatrix[ m_index ] != 0) {
    temp = theMatrix[ m_index ];
    } else {
    distance = sqrt(pow(x,2) + pow(y,2) + pow(z,2));

    theMatrix[ m_index ] =
    (1/distance) * exp(-distance/L);
    }

    Gtotal += (theMatrix[ m_index ] * Gi[ i_index ]);
    }
    }}}

    if(Gtotal != 0)
    Gf[ l + (m * size) + (n * size * size) ] += Gtotal;
    }}}

    //Algorithm ends here

    time (&end);
    dif = difftime (end,start);
    cout << "Delta t : " << dif << endl;
    return 0;
    }

    void sortValues(int &x, int &y, int &z) {
    int n;

    if(x >= y) {
    n = x;
    x = y;
    y = n;
    }
    if(x >= z) {
    n = x;
    x = z;
    z = n;
    }
    if(y >= z) {
    n = y;
    y = z;
    z = n;
    }
    }

    -----------------------------------------------------------
    Anyways, I haven't found a better way of doing this. I was suggested to
    consider using a Sparse Matrix but I have no idea how to make a 3d one.


    All I'm trying to do is reduce the amount of time it takes to compute
    this.
     
    , May 10, 2006
    #7
  8. Daniel T. Guest

    In article <>,
    wrote:

    > Daniel T. a écrit :
    >
    > > In article <>,
    > > wrote:
    > >
    > > > thanks mlimber for the input
    > > >
    > > > I tried to explain that xi, xf, yi, yf, zi, and zf do change for each
    > > > slot of Gi.
    > > >
    > > > Lots of the things you said were relavant. I bunched up the code when I
    > > > was writing it to better see the loops but I do space my code normally.
    > > >
    > > > Anyways, I figured out a way to do this. Thanks for your time.

    > >
    > > Please, share it with us...

    >
    > Actually, I'm right back at square one now. Even though the runtime has
    > greatly improved, it's still too long. The variable 'size' is set to 20
    > in the code but ideally it should be set to 50.
    >
    > Anyways, I haven't found a better way of doing this. I was suggested to
    > consider using a Sparse Matrix but I have no idea how to make a 3d one.


    A sparse matrix is simple:

    class tuple {
    tuple( int a, int b, int c ):x(a),y(b),z(c) { }
    int x;
    int y;
    int z;
    };

    bool operator<( tuple a, tuple b ) {
    return a.x < b.x ||
    a.x == b.x && a.y < b.y ||
    a.x == b.x && a.y == b.y && a.z < b.z;
    }

    typedef map< tuple, double > SparceMatrix;

    Access it as follows:

    SparceMatrix m;

    m[ tuple( 5, 2, 6 ) ] = 234.8673;
     
    Daniel T., May 10, 2006
    #8
    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. Jun
    Replies:
    1
    Views:
    345
    Sudsy
    Nov 25, 2003
  2. Maurice Hulsman
    Replies:
    1
    Views:
    1,856
    Guus Bosman
    Jul 25, 2004
  3. Replies:
    6
    Views:
    405
    Ian T
    Dec 10, 2004
  4. Oliver Wong
    Replies:
    5
    Views:
    448
    Oliver Wong
    Nov 2, 2005
  5. Me
    Replies:
    2
    Views:
    247
Loading...

Share This Page