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: jdorje@xxxxxxxxxxxx
Cc: freeciv-dev@xxxxxxxxxxx
Subject: [Freeciv-Dev] Re: Priority queue for Dijkstra
From: Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>
Date: Sat, 16 Mar 2002 18:57:33 +0000 (GMT)

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.


> > Found it.  The next question: where should I declare the new file 
> > ( 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 
>   In the latter, you'll need to add the file somewhere in common/, then 
> add it to common/

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.


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