domingo, 23 de octubre de 2011

End.

I started this blog many years ago, and i posted new notes while i studied my engineer degree.
Now, it is time to close.
Best regards.

martes, 11 de enero de 2011

Nested loop optimized with Java Iterators

Few days ago, i saw a piece of a geoprocessing algorithm code. This algorithm get a vector of points, each point with two spatial coordinates: (x,y), and calculate the euclidean distance between of each point with the whole points of the vector. The result is a beatifull matrix of distance between each points.

The problem was the follow: this algorithm use "Iterators" on the vector, as follows:

Iterator i1=layer.iterator();
while(i1.hasNext()){
i1.next();
Iterator i2=layer.iterator();
while(i2.hasNext()){
i2.next();
// calculate Euclidean distance
}
}

but it has a problem in optimization terms, because the distance between point #1 and point #2 is the same that between point #2 and point #1, i.e.,an optimized algorithm only need compute the superior diagonal of the matrix, beacuse the matrix of distances is simetric.

In above sample, with optimized algorithm, we need 3 iterations on the vector and symmetrize the matrix; in the other hand without optimization we need 9 iterations: n^2.

If we assume that the objects in the vector are unique, the best solution in order of do not lose the semantic of Iterators is the use the follows code:

Iterator i1 = l.iterator();
while (i1.hasNext()) {
Integer ii1 = (Integer) i1.next();
Iterator i2 = l.subList(l.indexOf(ii1),l.size()).iterator();
while (i2.hasNext()){
i2.next();
}
}

If we use two index in order to follow the loops, we can use the follows code:

int i=0;
Iterator i1 = l.iterator();
while (i1.hasNext()) {
c=0:
Integer ii1 = (Integer) i1.next();
Iterator i2 = l.subList(i,l.size()).iterator();
while (i2.hasNext()){
i2.next();
long distance = ....
matrix[i][j] = distance;
matrix[j][i] = distance;
c++;
}
i++;
}

In this way we can reduce the computing time in n/2.