[Haskell-beginners] Re: [Haskell-begin] Maximum of a List?
Niels Aan de Brugh
nielsadb at gmail.com
Mon Jul 28 17:35:23 EDT 2008
Daniel Fischer wrote:
> 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.
Right. For this puzzle (n up to 1000000) it's quite safe to say an Int64
will never overflow. :-)
I was wondering how the Integer type is implemented. If I were to
implement such a type my first approach would be to keep a list of
digits (and perform calculation like I do by hand). But operations on
Integers are very fast, even on very big numbers, so I guess that's not
the approach taken by the GHC developers. (For example, calculating the
faculties of [1..1000] takes a little under 300ms to perform on my Intel
PC; if I don't pipe to /dev/null it takes about 10s because of all the
digits being printed.)
Having a type like Integer on board makes many of the puzzles on Project
Euler a shoo-in. One of the questions is indeed to calculate the last n
digits of 1000!.
> 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).
The problem with an array is finding a good upper limit. One could of
course copy the whole array if a new upper bound is found, the costs
would amortize over the whole run. Having a really big and sparse array
is no good either (no/bad locality of reference).
Oh well, the puzzle itself definitely isn't worth the effort, but maybe
some custom made heap structure would perform best.
> At least, it would take far longer to get the solution.
Yes, but sometimes the difference is several days vs. a couple of minutes.
> 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.
Interesting. In which release has the back-end been reworked? Does it
work equally well for architectures other than Intel?
More information about the Beginners