Chris Angelico於 2012年9月14日星期五UTC+8下午10時41分06秒寫道: > On Sat, Sep 15, 2012 at 12:12 AM, andrea crotti > > <andrea.crott...@gmail.com> wrote: > > > def fib(n): > > > if n <= 1: > > > return 1 > > > return fib(n-1) + fib(n-2) > > > > > > @memoize > > > def fib_memoized(n): > > > if n <= 1: > > > return 1 > > > return fib_memoized(n-1) + fib_memoized(n-2) > > > > > > > > > The second fibonacci looks exactly the same but while the first is > > > very slow and would generate a stack overflow the second doesn't.. > > > > Trouble is, you're starting with a pretty poor algorithm. It's easy to > > improve on what's poor. Memoization can still help, but I would start > > with a better algorithm, such as: > > > > def fib(n): > > if n<=1: return 1 > > a,b=1,1 > > for i in range(1,n,2): > > a+=b > > b+=a > > return b if n%2 else a > > > > def fib(n,cache=[1,1]): > > if n<=1: return 1 > > while len(cache)<=n: > > cache.append(cache[-1] + cache[-2]) > > return cache[n] > > > > Personally, I don't mind (ab)using default arguments for caching, but > > you could do the same sort of thing with a decorator if you prefer. I > > think the non-decorated non-recursive version is clear and efficient > > though. > > > > ChrisA
Uhn, the decorator part is good for wrapping functions in python. For example a decorator can be used to add a layor of some message handlings of those plain functions to become iterators which could be used as call back functions in a more elegant way. -- http://mail.python.org/mailman/listinfo/python-list