Complete.Org: Mailing Lists: Archives: freeciv-dev: March 2002:
[Freeciv-Dev] Re: Priority queue for Dijkstra

[Freeciv-Dev] Re: Priority queue for Dijkstra

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>
Cc: freeciv-dev@xxxxxxxxxxx
Subject: [Freeciv-Dev] Re: Priority queue for Dijkstra
From: Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>
Date: Sat, 16 Mar 2002 20:00:18 +0100
Reply-to: rf13@xxxxxxxxxxxxxxxxxxxxxx

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.


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

[Prev in Thread] Current Thread [Next in Thread]