[Freeciv-Dev] Re: Priority queue for Dijkstra

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Sat, 16 Mar 2002, Jason Short wrote:

> Gregory Berkolaiko wrote:
> > I am not sure where n is coming from.  Each queue is LILO, no sorting 
> > invloved.  And each new piece of data comes with the number of the queue 
> > it wants to be put in.
> 
> O(n) is the time for a bucket sort.  The corresponding time for a 
> "bucket priority queue" would be O(1) for both insert and remove.

m'kay

> > Found it.  The next question: where should I declare the new file 
> > (configure.in or somewhere else) ?
> 
> Is this an external library (in which case you'll have to fight purists 
> who want as little requirements as possible), or are you importing the 
> library file?

no, just another tiny file that I stole somewhere.

> In the former case, you'll need a check for the library in configure.in. 
>   In the latter, you'll need to add the file somewhere in common/, then 
> add it to common/Makefile.am.

the latter

> >>Yes, I see.  And you're saying this is a problem given the current 
> >>implementation of the priority queue.
> 
> Sounds like the current system should be reworked.

It is quite efficient, but a bit complicated...

> 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.

> 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.

Best,
G.