2012/9/14 Chris Angelico <ros...@gmail.com>: > > 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 > -- > http://mail.python.org/mailman/listinfo/python-list
The poor algorithm is much more close to the mathematical definition than the smarter iterative one.. And in your second version you include some ugly caching logic inside it, so why not using a decorator then? I'm not saying that with the memoization is the "good" solution, just that I think it's a very nice example of how to use a decorator, and maybe a good example to start with a talk on decorators.. -- http://mail.python.org/mailman/listinfo/python-list
