[Freeciv-Dev] Re: curiosity

[Andrew Sutton <ansutton@xxxxxxx>]

On Saturday 01 December 2001 06:27 pm, Justin Moore wrote:
>    Having spent a lot of time fiddling with the list operator in freeciv,
> I'm going to have to disagree with this.  Freeciv does *very* few
> searches, and lots and lots of simple iterations over all elements.
> Either that or it searches for all elements in a list that meet property
> X.  I actually went through at one point and rewrote the list data
> structure, and added a sortlist data structure.  The speed gains were
> negligable, even on a very large all-AI game.

it doesn't matter though. average search time of a list will still be O(n/2) 
- at least iteratively. even if the lists are small, and i'm sure they are, 
the iterations WILL add up. i'm not saying this to be critical of existing 
code, it's just a fact and a reason to maps where lots of lookups are 
required.

andy