On Fri, 30 Nov 2007, Daniel Fischer wrote: > Am Freitag, 30. November 2007 14:39 schrieb Henning Thielemann: > > > Is this thread still about the prime sieve? As I mentioned, I think one > > can avoid the mutable array, because if there is only a small number of > > array updates with much changes per update, it should be efficient enough > > to copy the array per update. > > I think in this case it's far less efficient than in-place update. Consider > sieving primes up to 10^7, there are 446 primes with p^2 < 10^7, so you would > have over 400 array updates. Even if you leave out the even numbers, an array > going up to 10^7 would require some 800 KB memory (each odd number one bit), > so overall, you'd allocate well over 300 MB (not at once, of course).
"not at once" - that's the point. With some luck there are only two pieces of memory where the data is copied back and forth. It's obviously not the most efficient solution, but a non-monadic solution. _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
