[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:
On Sat, 16 Mar 2002, Jason Short wrote:
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
n is up 100 I think.
I'm going to make a wild guess and speculate that the "standard" prioity
queue implementation will be significantly faster than the current one,
because its more effective memory usage promotes cache hits. That's
*if* we use an implementation where we don't have to malloc/free on
Of course, data will be needed to back this up.
So what I'm saying is, the "optimization" of using buckets for the queue
may or may not actually make things faster.
It is easier to experiment than guess, I think...
I will try to write both and then compare.
[Freeciv-Dev] Re: Priority queue for Dijkstra, Raimar Falke, 2002/03/16