|
锁定老帖子 主题：ruby 写的求fib数的性能问题
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2007-10-25
代码:
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写很快就出来了,不知道是什么原因造成这样的结果呢? 声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：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 |
| 返回顶楼 | |
|
发表时间：2007-10-25
ruby并没有尾递归优化，这个东西应该转成迭代来处理吧
|
| 返回顶楼 | |
|
发表时间：2007-10-25
<layer id="google-toolbar-hilite-0" style="background-color: Fuchsia; color: black;">ruby</layer> 代码
这个尾递归版本，fib(10000)仍然可以计算，再增加一个数量级就栈溢出了 |
| 返回顶楼 | |
|
发表时间：2007-10-25
尾递归在这里表现的快一些的原因，我想是因为尾递归版本是将结果作为方法参数传入，那么在计算结束后，不需要弹出栈就可以得到结果
|
| 返回顶楼 | |
|
发表时间：2007-10-26
这种的递归在ruby 1.8中是非常非常的慢,很多时间都浪费在维护ruby自己的堆栈上.
ruby 2.0中这个问题得到解决.2.0改用了基于bytecode的执行引擎,能快上几十倍. xruby在这方面都比ruby 1.8快很多: http://xruby.iteye.com/blog/69937 |
| 返回顶楼 | |
|
发表时间：2007-10-31
ruby 代码
发现这个是最快的～～ |
| 返回顶楼 | |
|
发表时间：2007-11-01
pure 写道 <div class="code_title">ruby 代码</div>
to ls:
<div class="dp-highlighter"> <div class="bar"></div> <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 < 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> 用查表的方法什么语言都可以变为O(n)的量级 这个没有意义的 |
| 返回顶楼 | |
|
发表时间：2007-11-01
怎么把9楼投隐藏阿?
我觉得挺有趣的,不要因为楼上帖子大家就不继续发言了. |
| 返回顶楼 | |
|
发表时间：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吧 |
| 返回顶楼 | |
