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