[Haskell-cafe] A tale of Project Euler

[Daniel Fischer]

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). Using 
an STUArray runs easily within 1MB allocated once. 
And why avoid mutable arrays in the first place?
What's bad about 
thing = runSTUArray (do work)?
Granted, "work" tends to be far less elegant code than list comprehensions &c, 
but also much faster.

Cheers,
Daniel