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: http://fanf.livejournal.com/81169.html http://fanf.livejournal.com/93032.html Getting the bits onto the screen quickly is the hardest part :-) Tony. -- f.anthony.n.finch <d...@dotat.at> http://dotat.at/ GERMAN BIGHT HUMBER: SOUTHWEST 5 TO 7. MODERATE OR ROUGH. SQUALLY SHOWERS. MODERATE OR GOOD. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
