[Freeciv-Dev] Re: Warmap

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Tue, 13 Aug 2002, Vasco Alexandre Da Silva Costa wrote:

> On Tue, 13 Aug 2002, Gregory Berkolaiko wrote:
> 
> > On Mon, 12 Aug 2002, Vasco Alexandre Da Silva Costa wrote:
> >
> > > Regarding warmap speedups:
> > >
> > > If anyone feels up to implementing them, there are some algorithms which
> > > promise to solve the single-source problem:
> > > <http://www.boost.org/libs/graph/doc/graph_theory_review.html>
> > >
> > > in linear time for undirected planar graphs:
> > > <http://mathworld.wolfram.com/PlanarGraph.html>.
> > >
> > > IIRC Dijkstra takes quadratic time in our implementation.
> >
> > Yes I did some research on it previously, in particular read the papers by
> > Thorup and Goldberg that you are referring to below.  Some of the
> > algorithms you mention are not applicable to our case which is non-planar
> > graph with non-negative (rather than strictly positive) weights.
> 
> Argh... silly me, only now that you mentioned it i noticed the graph has
> edges that cross. I had noticed that Thorup's paper was only for positive
> weights, i put it mostly as reference, hence why i placed the link to the
> planar graph algorithm first (which seemingly doesn't apply here either,
> doh!).
> 
> > Besides AFAIU the current implementation _is_ linear, at least in the
> > sense that Thorup's algorithm is linear (his discovery was that you can
> > pile nodes into a bucket list even though your weights are not integers --
> > this is already done in the current warmap).  My own empirical discovery
> > was that if in our case you go for priority queue (log(n) time) rather
> > than for bucket list (constant time) you get a speed-up: the bucket list
> > is too expensive to set up for the small $n$ we usually get.
> 
> Hmmm... Ok. So on your optimization you use a heap instead? (log(n) time
> suggests some tree structure).
> 
> Did you benchmark it after several runs? Glancing at it it seems to me
> that it only does those nasty mallocs() once, afterwards memory is fetched
> from a pool.

Well, I didn't tell you the whole truth I guess :)
I implemented both the bucket list and the heap in my own version of 
warmap.  One of the features of this map was that it wasn't static 
anymore and the bucket list was private to the map hence the need for 
reallocation over and over again.

Still, I wouldn't be surprised if the heap outperformed even current 
(static) bucket list, since the length of the queue is usually small.  
I didn't try it though.

G.