Improve an algorithme involving 6 loops

[dphizler]

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.

 

[Puppet_Sock]

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

 

[mlimber]

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>

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:ow(). 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

 

[Daniel T.]

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.

 

[dphizler]

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.

 

[Daniel T.]

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...

 

[dphizler]

Daniel T. a écrit :

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.

 

[Daniel T.]

Daniel T. a écrit :


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;