[Tutor] fibonacci [caching]
Jayprasad J. Hegde
jjhegde@konark.ncst.ernet.in
Mon Feb 17 00:07:03 2003
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"))