Beware the libraries...

Although I mentioned my next post would be mid-week, I have come across a nuisance within Java.

<EDIT> Just discovered the cause for vertices being "thrown" from the graph; the when two vertices are too close together, the forces repulse so much that the displacement is magnitudes higher than it should be. This is what happens when you use quadratics such as the inverse square law.


For reference; if d = 0.01, 1/d^2 = 1000, if nothing is limiting the forces this is allowed through. The repulsive forces are calculated first so this should never happen (unless the springs are too powerful), however, in larger graphs its possible the forces push two vertices too close or something? (still doesn't sound like it should happen but its the only piece of code (so far) that exhibits such force)</EDIT>

It is relatively obvious that more complex calculations take a little more time to calculate, although if only performed a few times, it is negligible. Fruchterman and Reingold mentioned that Eades logarithmic equation for calculating spring forces were inefficient and managed to get similar results using linear equations (although I may need to check if it was the algorithm or the calculation which was inefficient).

Although I should be focusing on other more important aspects and not the software/programming part, I wanted to check whether Java would display a difference between such calculations. I found some interesting results:

for 10million iterations (had to scale for measurable data);

calculation [x - 1.5] - 185ms

calculation [x * x] - 206ms

calculation [math.log(x)] - 3822ms

calculation [math.pow(x)] - 3765ms

As you can see, using java.lang.Math significantly increases the time taken. This is most likely due to having call the method from the Math class instead of throwing it at the processor. Note, importing the Math libraries makes little difference. Bare in mind that a graph of 5k vertices in an O(|V|^2) algorithm is 25million iterations.

Just food for thought for any mathematicians or statisticians out there working with Java libraries and collections of millions of entities, and are looking to reduce runtime. Now back to implementing my ideas...

<EDIT> Thanks for the advice Chris; for those who do not read comments, Chris proposed a fairer test to determine the delay with using libraries (if any), by using Math.abs(), as pow() and log() take time to calculate anyway. The results still show a delay but it is infinitesimal in comparison to that shown above (a few ms for 10million iterations). </EDIT>