Don's benchmark.

It appears the mob has spoken and that I am a wrong headed twit.

My apologies to Don on the misunderstanding. When I first saw the numbers I assumed that the speed had to be due to memoization. It's not.

I saw a link earlier to a post by Don Stewart in that he asserts that Haskell is 40 times faster than python for a given algorithm.

He then goes on to point out how easy it is to drop hints to the code to parallelize the code.

While I won't go into any threading issues, the core point that it takes python almost thirty seconds to generate each Fibonacci number up to 36 is misplaced.

Haskell is a language built around the idea of functions that can be assumed to be functionally transparent. If you give them the same set of arguments they'll give the same answer.

The upside to this is that the compiler writers can automatically memoize every function if they want to unless its been explicitly marked as being otherwise.

Python, being based upon the idea of dynamic objects rather than that of transparent functions has no need for such optimizing. The developers time is better spent ensuring rapid dictionary insertion and deletion over transparent function memoization.

But, as he doesn't seem to mind having to annotate concurrancy, I'm sure that annotating transparency is just as fair.

#!/usr/bin/python

# Don's original python
# def fib(n):
#     if n == 0 or n == 1:
#          return n
#     else:
#         return fib(n-1) + fib(n-2)
#     
# for i in range(36):
#     print "n=%d => %d" % (i, fib(i))

def memoize ( func ) :
    """ In haskell mutability must be handled explicitly.
    Only fair that Python do the same to transparent functionality
    """
    remembered = {}
    def memoized ( *args ) :
        if args in remembered :
            return remembered[ args ]
        else :
            new = func( *args )
            remembered[ args ] = new
            return new
    return memoized

@memoize
def fib(n):
    if n == 0 or n == 1:
         return n
    else:
        return fib(n-1) + fib(n-2)
    
for i in range(36):
    print "n=%d => %d" % (i, fib(i))

The above code runs at a comfortable

  real    0m0.020s
  user    0m0.012s
  sys     0m0.008s

which compared to his times

  Ruby (1.8.5)   64.26s
  Python (2.4) 25.16s
  Haskell (GHC 6.8)  0.78s
  Parallel Haskell (GHC 6.8)  0.67s

fairs reasonably.

Since Python allows mutable variables a looping implementation would have been more idiomatic python. Even better to use a generator. Then we can start output before the sequence is complete.

All his benchmark really showed was that memoization on transparent functions is really great. Thanks guy.