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.

Smart pointers. shared_ptr and normal pointer

Shared pointer can make our code more secure. shared_pointer is a kind of pointer that allow to others pointer share his container. And when no pointer points to a container, the garbage collector erase the container thus ensuring the reliable of the program in order to no consume the heap of the process.

If we use the next code, the above behaviour.

The follow code show the common error, creating new pointers and not erase the container.


If we compile and execute this two codes, we obtain the next statistical result: