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

[Peter K]

> 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.

TreeMap.size just accesses the size variable ...

Peter

> 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/695765c7/attachment.html>