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… 🙂
THX
The best (fastest) way is not to use recursion or loops. Example of very goog solution which works fast for big numbers:
from numpy import matrix
def fib(n):
return (matrix(
‘0 1; 1 1’ if n >= 0 else ‘-1 1; 1 0’, object
) ** abs(n))[0, 1]