[Tutor] fibonacci [caching]

[Gregor Lingl]

Hi Danny,

thanks for your very clear and *beautiful* Pythonic explanation.

Moreover I understand very well, that there are people, especially
seasoned pythonistas, who refuse to read code like the obfuscated
one I posted several postings before to this thread:  fib1liner
Maybe sometimes this will be used as a "prototypical example of abusing
Python" --- in my opinion it certainly is!

However, I'd like to stress, that it does just what your example does,
except that the fibonaccis are stored in a list - which I thiok is ok when
defining a function whose domain is the set of the nonnegative integers.

Consider it to be a curiosity.And let's keep in mind, that even Guido 
dislikes
lambda. ;-)

Danny Yoo schrieb:

>>def fib2(n):
>>    if n < 2:
>>        return n
>>    else:
>>        return fib2(n-2) + fib2(n-1)
>>    
>>
>
>Hi Gregor,
>
>
>The above defintion of the fibonacci function is always used as the
>prototypical example of abusive recursion.  However, there is a
>programming technique called "caching" that will greatly improve the
>performance of something like the recursive fibonacci function.
>
>
>###
>"""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
>
>
>
>Hope this helps!
>
>
>
>  
>