[Freeciv-Dev] Re: curiosity

[Justin Moore <justin@xxxxxxxxxxx>]

> > First: searching a list of 10 players isn't slow. Complexity kicks in
> > latter.
>
> no, but searching a list of a couple thousand is - well, relatively :)
> besides, all those O(n/2) operations add up after a while and do affect game
> performance in the long run.

   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.

> > Second: we have also hashs. See common/game:struct unit
> > *find_unit_by_id(int id) and struct city *find_city_by_id(int id);
>
> cool. i never saw that. all the code i looked at used lists.

   Most of the hashes are used when loading or saving a game.  Some lists
within a game can reach 8000+ elements, but only during saving and loading
a game.

-jdm

Department of Computer Science, Duke University, Durham, NC 27708-0129
Email:  justin@xxxxxxxxxxx