[Freeciv-Dev] Re: freeciv2 kernel,modules and rulesets

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Mon, Dec 03, 2001 at 08:34:24AM -0500, Andrew Sutton wrote:
> On Monday 03 December 2001 08:05 am, Julian Rüth wrote:
> > Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx> writes:
> > >  1) current situation: deref a pointer of the tile and go trough the
> > >  short (<7) list; costs 4 bytes per tile
> > >  2) proposed solution: go through all units (this can be hundreds) and
> > >  select the units you want; costs 0 bytes per tile
> 
> dear god no! give me some credit ;)
> 
> > >
> > > We can afford these 4 bytes per tile. Max size is 200x100 ==
> > > 200*100*4=80k.
> > >   Raimar
> >
> > I don't think this is a real problem. Just put all the units in some kind
> > of tree (ordered by x and y positions) so it costs only something like
> > O(lgn). Jule
> 
> closer... i was thinking of a map that stored some informatic structure about 
> the tile. it could be keyed on the x,y coordinate of the tile. if nothing's 
> on the tile, there's no associated key in the map. it's a constant time 
> lookup and hashtables _are_ built for sparsely populated arrays :)

And with 4 extra bytes we need only one (exactly one) memory access
(which is quite constant to me).

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "USENET is *not* the non-clickable part of WWW!"