alternative to for loops

[harryos]

hi
i am trying to do a calculation like below.It iterates over the
elements of a double[][] using 2 for loops .Since i am using 2 for
loops to do this,i am worried that it will be slow for a large input
array.I thought of using a Matrix class like jama or colt to replace
the double[][] but am not sure how to reproduce the logic (finding the
sum value and filling the distances[].
if anybody can point out the correct way to handle this using a matrix
class pls help.
thanks in advance
harry

public double[] findDistances(double[][] temp){

double[] distances = new double[temp.length];
for (int i = 0; i < temp.length; i++) {
double sum = 0.0;
for (int j = 0; j < temp[0].length; j++) {
sum += temp[j];
}
distances = sum;
}
return distances;
}

 

[Joshua Cranmer]

hi
i am trying to do a calculation like below.It iterates over the
elements of a double[][] using 2 for loops .Since i am using 2 for
loops to do this,i am worried that it will be slow for a large input
array.I thought of using a Matrix class like jama or colt to replace
the double[][] but am not sure how to reproduce the logic (finding the
sum value and filling the distances[].

Define "large"? The code below took 0.5s (including JVM startup) on my
computer for a 10 million element matrix.

Any improvement on a linear scan would have to rely on special
properties, such as knowing in advance that the majority of elements is
0. Without knowing anything specific, it's hard to improve on the code...

for (int j = 0; j < temp[0].length; j++) {

.... although I would recommend using temp.length here.

 

[harryos]

Define "large"? The code below took 0.5s (including JVM startup) on my
computer for a 10 million element matrix.

in my program this code is only a small part of calculations and i do
not want it to take more than a few nanosecs..
My pc is quite old with less speed:-(.I was using matrix of the size
50000 X 50000.
also i thought that using for loops to go thru a double[][] was
inferior to using a performance optimized matrix class.

for (int j = 0; j < temp[0].length; j++) {

... although I would recommend using temp.length here.

does that make a difference?i assumed that all elements of temp[] are
of equal length


thanks for the reply
harry

 

[Boris Stumm]

Define "large"? The code below took 0.5s (including JVM startup) on my
computer for a 10 million element matrix.

in my program this code is only a small part of calculations and i do
not want it to take more than a few nanosecs..
My pc is quite old with less speed:-(.I was using matrix of the size
50000 X 50000.
also i thought that using for loops to go thru a double[][] was
inferior to using a performance optimized matrix class.

The only optimization that a "matrix class" can do here is using a
one-dimensional array instead of a two-dimensional one. This you can
easily do yourself.
(I found this as example: http://isomerica.net/~dpn/Matrix.java.html)

This might increse the speed by a significant percentage. Besides this,
you cannot use a real alternative to loops. The problem that you are
trying to solve has a lower runtime bound in O(n^2), so you _need_ two
nested loops.

 

[Patricia Shanahan]

Then your cause is hopeless. You have 2.5 billion `double'
values, or 20GB of numeric data that must move from memory to
the CPU for inspection and computation. Fetching 20GB in "a few
nanosecs" would need a memory bandwidth in the neighborhood of
a couple exabytes per second, a few million times faster than
today's fastest supercomputers. A machine that is "quite old
with less speed" will take a wee bit longer ... Oh, and that's
just the raw memory transfer: Doing arithmetic on the numbers,
managing array indices, and so on will add some more time. So
forget it.

... or tell us more about the actual problem you're
trying to solve.

In particular, what calculates this matrix? Maybe it can be modified to
also calculate the sums.

Patricia

 

[Nigel Wade]

in my program this code is only a small part of calculations and i do
not want it to take more than a few nanosecs..
My pc is quite old with less speed:-(.I was using matrix of the size
50000 X 50000.

Interesting. What "quite old " PC hardware, and OS, allowed you to create an
array which is 20GB in size?

I'm fairly certain that any current hardware which does allow you to create an
array that size won't perform your intended calculations in a few nanoseconds.
For example a Sun X4600 with 32GB of RAM took about 2mins just to create and
initialize a 50000x50000 array (the JVM needed 28GB of heap just to get it to
run). The calculations in your method took a further 30s.

I don't think software optimization, even combined with the current world's
fastest hardware, will get that reduced by 10 orders of magnitude. Maybe you
need more realistic numbers in your estimates.

 

[Daniel Pitts]

hi
i am trying to do a calculation like below.It iterates over the
elements of a double[][] using 2 for loops .Since i am using 2 for
loops to do this,i am worried that it will be slow for a large input
array.I thought of using a Matrix class like jama or colt to replace
the double[][] but am not sure how to reproduce the logic (finding the
sum value and filling the distances[].
if anybody can point out the correct way to handle this using a matrix
class pls help.
thanks in advance
harry

a "double[][]" that is 100x100 is not going to perform significantly
different from a "double[]" that is (100*100) in length.

Just because you have a nested for loop doesn't mean you're going to
have a slower algorithm. It just means that your algorithm is O(n*m),
which would *still* be the case if you moved to a linear array instead.

 

[Boris Stumm]

[...]
My pc is quite old with less speed:-(.I was using matrix of the size
50000 X 50000.
also i thought that using for loops to go thru a double[][] was
inferior to using a performance optimized matrix class.

The only optimization that a "matrix class" can do here is using a
one-dimensional array instead of a two-dimensional one. This you can
easily do yourself.

Not with a 50000x50000 matrix, he can't ...

You are right, I didn't do the space calculations...

 

[Roedy Green]

ince i am using 2 for
loops to do this,i

Don't worry, measure. The for loop itself is something optimisers
hover over like mother hens.

See http://mindprod.com/jgloss/time.html