reset password
Author Message
rabbott
Posts: 1649
Posted 12:17 Feb 08, 2019 |

This code computes Fibonacci in three ways.

1. The traditional (naive, i.e., top-down) algorithm using recursion.

2. The same traditional algorithm but making the computation more explicit. Uses a while loop instead of recursion.

3. The same traditional algorithm but again making the computation more explicit and also caching the results.

To see how they compare, select "Run all" under the Runtime menu. (With n == 35, fib2 takes a minute and 10 seconds with trace off.)

Set trace=True (and use a single-digit n) to see the progress of the computation in versions 2 and 3.

Last edited by rabbott at 18:56 Feb 08, 2019.
rabbott
Posts: 1649
Posted 18:53 Feb 08, 2019 |

Versions 1 and 2 are both exponential, but version 1 is about 13 times faster than version 2. Version 3 is linear.

Version 1 is limited by stack size -- although you probably don't want to run a number large enough to find out what the limit is.

My guess is that the primary reason version 2 is slow is that it does list concatenation rather than list mutation.

Version 2a is a modification of version 2 that uses only list mutation operations and a couple of other optimizations--which made more of a difference than I expected. It speeds up version 2 by less than 60%. (Python's list processing seems to be surprisingly slow.)

Another optimization speeds it up to run at 30% of the original.

Can anyone find a way to speed it up further?

 

Last edited by rabbott at 15:01 Feb 10, 2019.
rabbott
Posts: 1649
Posted 10:44 Feb 09, 2019 |

I added a second (and more general) approach to caching. (This version of fibonacci is also linear.) Python has a "decorator" called @lru_cache that caches all calls and return values for the function it decorates. (It is defined in functools.) 

To illustrate how it works, I included a decorator called @memoize that does the same thing. The initial version of the implementation was copied from StackOverflow, but it was modified as explained in Hjelle's tutorial.

Briefly, decorators are functions that operate on and return a modified version of the functions they decorate! See also Hjelle's tutorial on Python decorators and the discussion of decorators in the functools library. 

We will talk about all this later.

Last edited by rabbott at 14:22 Feb 09, 2019.