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:01:11 -0500
Reply-to: jdorje@xxxxxxxxxxxx

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


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