5 Ways of Fibonacci in Python – Best way!


For appreciating this post, I request you to go through 5 Ways of Fibonacci in Python post of mine, where I have explained 5 different ways by which you could write code for finding nth Fibonacci number. At the end of the post, I had promised you that I would come up with performance measurements for each of these ways and conclude on whats the best way; So, here I am!

When I used all five ways to calculate 15000th Fibonacci number, and calculated the time taken by each of these methods for 10 iterations, this is what I got

                                           Fib(n=15000)
loops recursion generators memoization memoization as decorator
45 87 58 44 43
47 88 58 42 42
51 92 60 44 43
43 87 58 42 43
48 92 61 42 44
45 87 59 43 44
44 85 57 42 44
44 87 62 43 43
48 86 59 42 43
45 91 61 45 45
46 88.2 59.3 42.9 43.4   (Avg)

Takeaways:

  • Looping technique seems pretty reasonable
  • Recursion is hell.. lets consider we need to find fib(5). Now, fib(5) = fib(4) + fib(3) and fib(4) = fib(3) + fib(2) and so on.. Now in this case, fib(3) is calculated twice, which is redundant. Hence the increased time as depicted in the table above.
  • Generators help in creating iterators and avoid the issues with recursion, but are slightly heavy as the function is re-entered over and again
  • Memoization ensures the calculated numbers like fib(3) in case of recursion and hence are faster
  • Decorators adds a slight overhead in terms of program flow switching between decorator to the actual function and hence slightly slower than Memoization without decorators

So the clear winner is Memoization on a function written with a for loop… :)

About these ads

About Chetan Giridhar

An avid technologist, blogger and a newbie photographer.

Posted on April 19, 2012, in Python and tagged , , , , , , , . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: