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]

 To: freeciv-dev@xxxxxxxxxxx Subject: [Freeciv-Dev] Re: Priority queue for Dijkstra From: Jason Short 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?
```
``` 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.)
```
```
```
```
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

```