[FreecivDev] Re: Priority queue for Dijkstra
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
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
get_from_mapqueue
routines? They are just priorityindexed 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
(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?
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.
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.
jason
 [FreecivDev] Priority queue for Dijkstra, Gregory Berkolaiko, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Jason Short, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Gregory Berkolaiko, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Jason Short, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Gregory Berkolaiko, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra,
Jason Short <=
 [FreecivDev] Re: Priority queue for Dijkstra, Gregory Berkolaiko, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Jason Short, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Raimar Falke, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Raimar Falke, 2002/03/16

