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

[Renaud De Landtsheer]

Le 2/05/2014 12:20, Peter K a écrit :
> > 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 ...

Right, I just found some source code

Forget about that.

>
> 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
>>
>
>
> _______________________________________________
> GraphHopper mailing list
> GraphHopper at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/graphhopper


-- 
*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/507270eb/attachment.html>