[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:
> > 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.
Mmmm, cannot see what's wrong with the function.
Here it is:
static int list_cmp_function(const void *value1, const void *value2)
const struct refuel *point1 = (const struct refuel *) value1;
const struct refuel *point2 = (const struct refuel *) value2;
return (MAX_FLIGHT * (point1->turns - point2->turns)
- (point1->moves_left - point2->moves_left));
Oh well, anyway I'm not going to use qsort.
> > 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.
Depends on n, really ;)
> > 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
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.
> 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
(configure.in or somewhere else) ?
> > 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.
[Freeciv-Dev] Re: Priority queue for Dijkstra, Raimar Falke, 2002/03/16