[Haskell-cafe] A tale of Project Euler
Daniel Fischer
daniel.is.fischer at web.de
Thu Nov 29 16:23:37 EST 2007
Am Donnerstag, 29. November 2007 19:43 schrieb Andrew Coppin:
> Daniel Fischer wrote:
> > One thing: since You check the array bounds, the system needn't check
> > them again, use unsafeWrite and unsafeRead. And use Int for the index,
> > that would be MUCH faster.
>
> I can't find the functions you're talking about.
As Sebastian already said, they're in Data.Array.Base, sorry, should've
mentioned that.
> I have however changed
> the index type. (Make little or no noticable speed difference. But then,
> it's already pretty damn fast in the first place...)
>
But it can be considerably faster. On my 5 yo 1200MHz thing, I can sieve up to
10 million in less than half a second:
dafis at linux:~/Documents/haskell/move> time ./Sieve2 10000000
664579
real 0m0.419s
user 0m0.420s
sys 0m0.000s
And that's even faster than any sieve in C that I managed to write.
(Okay, I don't know how to use bitsets in C, that might beat Haskell)
> > Another thing: you can stop sieving when p*p > size, another speedup
>
> Saves a few hundred milliseconds.
Which is pretty much for a programme running below 1 second.
>
> > Fifth thing: better use an STUArray, don't drag IO in if it's not
> > necessary.
>
> I don't understand the ST monad.
Nor do I. Just use it (and be prepared to use scoped type variables).
>
> >> The obvious downside of course is that you must know how big
> >> to make the array at the start of your program, and you must compute the
> >> entire array before you can use any of it. Both limitations not precent
> >> in the lazy recursive list implementation...
> >
> > The size of the array can easily be estimated by the prime number
> > theorem,
>
> Probably. But it doesn't compare to the elegance and simplicity of being
> able to generate an arbitrary number of primes on an as-needed basis.
True. But when speed matters, you have to bite the bullet.
And if you don't know up to which bound you need the primes, but know it's a
not too low bound, you can sieve the first part in an array and then go on
using a list, that's what I do.
>
> > Keep enjoying Project Euler,
> > Daniel
>
> Well, I don't know about "enjoy" - generally I just find it quite
> frustrating. It's kind of addictive trying to increase your score
> though... (Anybody here reached 100% yet?)
int-e (Bertram Felgenhauer, I believe), well he has not yet solved last
week's, so currently he's at 99%, and there were a couple of others but they
didn't persevere.
>
> I find that a lot of the problems don't seem to involve much math.
> (E.g., "here is some data, process it into a list of integers, find the
> highest one". Where is the deep mathematics in that?) A few of them do,
> but a lot are simply to do with prime numbers, and as far as I'm away,
> it is impossible to know anything about prime numbers. In other words,
> you must compute them all the hard way.
>
Some of the problems require little math, but more programming techniques.
Others require a good grip of maths to find an efficient algorithm. Really
deep maths can't be required, the site is not meant for professional
mathematicians but for laypeople with mathematical interest.
The aim is to make brute force unattractive (brute forcing times from 5 hours
upwards), while a mathematical insight will often give the solution in a few
nanoseconds.
Many problems require both, some maths to find a good algorithm, and some
programming techniques to make it run really fast.
Cheers,
Daniel
More information about the Haskell-Cafe
mailing list