[Haskell-cafe] Game of life in haskell.
dot at dotat.at
Tue Feb 2 16:23:02 EST 2010
On Tue, 2 Feb 2010, Serguey Zefirov wrote:
> Creation of new Array is (without knowing some subtle details) is
> O(max coordinates difference between live cells). Creation of new Set
> (X,Y) is O(NlogN) (N = number of live objects). Most of the cells in
> Life are empty, so the Set/Map approach is faster. Also it leads to
> very concise code.
I have a small and relatively quick Life algorithm that's based on lists,
so it should translato to Haskell quite nicely.
The basic representation of the Life universe is a sorted list of the
co-ordinates of live cells. You can compute a new generation in one scan
of the list, or rather a kind of zip3 that scans a 3x3 box along three
adjacent rows, skipping empty space. It's much faster if, instead of
storing one live cell in each list element, you store a small word-sized
bitmap. You can then use SIMD-within-a-register to combine the three rows
of cells and emit a new bitmap if it is non-zero.
Have a look at http://dotat.at/prog/life/life.html for the story of how I
developed the algorithm, including C source (about 40 lines of code).
I've written a couple of other articles about SWAR techniques for Life:
Getting the bits onto the screen quickly is the hardest part :-)
f.anthony.n.finch <dot at dotat.at> http://dotat.at/
GERMAN BIGHT HUMBER: SOUTHWEST 5 TO 7. MODERATE OR ROUGH. SQUALLY SHOWERS.
MODERATE OR GOOD.
More information about the Haskell-Cafe