[Haskell-beginners] What's the difference between those two solution?

[Brent Yorgey]

On Tue, Dec 13, 2011 at 11:49:03AM +0800, Haisheng Wu wrote:
> Hello,
>   I'm trying to solve Euler problem 104 with the solution "My Solution"
> below but it takes quite long time therefore I quite.
>   Then I turn to haskell wiki for better solution which work well but I can
> not figure out why it is better than mine.
>   I'm wondering whether more function call decrease the performance.
> 
>   Could you please help a little?
>   Thank you.
> 
> *-- | My Solution *
> main = print $ snd $ head $ dropWhile (\(x,y) -> (not . bothNinePandigit
> "123456789") x) (zip fibs [1..])
> 
> bothNinePandigit digits n = isFirstNinePandigit digits n &&
> isLastNinePandigit digits n
> 
> isLastNinePandigit  digits n = digits == sort (lastDigits 9 n)
> isFirstNinePandigit digits n = digits == sort (firstDigits 9 n)
> 
> firstDigits k n = take k (show n)
> lastDigits  k n = show (n `mod` 10^k)
> 
> fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
> 
> *-- | From Haskell Wiki *
> fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
> 
> isFibPan n =
>   let a = n `mod` 1000000000
>       b = sort (show a)
>       c = sort $ take 9 $ show n
>   in  b == "123456789" && c == "123456789"
> 
> ex_104 = snd $ head $ dropWhile (\(x,y) -> (not . isFibPan) x) (zip fibs
> [1..])

Aha, this is sneaky!  

Having a bunch of function calls should not make
a difference if you are compiling with -O2 (you are compiling with
-O2, aren't you)?  Nonetheless, even compiling with -O2 I was also
getting the results you mention -- the wiki version was pretty fast
(about 24s) whereas your version took more than 15 minutes.

So I ran your version with profiling to help figure out what was going
on.  I compiled with

  ghc --make -O2 -prof -auto-all -rtsopts PE104.hs

and then ran with

  ./PE104 +RTS -p -RTS

This causes a file "PE104.prof" to be written which has a bunch of
data on execution time and allocation broken down by function. The
results showed that 95% of the program's run time was being spent in
'firstDigits'.

And then it hit me -- the difference is due to the fact that your
version and the wiki version test the first digits and the last digits
in a different order!

'show' on integers is (relatively) very slow.  Your version first
tests the first 9 digits of the number -- note that computing the
first digits of a number requires computing all the digits, even the
ones that don't get shown.  Only if the first 9 digits are "123456789"
does your version go on to test the last nine digits (since (&&) is
lazy).  The wiki version, on the other hand, first tests the last 9
digits (much faster) and only if those are "123456789" does it bother
doing the (expensive) test for the first 9 digits.  Since only 112 out
of the first 329000 or so Fibonacci numbers end in the digits 1..9,
this makes a huge difference.

-Brent