<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-cite-prefix">Le 2/05/2014 12:20, Peter K a écrit :<br>
</div>
<blockquote cite="mid:5363717D.50206@yahoo.de" type="cite">
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
<div class="moz-cite-prefix">> I am not quite sure that
sortedNodes.getSize() has a good complexity of O(1). <br>
> I fear it is actually O(n); the documentation of Java is
not clear on that point. <br>
<br>
TreeMap.size just accesses the size variable ...<br>
</div>
</blockquote>
<br>
Right, I just found some source code<br>
<br>
Forget about that. <br>
<br>
<blockquote cite="mid:5363717D.50206@yahoo.de" type="cite">
<div class="moz-cite-prefix"> <br>
Peter<br>
<br>
</div>
<blockquote cite="mid:53636FA4.80205@cetic.be" type="cite">
<meta http-equiv="content-type" content="text/html;
charset=ISO-8859-1">
Hi Peter, <br>
<br>
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: <br>
<br>
if (sortedNodes.getSize() < lastNodesLazyUpdates){<br>
lazySW.start();<br>
wn.priority = calculatePriority(wn.node);<br>
....<br>
lazySW.stop();<br>
}<br>
<br>
I am not quite sure that sortedNodes.getSize() has a good
complexity of O(1). <br>
I fear it is actually O(n); the documentation of Java is not
clear on that point. <br>
<br>
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. <br>
<br>
My friday's two cents. <br>
<br>
<div class="moz-signature">-- <br>
<table cellspacing="0" width="400">
<tbody>
<tr>
<td colspan="2" style="border-left: 1px solid rgb(0,
102, 0); background-color: rgb(255, 255, 255);
font-family: arial; font-style: normal; font-variant:
normal; font-weight: normal; font-size: 14px;
line-height: normal; font-size-adjust: none;
font-stretch: normal; vertical-align: top;"> <b>Renaud
De Landtsheer, Ir, Phd</b> </td>
</tr>
<tr>
<td colspan="2" style="border-left: 1px solid rgb(0,
102, 0); background-color: rgb(255, 255, 255);
font-family: arial; font-style: italic; font-variant:
normal; font-weight: normal; font-size: 14px;
line-height: normal; font-size-adjust: none;
font-stretch: normal; vertical-align: top;">Senior
R&D Expert</td>
</tr>
<tr>
<td colspan="2" style="border-left: 1px solid rgb(0,
102, 0); background-color: rgb(255, 255, 255);
font-family: arial; font-style: normal; font-variant:
small-caps; font-weight: normal; font-size: 14px;
line-height: normal; font-size-adjust: none;
font-stretch: normal; vertical-align: top;"> CETIC <br>
Rue des Frères Wright, 29/3 <br>
B-6041 Charleroi <br>
Phone: +32 71 490 754 </td>
</tr>
<tr>
<td colspan="2" style="border-top: 1px solid rgb(0, 102,
0); background-color: rgb(255, 255, 255); font-family:
arial; font-style: italic; font-variant: normal;
font-weight: normal; font-size: 12px; line-height:
normal; font-size-adjust: none; font-stretch: normal;
vertical-align: top;" align="top"><br>
</td>
</tr>
</tbody>
</table>
</div>
</blockquote>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
GraphHopper mailing list
<a class="moz-txt-link-abbreviated" href="mailto:GraphHopper@openstreetmap.org">GraphHopper@openstreetmap.org</a>
<a class="moz-txt-link-freetext" href="https://lists.openstreetmap.org/listinfo/graphhopper">https://lists.openstreetmap.org/listinfo/graphhopper</a>
</pre>
</blockquote>
<br>
<br>
<div class="moz-signature">-- <br>
<table cellspacing="0" width="400">
<tbody>
<tr>
<td colspan="2" style="border-left: 1px solid rgb(0, 102,
0); background-color: rgb(255, 255, 255); font-family:
arial; font-style: normal; font-variant: normal;
font-weight: normal; font-size: 14px; line-height: normal;
font-size-adjust: none; font-stretch: normal;
vertical-align: top;"> <b>Renaud De Landtsheer, Ir, Phd</b>
</td>
</tr>
<tr>
<td colspan="2" style="border-left: 1px solid rgb(0, 102,
0); background-color: rgb(255, 255, 255); font-family:
arial; font-style: italic; font-variant: normal;
font-weight: normal; font-size: 14px; line-height: normal;
font-size-adjust: none; font-stretch: normal;
vertical-align: top;">Senior R&D Expert</td>
</tr>
<tr>
<td colspan="2" style="border-left: 1px solid rgb(0, 102,
0); background-color: rgb(255, 255, 255); font-family:
arial; font-style: normal; font-variant: small-caps;
font-weight: normal; font-size: 14px; line-height: normal;
font-size-adjust: none; font-stretch: normal;
vertical-align: top;">
CETIC <br>
Rue des Frères Wright, 29/3 <br>
B-6041 Charleroi <br>
Phone: +32 71 490 754 </td>
</tr>
<tr>
<td colspan="2" style="border-top: 1px solid rgb(0, 102, 0);
background-color: rgb(255, 255, 255); font-family: arial;
font-style: italic; font-variant: normal; font-weight:
normal; font-size: 12px; line-height: normal;
font-size-adjust: none; font-stretch: normal;
vertical-align: top;" align="top">
<p><br>
</p>
</td>
</tr>
</tbody>
</table>
</div>
</body>
</html>