From: Robert Klemme <shortcutter@...>
Date: 2011-04-20T20:37:03+09:00
Subject: Re: Tail Call Optimization (Tail Recursion)

On Wed, Apr 20, 2011 at 6:35 AM, WJ <w_a_x_man@yahoo.com> wrote:
> WJ wrote:
>
>> (time (set! bigfib (fib 50000)))
>>     562 ms real time
>>     516 ms cpu time (500 user, 16 system)
>
> This Ruby version runs in about 0.6 seconds:
>
> def fib n
>  a,b = 0,1
>  2.upto(n){
>    a,b = b, a+b
>  }
>  b
> end

Just for the fun of it a version with a Hash as "function" for faster
repeated access.

13:35:36 Temp$ ruby19 fib.rb
                     user     system      total        real
0 def(50000)     0.187000   0.000000   0.187000 (  0.184000)
0 hash[50000]    0.313000   0.047000   0.360000 (  0.350000)
0 def(40000)     0.234000   0.000000   0.234000 (  0.241000)
0 hash[40000]    0.000000   0.000000   0.000000 (  0.000000)
1 def(50000)     0.359000   0.000000   0.359000 (  0.361000)
1 hash[50000]    0.000000   0.000000   0.000000 (  0.000000)
1 def(40000)     0.250000   0.000000   0.250000 (  0.240000)
1 hash[40000]    0.000000   0.000000   0.000000 (  0.000000)
2 def(50000)     0.360000   0.000000   0.360000 (  0.365000)
2 hash[50000]    0.000000   0.000000   0.000000 (  0.000000)
2 def(40000)     0.234000   0.000000   0.234000 (  0.240000)
2 hash[40000]    0.000000   0.000000   0.000000 (  0.000000)
3 def(50000)     0.375000   0.000000   0.375000 (  0.363000)
3 hash[50000]    0.000000   0.000000   0.000000 (  0.000000)
3 def(40000)     0.235000   0.000000   0.235000 (  0.239000)
3 hash[40000]    0.000000   0.000000   0.000000 (  0.000000)
4 def(50000)     0.359000   0.000000   0.359000 (  0.357000)
4 hash[50000]    0.000000   0.000000   0.000000 (  0.000000)
4 def(40000)     0.234000   0.000000   0.234000 (  0.241000)
4 hash[40000]    0.000000   0.000000   0.000000 (  0.000000)
13:35:53 Temp$ cat -n fib.rb
     1
     2  require 'benchmark'
     3
     4  def fib n
     5   a,b = 0,1
     6   2.upto(n){
     7     a,b = b, a+b
     8   }
     9   b
    10  end
    11
    12  f2 = Hash.new do |h,n|
    13    l = nil
    14
    15    (h.keys.max + 1).upto n do |i|
    16      h[i] = l = h[i-1] + h[i-2]
    17    end
    18
    19    l
    20  end.merge(0=>0, 1=>1)
    21
    22  Benchmark.bm 15 do |x|
    23    5.times do |i|
    24      [50_000, 40_000].each do |n|
    25        x.report "#{i} def(#{n})" do
    26          fib n
    27        end
    28
    29        x.report "#{i} hash[#{n}]" do
    30          f2[n]
    31        end
    32      end
    33    end
    34
    35  end
13:35:56 Temp$

Cheers

robert


-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/