«

On Sat, Sep 15, 2012 at 12:12 AM, andrea crotti
<> 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

Chris Angelicoæ–¼ 2012å¹´9月14日星期五UTC+8下å�ˆ10時41分06ç§ ’寫é�“：
> On Sat, Sep 15, 2012 at 12:12 AM, andrea crotti
>
> <> 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.

Chris Angelicoæ–¼ 2012å¹´9月14日星期五UTC+8下å�ˆ10時41分06ç§ ’寫é�“：
> On Sat, Sep 15, 2012 at 12:12 AM, andrea crotti
>
> <> 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.