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.