<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<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>
<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>
</body>
</html>