Tony Finch dot at dotat.at
Tue Feb 2 20:17:57 EST 2010

On 3 Feb 2010, at 02:04, Jon Harrop <jon at ffconsultancy.com> wrote:
> On Tuesday 02 February 2010 23:54:58 Richard O'Keefe wrote:
>>
>> 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  <dot at dotat.at>  http://dotat.at/