Pyhon profiling

Lately i've been using Python as it is widely used on any programming related courses from Udacity and Coursera. This blog will be dedicated to the field of functional programming. A nice example to get started is the Fibonacci sequence which you can easily implement recursively or iteratively. We will focus on recursive solutions and fix any performance issues along the way.

A recursive functional style implementation:

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    else:
       return fibonacci(n-2) + fibonacci(n-1)   

import cProfile
cProfile.run('print fibonacci(10)')

I use CodePad to run the python code which gives following output (which can of course vary).

55
         179 function calls (3 primitive calls) in 0.127 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.001    0.001    0.127    0.127 <string>:1(<module>)
    177/1    0.126    0.001    0.126    0.126 t.py:1(fibonacci)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

If you try to execute fibonacci(40) you will already run into a timeout. So we need a way to temporary store calculated values so we don't need to recalculate them over and over again. Python offers a nice way to accomplish this.

def memoize(f):
   """Decorator that caches the return value for each call to f(args)"""
   cache = {} # create a dictionary
   def _f(*args):
       try:
           #try to retrieve value from cache
           return cache[args] 
       except KeyError:
           #value was not found se we first cache it and return it
           cache[args] = result = f(*args)
           return result
       except TypeError:
           #Some values can't be used as keys so we have to calculate the result
           return f(args)
   return _f
 
@memoize
def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    else:
       return fibonacci(n-2) + fibonacci(n-1)   
            
 
import cProfile
cProfile.run('print fibonacci(10)')

As you can see the same invocation now only makes 32 function calls and has become very fast.

55
         32 function calls (4 primitive calls) in 0.007 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.001    0.001    0.007    0.007 <string>:1(<module>)
     19/1    0.003    0.000    0.006    0.006 t.py:13(_f)
     11/1    0.003    0.000    0.006    0.006 t.py:26(fibonacci)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}