On 3 Feb 2010, at 02:04, Jon Harrop <j...@ffconsultancy.com> wrote:
On Tuesday 02 February 2010 23:54:58 Richard O'Keefe wrote:
One message in this thread has already pointed to a
solution (in C) that in effect uses a bit-packed sparse
representation
to achieve high speed. The point is that that approach takes time
(and
space) per generation proportional to the number of occupied cells,
not the size of the space, and that is the basis of the "scaling"
claim.
A simple Haskell analogue, which has the right asymptotic cost, would
be to represent a Life generation by a list of
(row_number, [col_no, ..., col_no])
pairs in strictly ascending order of row number, where each pair
contains a list of the numbers of the occupied columns in strictly
ascending order. The space is (number of occupied cells * a
constant)
+ (number of occupied rows * another constant). Computing the next
generation then amounts to a bunch of 3-way merges.
That will be a lot faster than using Map or Set but you're still
paying a lot
for the indirections between cons cells. Mutating an array in-place
would be
significantly faster and no more difficult to code correctly because
this is
such a trivial algorithm.
Richard's description is pretty much exactly what I had in mind for a
Haskell version of my C code. The C translates to Haskell so well
because its data structure is immutable: the new generation is written
to fresh memory then the old generation becomes garbage. The old
generation is scanned in the order it is written (albeit by three
pointers with a row between each one) which is inconvenient for linked
lists. However the algorithm is symmetrical so it doesn't mind
processing the universe in alternating directions, so long as the
rendering code can cope :-) The indirections are less bad than they
might be because the code will always be following a pointer to an
adjacent memory location, because of the algorithm's simple allocation
behaviour. But it'll be about twice as slow as the C equivalent
because it uses twice the memory.
Efficient mutate-in-place Life algorithms become disgustingly
complicated before they can beat listlife.
Tony.
--
f.anthony.n.finch <d...@dotat.at> http://dotat.at/
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
