[Freeciv-Dev] Re: Priority queue for Dijkstra

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Sat, Mar 16, 2002 at 06:51:36PM +0000, Gregory Berkolaiko wrote:
> On Sat, 16 Mar 2002, Raimar Falke wrote:
> 
> > > The current implementation of priority queue in gotohand.c is actually
> > > O(1) --- as far as I can tell --- due to the limited set of possible
> > > priorities.  But it's a bit ugly.  Maybe there is a standard heap method 
> > > ( heap is O(log(n)) ) somewhere in C or hidden in freeciv code?
> > 
> > None that I know of. I found these (GPLed):
> >     223     864    5646 heap.c
> >      77     356    2206 heap.h
> > 
> > Do you think that a "real" priority queue performance or does it will
> > "only" increase readability?
> 
> Raimar, you been drinking???
> 
> It would definitely increase performance of your goto agent from 
> O(n log(n)) to O(log(n)).

The goto agent was only a requirement for the SMA. It only works for
ground units (and maybe sea units) anyway. I have never done any
profiling (especially in comparison with gotohand.c). So this
potential performance increase is nice but I haven't identified it as
a problem yet. I would be surprised if the goto agent usses more time
that the SMA.

> Compared with the current mapqueue methods it will be inferior I am 
> afraid.  But mapqueue is hardly extendable and priority queue is.
> 
> Readability of the "user" code will not change.  It's the internal 
> representation of mapqueue that is ugly, not the interface.
> 
> Right now I just want my air route-finding to be working.  Later I will 
> try to convert to the best queue.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  The trick is to keep breathing.