[Freeciv-Dev] Re: Priority queue for Dijkstra
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
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
> > (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?
no, just another tiny file that I stole somewhere.
> 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.
> >>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
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.
[Freeciv-Dev] Re: Priority queue for Dijkstra, Raimar Falke, 2002/03/16