Path: csiph.com!usenet.pasdenom.info!gegeweb.org!usenet-fr.net!nerim.net!novso.com!newsfeed.xs4all.nl!newsfeed5.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <CAF_E5JY6c+QfYGo9N=0p7HdSa6NX8oL-Hj9gR6=7TayQeOqmoA@mail.gmail.com>
References: <XnsA0CE7D6F43F18duncanbooth@127.0.0.1> <1017333532.1009581.1347628946603.JavaMail.root@sequans.com> <CAF_E5JY6c+QfYGo9N=0p7HdSa6NX8oL-Hj9gR6=7TayQeOqmoA@mail.gmail.com>
Date: Sat, 15 Sep 2012 00:41:01 +1000
Subject: Re: Decorators not worth the effort
From: Chris Angelico <rosuav@gmail.com>
To: python-list@python.org
Content-Type: text/plain; charset=ISO-8859-1
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.705.1347633665.27098.python-list@python.org>
Lines: 41
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:29168

On Sat, Sep 15, 2012 at 12:12 AM, andrea crotti
<andrea.crotti.0@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