Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

mdxi (4658)

mdxi
  (email not shown publicly)
http://mdxi.collapsar.net/

Journal of mdxi (4658)

Sunday May 15, 2005
09:21 PM

Benchmarking

[ #24712 ]

Started learning Haskell today. So far, it's neat and only minimally annoying (stupid types). Knowing Perl and Elisp make it not too brain-stretchy. Actually compiling code feels odd...it's been probably since my last C++ class in 1999 that I compiled something written by myself.

One of the early examples in the tutorial I'm working through (YAHT) involves -- surprise -- the Fibonacci series, implemented recursively. Out of curiosity I wrote an iterative version in Perl and started running them side-by-side. First the code:

--
-- This is Haskell...
--
module Main
    where

import IO

main = do
       hSetBuffering stdin LineBuffering
       putStrLn "Find which Fibonacci number?"
       num <- getLine
       putStrLn ("F[" ++ num ++ "] is " ++ show(fibo(read num)))

fibo 1 = 1
fibo 2 = 1
fibo n = fibo (n - 2) + fibo (n - 1)

#
# ...and this is Perl
#
$num = <>;
chomp $num;
$t1 = 1;
$t2 = 1;

for (1..$num) {
    if ($_ == 1 || $_ == 2) {
        $f = 1;
    } else {
        $f = $t1 + $t2;
        $t1 = $t2;
        $t2 = $f;
    }
}
print "F[$num] is $f\n";

The Haskell code was compiled with no special options using ghc. The perl was run under Perl, twice the first time, so that perl(1) would be buffered. Things didn't get interesting until around the 30th number in the series:

mdxi@fornax:~$ time ./haskell/fibo_hs
Find which Fibonacci number?
30
F[30] is 832040

real    0m0.672s
user    0m0.432s
sys     0m0.004s
mdxi@fornax:~$ time perl fibo.pl
30
F[30] is 832040

real    0m0.240s
user    0m0.002s
sys     0m0.002s

This is where you can finally start to see a difference between recursive and iterative implementations. By 40 the difference was staggering:

mdxi@fornax:~$ time ./haskell/fibo_hs
Find which Fibonacci number?
40
F[40] is 102334155

real    0m52.804s
user    0m52.541s
sys     0m0.024s
mdxi@fornax:~$ time perl fibo.pl
40
F[40] is 102334155

real    0m0.256s
user    0m0.002s
sys     0m0.003s

It took the recursive implementation 1m26s (162% longer) to find number 41 and 2m17s (147% longer than 41; 240% longer than 40) to find number 42.

Meanwhile the iterative implementation took 0.43 seconds to find the 100th number and the same amount of time to find the 500th. At this point I figured my typing lag was taking most of the time, so I rewrote the perl to use command-line arguments (I don't know how to handle that in Haskell). With this change, the iterative approach took 0.005s to find the 1000th number of the sequence, and (0.014, 0.111)s to tell me that perl(1) considers the (10,000; 100,000)th numbers equivalent to infinity.

What does this tell us? Other than that I am easilly amused, pretty much just that: the flip side to TMTOWTDI is that not every way is the right way for the job at hand. But we all knew that already, right?

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • I've had pretty much the same experience, which I put down to my lack of experience(!). One of the fun things to work with in Haskell is infinite lists: you can do some amazingly powerful things in a tiny piece of code. The "iterate" function is quite fun in this sort of setting: for example (Haskell newbie code alert...)

    map head (iterate(\y->[x| x<-y, (x `mod` head(y) /= 0)]) [2..])

    You'll probably spot the nature of the output pretty quickly (in case it's not clear from the input), which leads to