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]
Cc: freeciv-dev@xxxxxxxxxxx
Subject: [Freeciv-Dev] Re: Priority queue for Dijkstra
From: Jason Short <vze2zq63@xxxxxxxxxxx>
Date: Sat, 16 Mar 2002 14:06:52 -0500
Reply-to: jdorje@xxxxxxxxxxxx

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

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

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.



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