Re: Which is faster - hash or array lookup
- From: xhoster@xxxxxxxxx
- Date: 26 Jan 2009 21:57:41 GMT
Rasmus Villemoes <burner+usenet@xxxxxxxxx> wrote:
bugbear <bugbear@xxxxxxxxxxxxxxxxxxxxxxxxx> writes:
Rasmus Villemoes wrote:
Hi
In a program I'm writing, I will need to access the 53130 different
5-element subsets of 0..24 many many times.
Are you sure there isn't a better algorithm for your (unstated)
purpose?
Well, that depends. I am suite sure that perl is not The Right Tool
for my overall purpose, but what I am trying to do probably does
involve accessing each of these combinations by number (or some other
key). I have decided to use perl for this pet project to help me learn
some more perl.
Well in that case, what I'd do (and have done) is implement them in several
different ways, run them, and compare the timings. It will teach you a lot
of Perl, especially those ineffable things hard to put into documentation
or USENET posts.
The project concerns a little game which is played on a 5x5
board. Each player has 5 pieces, and additionally there is a common
piece used by both players. Only one piece can occupy a square at any
time, so the positions of either player's pieces at any time is
exactly a 5-subset of 0..24. If I use a canonical numbering of these
5-subsets, I can describe the state of the game using 5 bytes (2*2
bytes to describe numbers in the range 0..53129, and 1 byte to
indicate the position of the common piece along with information on
whose turn it is).
Your scheme allows impossible boards, because some combinations of the
two players combinations (or one of them and the common piece) will be
incompatible. Couldn't you canonicalize at entire-board level, rather than
at each player individually?
For any given state, a move from that state can be
described by 3 bytes (encoding the new positions of the player's
pieces and the common piece).
Why would you want to scrimp on space here? Are you planning on storing
all possible moves from all possible boards in memory simultaneously? I'd
probably just plan on recomputing possible moves on the fly, rather than
storing, and so wouldn't care about storage space for this.
But in order to compute which moves are
possible from a given state, I need the positions of the 11 pieces on
the board. It may not be smart to store anonymous arrays containing
the 5-subsets. Another possibility is to use a bitstring with exactly
5 1's. That would probably save a lot of memory, and may be faster to
use (I will often need to ask "in state $x, is there a piece on square
number $n". I guess vec() can answer that question if I use
bitstrings, whereas traversing an array looking for $n is slow).
You can use a sparse array, checking defined $x[$n] rather than
grep $_==$n, @x, just like you can a sparse vector. Although I'd usually
use a hash for that purpose instead of an array. But if I'm understanding
this right, this choice is at a different level than the one you originally
asked.
Of course, I could skip the huge constant table, but then I would
either have to describe each state using more data, or compute the
occupied/empty squares each time.
The CPU still has to compute it each time, it is just a matter of how you
go about getting it to do so. It seems like you will have to go in both
directions rapidly, canonical->board->different board->canonical. Unless
you have something especially clever in mind, I'd think it would be less
work to go from human-readable-string-representation of board to
array/hash-representation of the board, then from some abstruse canonical
number to an array/hash representation. (And back)
Xho
--
-------------------- http://NewsReader.Com/ --------------------
The costs of publication of this article were defrayed in part by the
payment of page charges. This article must therefore be hereby marked
advertisement in accordance with 18 U.S.C. Section 1734 solely to indicate
this fact.
.
- Follow-Ups:
- Re: Which is faster - hash or array lookup
- From: Rasmus Villemoes
- Re: Which is faster - hash or array lookup
- References:
- Which is faster - hash or array lookup
- From: Rasmus Villemoes
- Re: Which is faster - hash or array lookup
- From: bugbear
- Re: Which is faster - hash or array lookup
- From: Rasmus Villemoes
- Which is faster - hash or array lookup
- Prev by Date: Re: How to remove a module from CPAN?
- Next by Date: Re: inputting the ephemerides
- Previous by thread: Re: Which is faster - hash or array lookup
- Next by thread: Re: Which is faster - hash or array lookup
- Index(es):
Relevant Pages
|
