[Haskell-beginners] Re: [Haskell-begin] Maximum of a List?

[Daniel Fischer]

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.
>
> Niels
>
> 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.

Cheers,
Daniel