[Freeciv-Dev] Re: Priority queue for Dijkstra
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
Gregory Berkolaiko wrote:
Hi Jason,
On Sat, 16 Mar 2002, Jason Short wrote:
Gregory Berkolaiko wrote:
quicksort is fast - O(n log n) in the average case, with a *small*
constant factor (compared to other n log n sorts); the drawback is that
it can be O(n^2) in the worst case (when everything is in the exact
wrong position). What the "wrong position" is depends on the
implementation of the quicksort; the standard qsort() function probably
avoids the most likely cases.
Mmm, the one on my computer seems to be broken. I sort an array, than
apply compare function to few neighbours and it changes sign!
Or maybe my head is broken...
I've gotten this behavior when I make a mistake in writing the
comparison function. If this function returns inconsistent comparisons
the resulting sort is garbage.
But, any kind of sort is definitely inferior to a priority queue. A
well-designed queue has a O(log n) insert time, and a small constant
factor. There is little overhead and it is ammortized well. By
contrast, implementing Dijkstra's correctly requires that the list
*always* be sorted, because each element you pop off must be the
smallest one. So to ensure correctness you'd really need to sort the
list *every time you popped an item*.
that's right.
it wasn't very right of me to call it "from time to time".
the easiest alternative is to run find_minimal function, which is O(n).
Ouch. Compared to O(log n), O(n) is awful.
And such will make the full search O(n^2) instead of O(n log n).
The list of priorities for planes can be bounded by map.xsize + map.ysize
but with some potential problems. If SINGLE_MOVE ever goes up from 3
thought, the maximum priority for land move will increase too, so heap
might be a good idea.
A heap is a good idea in any case - especially since such a structure
has already been implemented, has it not? Can't you just use the
existing priotiry queue class?
where is _the_ existing priority queue class?
are you talking about
add_to_mapqueue
get_from_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
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.)
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.
As a side note, I though planes ignored SINGLE_MOVE and just took 1 unit
of movement per tile?
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.
jason
[Freeciv-Dev] Re: Priority queue for Dijkstra, Raimar Falke, 2002/03/16
|
|
