<div>Well, thanks to all of you.<br></div><div><br></div><div>Daniel<br></div><div><br></div><div class="gmail_quote">2009/4/23 Daniel Fischer <span dir="ltr"><<a href="mailto:daniel.is.fischer@web.de">daniel.is.fischer@web.de</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Am Donnerstag 23 April 2009 14:15:16 schrieb Max Rabkin:<br>
<div><div class="h5">> On Wed, Apr 22, 2009 at 10:38 AM, Daniel K. <<a href="mailto:anmeldemails@gmail.com">anmeldemails@gmail.com</a>> wrote:<br>
> > Dijkstra's algorithm ... relies heavily on mutating arrays<br>
><br>
> Well, the imperative implementation does.<br>
><br>
> > Not mutating the underlying arrays would probably result in poor<br>
> > performance.<br>
><br>
> Indeed. Non-mutable arrays are not very performant for mutations.<br>
> Tree-like data structures Are Your Friend.<br>
><br>
> I've never compared the performance of an ST-based implementation with<br>
> a set/map based algorithm, but I've often found the latter usably<br>
> performant.<br>
<br>
</div></div>I have occasionally, and I can confirm that often set/map based algorithms give quite<br>
usable performance. But usually ST-based implementations are significantly faster.<br>
If the algorithm demands a lot of updates and performance is important, I recommend<br>
sacrificing the ease and elegance of coding with sets/maps for ST's uglier but faster code<br>
(but verify that set/map performance is unsatisfactory first).<br>
<br>
><br>
> --Max<br>
<br>
</blockquote></div><br><div><br></div>