[Haskell-beginners] Re: [Haskell-begin] Maximum of a List?
daniel.is.fischer at web.de
Mon Jul 28 15:11:11 EDT 2008
Am Montag, 28. Juli 2008 18:15 schrieb Niels Aan de Brugh:
> Steve Klabnik wrote:
> > I think you're onto something with the Int/Integer thing....when using
> > a type signature of "Integer", "f 1 113383" gives "248" immediately.
> > Compiling and running the code with "Integer" types on my home machine
> > yields "525".... which Euler says isn't the right answer?
> Because you're not providing the right number. :-)
> > Also, on the strictness annotations: Do you put them in the type
> > declaration? Or in the pattern match on the lhs of the declaration?
> I've tested your code with strictness annotations and it appears to not
> make a difference. GHC employs several optimization techniques, one of
> those being strictness analysis, so maybe it is already using a strict,
> unboxed integer.
Using -O2, GHC produces the same core with or without strictness annotations,
the 'acc' parameter of f is an unboxed Int, so the optimiser indeed sees it
is needed. The Integer parameter unfortunately can't be unboxed. A native
64-bit integer type might gain something.
> The real speed-up (a non-linear one) here is not to re-calculate every
> sequence over and over again, but keep it in a map/array (as suggested
> by Rafael and me).
Using a Map, though easier to code, doesn't buy you much here, indeed less
than a few easy considerations where the maximal length cannot occur. The
problem is that you have to update the Map often, which is rather costly,
also the Map takes a lot of memory. Using an array is more convoluted, but
much faster (if done right).
> I've found some Euler puzzles are impossible to solve
> without this technique.
At least, it would take far longer to get the solution.
> P.S.: If you're really going for speed, compile (not interpret) the code
> (using -O -fvia-C, and there's some more stuff in the manual) using the
> latest greatest version of GHC.
Nowadays, the native code generator is not necessarily slower than -fvia-C,
often faster. So the best should be to test both, -O2 and -O2 -fvia-C
-optc-On, for some medium sized inputs and see which actually is faster.
More information about the Beginners