[Freeciv-Dev] Re: Priority queue for Dijkstra

[Jason Short <vze2zq63@xxxxxxxxxxx>]

Gregory Berkolaiko wrote:
> On Sat, 16 Mar 2002, Jason Short wrote:
> > > where is _the_ existing priority queue class?
> > > are you talking about 
> > >  add_to_mapqueue
> > >  get_from_mapqueue
> > > routines?  They are just priority-indexed arrays of LILO queues (with a 
> > > weird implementation).  This is a solid O(1) solution, unless you have too many indices.
> > Ahh, I see.  So you're saying this "priority queue" will degrade badly 
> > as the number of possible priorities increases.  (If you have a limited 
> precisely.  I can't really say it will degrade badly though...
>
>
> > number of keys, you don't need to worry about quicksort.  You can just 
> > do a bucket sort, which is O(n), and corresponds with what you describe 
> > for add_to_mapqueue/get_from_mapqueue.)
> 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.
> > The solution is to either convert add_to_mapqueue/get_from_mapqueue to 
> > be a "real" priority queue, or write a new priority queue, or (best 
> > choice) find some library implementation of a priority queue.
> 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?
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.
> > > In the SINGLE_MOVE sentence I was talking about land move.
> > > The idea is that if you make railroads cost 1/10, the number of possible 
> > > movecosts will be multiplied by 10 !
> > 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'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.
So what I'm saying is, the "optimization" of using buckets for the queue 
may or may not actually make things faster.
jason