[Freeciv-Dev] Re: Priority queue for Dijkstra

[Jason Short <vze2zq63@xxxxxxxxxxx>]

Gregory Berkolaiko wrote:
> On Sat, 16 Mar 2002, Jason Short wrote:
> > It's easy enough to say that O(n) is better than O(n log n), but this 
> > isn't necessarily true.  For the type of numbers we're talking about log 
> > n is quite small, and constant factors are likely to make more of a 
> > difference.
> n is up 100 I think.
Right...

I'm going to make a wild guess and speculate that the "standard" prioity 
queue implementation will be significantly faster than the current one, 
because its more effective memory usage promotes cache hits.  That's 
*if* we use an implementation where we don't have to malloc/free on 
every entry.
Of course, data will be needed to back this up.

> > So what I'm saying is, the "optimization" of using buckets for the queue 
> > may or may not actually make things faster.
> It is easier to experiment than guess, I think...
>
> I will try to write both and then compare.
Sweet.

jason