From: Robert Klemme <bob.news@...>
Date: 2003-09-15T18:26:45+09:00
Subject: Re: performance and style advice requested


"Ben Giddings" <bg-rubytalk@infofiend.com> schrieb im Newsbeitrag
news:059CAA7E-E703-11D7-88E6-00039381462A@infofiend.com...
> Some style advice:
>
> On Sunday, September 14, 2003, at 12:44  PM, Alex Martelli wrote:
> > #
> > # factorial, memoized via an Array
> > #
> > $_fact_memo=[1,1,2,6,24,120,720]
>
> Ugh.  This is what really bothers me about python programs.  Ugly
> underscores.
>
> > def fact(x)
> >     # factorial of x (0 if x<0)
> >     result = $_fact_memo[x]
> >     if !result
> >         return 0 if x<0
> >         result = $_fact_memo[x] = x*fact(x-1)
> >     end
> >     return result
> > end
>
> Hmm, how about
>
> def fact(x)
>      $fact_memo[x] ||= if x<0
>                           0
>                        else
>                           x*fact(x-1)
>                        end
> end
>
> Although I'm pretty sure that a simple conditional is faster than an
> array lookup so this might be faster (and is easier to read):
>
> def fact(x)
>      return 0 if x<0
>      $fact_memo[x] ||= x*fact(x-1)
> end

Since recursions are costly and abort the interpreter for large n I
suggest this implementation:

def fact(n)
  return 0 if n<1

  @facts ||= [0,1]

  last = @facts.size - 1

  for i in @facts.size .. n
    @facts[i] = @facts[last] * i
    last = i
  end

  @facts[n]
end


Regards

    robert