[Haskell-cafe] A tale of Project Euler
daniel.is.fischer at web.de
Fri Nov 30 10:49:49 EST 2007
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.
More information about the Haskell-Cafe