in reply to Re: 2D Arrays as a Gameboard
in thread 2D Arrays as a Gameboard

I'd actually use a single hash here to save space: 

my %grid;
keys %grid= 11*11;    # preallocate our hash size
for my $x(-5..5) {
    for my $y(-5..5) {
        $grid{$x,$y} = "co-ords x:$x, y:$y";
    }
}

[download]
Also note that you either need to remove the "->"s from your code or change "my %grid" to "my $grid".

        - tye (but my friends call me "Tye")

Replies are listed 'Best First'.
Re: (tye)Re: 2D Arrays as a Gameboard
by tachyon (Chancellor) on Jun 06, 2001 at 23:26 UTC

    Good point, in my examples $grid, $grid1 and $grid2 store refs to the data structure not %grid....Damn sloppy. I will take the liberty of fixing the code if that's OK

    I love the economy of $grid{$x,$y} to give keys like "0.-1"- very neat. Q: How much space does it save over and above the 11 unnecessary keys (121 hash keys - all in one hash in your case and in 132 in 12 hashes in mine). Or to put it another way how big is the memory penalty in setting up each extra anon hash?

    Also can you explain the purpose of the preallocation? No doubt it is an efficiency measure but does it commit to a set board size? If not why do we need it as we are about to allocate values to all the keys.

    cheers

    tachyon

[reply]

      Well, each hash has an overhead. This isn't that much but if you end up only putting 11 items in, then percentage-wise it isn't trivial. Also, with 11 items, each hash should end up with 16 buckets. With 121 items, my hash should have 128 buckets (versus 176). So it isn't a huge win.

      You updated your node to use something like $grid{$x}{$y}{item}. Here the space savings of $grid{$x,$y,$item} could be even greater, though it also illustrates the main problem with this technique: You can no longer use $grid{$x}{$y}, for example, to pass to a subroutine that wants to just use $_[0]{item}, $_[0]{other}.

      Without the preallocation, the hash would start out with 8 buckets, then grow to 16, then 32, then 64, then 128. Since this is one of those case where we know exactly how many items we plan to store, we can save time and some memory fragmentation by just jumping to 128 buckets at the start. This doesn't stop you from adding fewer or more items; the hash will still grow further if it needs to. This will only very rarely make much difference, however. I threw it in since I was specifically thinking about the memory impact of the data structure at the time.

      The real point is that you probably have no use for $grid{$x}. That is, unless the game does a lot of manipulations to one row at a time. But then, if it also does work on one column at a time, then optimizing the row case may not be worth the effort.

      Most of the time you are better off just ignoring this type of stuff. You can waste a lot of thought and time trying to preoptimize your data structures and code. (:

              - tye (but my friends call me "Tye")
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom