4 ms·
It's a dual-core machine. The par annotations get you a factor of two at best. Dons is still arguably pulling a fast one, though. Even though the Haskell pro
by dfranke 19y ago
It's a dual-core machine. The par annotations get you a factor of two at best.
Dons is still arguably pulling a fast one, though. Even though the Haskell program looks like it should behave in more-or-less the same way as the other two, the semantics are actually quite different. Haskell defaults to lazy evaluation with memoization -- hence the "naive" recursion isn't really naive. That's where the orders of magnitude come from.
That said, Haskell is still a pretty fast language, on par with Java.
- SamReidHughes 19y agoIt isn't memoizing anything here. If it were memoizing, do you think it would take 0.48 seconds? Laziness is not the same thing as memoization of function arguments.
- dfranke 19y agoOkay, apparently I didn't quite think this one through. I wasn't claiming that GHC memoizes values, but it does memoize thunks. I thought this algorithm would be getting some benefit from that, but having inserted some trace statements, I was apparently wrong. Here's a version that really is memoized: import Control.Parallel import Control.Monad import Text.Printf cutoff = 35 fibs = [ fib n | n <- [0..] ] fib' :: Int -> Integer fib' 0 = 0 fib' 1 = 1 fib' n = fibs !! (n-1) + fibs !! (n-2) fib :: Int -> Integer fib n | n < cutoff = fib' n | otherwise = r `par` (l `seq` l + r) where l = fibs !! (n-1) r = fibs !! (n-2) main = forM_ [0..45] $ \i -> printf "n=%d => %d\n" i (fib i)