On Tuesday 02 February 2010 23:54:58 Richard O'Keefe wrote: > I understood the ""simple but not scalable and not particularly fast" > claim *NOT* as a claim about imperative languages but in context as > a claim about using two-dimensional arrays of booleans to implement > Conway's Life.
Fair enough. If you want to model either an infinite board or a very sparse one then a sparse data structure will be asymptotically faster. But they won't be simpler and asymptotically efficient mutable data structures will be faster again. > 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. -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
