[Tutor] fibonacci [caching]

[Jayprasad J. Hegde]

On Fri, Feb 14, 2003 at 10:31:10AM -0800, Danny Yoo wrote:
> 
> > def fib2(n):
> >     if n < 2:
> >         return n
> >     else:
> >         return fib2(n-2) + fib2(n-1)
> The above defintion of the fibonacci function is always used as the
> prototypical example of abusive recursion.  
true. 

> However, there is a
> programming technique called "caching" that will greatly improve the
> performance of something like the recursive fibonacci function.

The solution that you have given is beautiful due to the elegance being retained and all the dirty work of caching/memoing being done in the "background". 
Simple, efficient and _not_ convoluted like the earlier examples (sorry folks!). :)
The closest so far to being a true representative python version of an efficient Fibonacci algo. 

Thanks Danny. 

- JJH

> ###
> """Demonstration of a simple caching technique."""
> 
> import weakref
> 
> class Cache:
>     def __init__(self, f):
>         self.f = f
>         self.cache = {}
> 
>     def __call__(self, *args):
>         if not self.cache.has_key(args):
>             self.cache[args] = self.f(*args)
>         return self.cache[args]
> 
> def fib2(n):
>     if n < 2:
>         return n
>     return fib2(n-2) + fib2(n-1)
> 
> fib2 = Cache(fib2)
> ###
> 
> 
> 
> Let's see how this might work:
> 
> ###
> >>> def measureFib(n):
> ...     start = time.time()
> ...     result = fib2(n)
> ...     stop = time.time()
> ...     print "fib2(%s) == %s, taking %s" % (n, result, stop-start)
> ...
> >>> measureFib(100)
> fib2(100) == 354224848179261915075, taking 0.00286304950714
> >>> measureFib(100)
> fib2(100) == 354224848179261915075, taking 4.19616699219e-05
> ###
> 
> 
> 
> This version of fib2() performs much better than the original; in fact,
> it's almost as fast as the iterative solutions!  (Although it does take up
> more space.)  So for this specific example, at least, there are perfectly
> good ways to get excellent performance as well as clean code.
> 
> 
> This technique of caching is often called "memoization", and there's a
> reference to it in the Python Cookbook:
> 
>     http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52201

- JJH
-- 
If you don't strike oil in twenty minutes, stop boring.
		-- Andrew Carnegie, on public speaking
(defun JJHdetails ()
  (format t "~&~A~&~A~&~A"
    "Jayprasad J Hegde, KBCS, NCST" "Gulmohar Cross
    Road 9, Juhu, Mumbai 400049." "tel: +91-22-26201606x373"))