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: freeciv-dev@xxxxxxxxxxx
Subject: [Freeciv-Dev] Re: Priority queue for Dijkstra
From: Jason Short <vze2zq63@xxxxxxxxxxx>
Date: Sat, 16 Mar 2002 13:33:49 -0500
Reply-to: jdorje@xxxxxxxxxxxx

Gregory Berkolaiko wrote:
On Sat, 16 Mar 2002, Jason Short wrote:
where is _the_ existing priority queue class?
are you talking about add_to_mapqueue
routines? They are just priority-indexed arrays of LILO queues (with a weird implementation). This is a solid O(1) solution, unless you have too many indices.

Ahh, I see. So you're saying this "priority queue" will degrade badly as the number of possible priorities increases. (If you have a limited

precisely.  I can't really say it will degrade badly though...

number of keys, you don't need to worry about quicksort. You can just do a bucket sort, which is O(n), and corresponds with what you describe for add_to_mapqueue/get_from_mapqueue.)

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.

The solution is to either convert add_to_mapqueue/get_from_mapqueue to be a "real" priority queue, or write a new priority queue, or (best choice) find some library implementation of a priority queue.

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?

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/

In the SINGLE_MOVE sentence I was talking about land move.
The idea is that if you make railroads cost 1/10, the number of possible movecosts will be multiplied by 10 !

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'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.

So what I'm saying is, the "optimization" of using buckets for the queue may or may not actually make things faster.


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