ruby 写的求fib数的性能问题

代码:

def fib(n)
  (n>=2)?fib(n-2)+fib(n-1):n
end

print(fib(20)+"\n")
#print(fib(40)+"\n")

求fib过程中,n<=20速度还算快,n>30都出不来了,dos窗口一直没有自动关闭.

用java写很快就出来了,不知道是什么原因造成这样的结果呢?

评论

12 楼 neodoxy 2007-12-06  

动态语言肯定会差一点,不过Ruby的VM的进化之路的确还很长

11 楼 edge_hh 2007-12-05  

0=>0
1=>1
2=>1
3=>2
4=>3
5=>5
6=>8
7=>13
8=>21
9=>34
10=>55
11=>89
12=>144
13=>233
14=>377
15=>610
16=>987
17=>1597
18=>2584
19=>4181
20=>6765
21=>10946
22=>17711
23=>28657
24=>46368
25=>75025
26=>121393
27=>196418
28=>317811
29=>514229
30=>832040
31=>1346269
32=>2178309
33=>3524578
34=>5702887
35=>9227465
time=484ms

JAVA.

性能差距还是蛮大的。

10 楼 fxsjy 2007-12-02  

python2.5+psyco 2.2s

import psyco
psyco.full()
def fib(n):
   if n == 0 or n == 1:
      return n
   else:
      return fib(n-1) + fib(n-2)

for i in range(36):
    print "n=%d => %d" % (i, fib(i))

9 楼 neodoxy 2007-12-01  

看这里：http://antoniocangiano.com/2007/11/28/holy-shmoly-ruby-19-smokes-python-away/
Mac OS X 10.5 with MacBook Pro (Core 2 Duo 2.2 GHz and 2 GB of memory)

def fib(n)
if n == 0 || n == 1
n
else
fib(n-1) + fib(n-2)
end
end

36.times do |i|
puts "n=#{i} => #{fib(i)}"
end

Ruby 1.8.6: 158.869s
Python 2.5.1: 31.507s
Ruby 1.9.0: 11.934s
等待Xmas礼物Ruby1.9吧

8 楼 lgn21st 2007-11-01  

怎么把9楼投隐藏阿?
我觉得挺有趣的,不要因为楼上帖子大家就不继续发言了.

7 楼 syhan 2007-11-01  

pure 写道

<div class="code_title">ruby 代码</div>
<div class="dp-highlighter">
<div class="bar"></div>
<ol class="dp-rb">
    <li class="alt"><span><span>Fib&nbsp;=&nbsp;</span><span class="builtin">Hash</span><span>.</span><span class="keyword">new</span><span>{&nbsp;</span><span class="variable">|h</span><span>,&nbsp;n|&nbsp;n&nbsp;&lt;&nbsp;2&nbsp;?&nbsp;h[n]&nbsp;=&nbsp;n&nbsp;:&nbsp;h[n]&nbsp;=&nbsp;h[n&nbsp;-&nbsp;1]&nbsp;+&nbsp;h[n&nbsp;-&nbsp;2]&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;</span></span></li>
    <li class=""><span>puts&nbsp;Fib[50]&nbsp;&nbsp;&nbsp;</span></li>
</ol>
</div>
<p>发现这个是最快的～～</p>

to ls:
用查表的方法什么语言都可以变为O(n)的量级
这个没有意义的

6 楼 pure 2007-10-31  

<div class='code_title'>ruby 代码</div>
<div class='dp-highlighter'>
<div class='bar'/>
<ol class='dp-rb'>
    <li class='alt'><span><span>Fib = </span><span class='builtin'>Hash</span><span>.</span><span class='keyword'>new</span><span>{ </span><span class='variable'>|h</span><span>, n| n &lt; 2 ? h[n] = n : h[n] = h[n - 1] + h[n - 2] }       </span></span></li>
    <li class=''><span>puts Fib[50]   </span></li>
</ol>
</div>
<p>发现这个是最快的～～</p>

5 楼 yawl 2007-10-26  

这种的递归在ruby 1.8中是非常非常的慢,很多时间都浪费在维护ruby自己的堆栈上.

ruby 2.0中这个问题得到解决.2.0改用了基于bytecode的执行引擎,能快上几十倍.

xruby在这方面都比ruby 1.8快很多:
http://xruby.iteye.com/blog/69937

4 楼 dennis_zane 2007-10-25  

尾递归在这里表现的快一些的原因，我想是因为尾递归版本是将结果作为方法参数传入，那么在计算结束后，不需要弹出栈就可以得到结果

3 楼 dennis_zane 2007-10-25  

<div class='code_title'>&lt;layer id="google-toolbar-hilite-0" style="background-color: Fuchsia; color: black;"&gt;ruby&lt;/layer&gt; 代码</div>
<div class='dp-highlighter'>
<div class='bar'> </div>
<ol class='dp-rb' start='1'>
    <li class='alt'><span><span class='keyword'>def</span><span> fib(n)    </span></span></li>
    <li class=''><span>  fib_iter(n, 1, 0)    </span></li>
    <li class='alt'><span><span class='keyword'>end</span><span>    </span></span></li>
    <li class=''><span><span class='keyword'>def</span><span> fib_iter(n,i, j)    </span></span></li>
    <li class='alt'><span>  <span class='keyword'>return</span><span> i </span><span class='keyword'>if</span><span> n==1  </span></span></li>
    <li class=''><span>  fib_iter(n-1, i + j, i)    </span></li>
    <li class='alt'><span><span class='keyword'>end</span><span>   </span></span></li>
</ol>
</div>
<br/>
这个尾递归版本，fib(10000)仍然可以计算，再增加一个数量级就栈溢出了

2 楼 dennis_zane 2007-10-25  

ruby并没有尾递归优化，这个东西应该转成迭代来处理吧

1 楼 Arbow 2007-10-25  

试试尾递归

def fib(n)
	if n==0
		return 0
	else
		return tailRecursionFib(n, 1, 0)
	end
end

def tailRecursionFib(n, f1, f2)
	if n==1
		return f1
	else
		return tailRecursionFib(n-1, f1+f2, f1)
	end
end