Re: Decorators not worth the effort

Discussion in 'Python' started by Chris Angelico, Sep 14, 2012.

  1. 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, Sep 14, 2012
    #1
    1. Advertising

  2. 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.
     
    88888 Dihedral, Sep 14, 2012
    #2
    1. Advertising

  3. 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.
     
    88888 Dihedral, Sep 14, 2012
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jean-Michel Pichavant

    Re: Decorators not worth the effort

    Jean-Michel Pichavant, Sep 14, 2012, in forum: Python
    Replies:
    4
    Views:
    221
    Steve Howell
    Sep 15, 2012
  2. Jean-Michel Pichavant

    Re: Decorators not worth the effort

    Jean-Michel Pichavant, Sep 14, 2012, in forum: Python
    Replies:
    1
    Views:
    152
    Steven D'Aprano
    Sep 14, 2012
  3. andrea crotti

    Re: Decorators not worth the effort

    andrea crotti, Sep 14, 2012, in forum: Python
    Replies:
    0
    Views:
    153
    andrea crotti
    Sep 14, 2012
  4. Jean-Michel Pichavant

    Re: Decorators not worth the effort

    Jean-Michel Pichavant, Sep 14, 2012, in forum: Python
    Replies:
    0
    Views:
    161
    Jean-Michel Pichavant
    Sep 14, 2012
  5. andrea crotti

    Re: Decorators not worth the effort

    andrea crotti, Sep 14, 2012, in forum: Python
    Replies:
    0
    Views:
    160
    andrea crotti
    Sep 14, 2012
Loading...

Share This Page