[GraphHopper] contraction: what is the complexity of Treemap.getSize?

[Renaud De Landtsheer]

Hi Peter,

In the contractNodes() method of the contractor of GH, there is a 
snippet of code that rises a question to me. It is the snipped related 
to lazy updates. The snipped is here below:

if (sortedNodes.getSize() < lastNodesLazyUpdates){
     lazySW.start();
     wn.priority = calculatePriority(wn.node);
     ....
     lazySW.stop();
}

I am not quite sure that sortedNodes.getSize() has a good complexity of 
O(1).
I fear it is actually O(n); the documentation of Java is not clear on 
that point.

If this is indeed the case that it has a O(n) complexity, you might be 
interested in replacing the condition with something simpler relying on 
the "level" variable that is also maintained throughout the contraction 
process and would, for sure, cost O(1) to evaluate.

My friday's two cents.

-- 
*Renaud De Landtsheer, Ir, Phd*
Senior R&D Expert
CETIC
Rue des Frères Wright, 29/3
B-6041 Charleroi
Phone: +32 71 490 754


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20140502/2076865f/attachment.html>