`
pure
  • 浏览: 354388 次
社区版块
存档分类
最新评论

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

相关推荐

    汇编求Fibonacci数的源程序

    在提供的"求Fibonacci数程序设计任务书1.doc"中,可能会包含更具体的任务说明、设计要求以及评估标准,帮助学习者更好地理解和完成项目。而"www.pudn.com.txt"可能是一个链接或者资源引用,用于获取更多的汇编语言...

    fib.rar_斐波那契_求斐波那契数

    题目中提到的“fib.rar”压缩包文件包含了关于如何用递归方式计算斐波那契数列第24项的实现,即求F(24)。 在编程中,递归是一种解决问题的方法,它会定义一个函数或过程,该函数或过程通过调用自身来解决问题。在...

    fib.rar_fib_fib 汇编语言_汇编_汇编 fib

    标题中的“fib.rar_fib_fib 汇编语言_汇编_汇编 fib”表明这是一个关于使用汇编语言实现斐波那契数列的压缩文件。斐波那契数列是一个数学序列,其中每个数字是前两个数字的和,通常以0和1开始:0, 1, 1, 2, 3, 5, 8,...

    高性能路由器FIB压缩方法.pdf

    FIB聚合的概念是将具有相同下一跳的多个路由条目归并为单一的条目,从而减少FIB表的总行数。例如,两个连续地址空间的路由前缀可以聚合为一个更大的路由前缀。 具体实现时,首先通过路由协议如BGP或IGP获得路由条目...

    递归方法求斐波那契函数FIB(N).pdf

    递归方法求斐波那契函数 FIB(N) 是一款基于汇编语言的课程设计项目,旨在加深对汇编语言理论和基本知识的理解,掌握 DOS 和 BIOS 系统功能调用,并提高分析问题和解决问题的能力。 该项目的主要目的是使用递归方法...

    汇编实现fib函数,fib(1)=fib(2)=1;fib(n)=fib(n-2)+fib(n-1)

    本人自己用汇编写的,输入的时候请输入数字,因为没有加输入字母的处理程序

    C++求Fib数列

    int fib(int pos) { int elem = 1; int n1 = 1, n2 = 1; for (int i = 3; i &lt;= pos; i++) { elem = n2 + n1; n1 = n2; n2 = elem; } return elem; } 2. 第二版本 bool fib(int pos, int &elem) { ...

    fib数列生成器

    产生第N为fib数列,高精度,缺点是占内存,没解决内存泄漏问题

    Fib.rar_fib

    标题"Fib.rar_fib"指的是一个关于斐波那契数列的C++程序集合,而“Fib”标签进一步确认了这一点。斐波那契数列是一个在计算机科学和数学中非常基础且重要的概念,它定义了一串数字序列,其中每个数字是前两个数字的...

    Zeiss Auriga FIB软件操作说明书

    此外,文档还可能包括故障排除部分,为用户遇到的问题提供解决方案,以及定期维护和校准的指导,确保显微镜的性能始终保持最佳状态。 Zeiss Auriga FIB和SmartSEM®软件作为一款高端的科研设备和软件,它们的使用和...

    fib.rar_FIB如何计算_Fibonacci

    对于50以内的斐波那契数,虽然递归方法可以工作,但当数值更大时,可能会遇到栈溢出或者性能问题。 递归方法的基本思路是定义两个函数(或子程序):一个用于返回第n个斐波那契数,另一个用于返回第n-1个斐波那契数...

    fib.rar_fib

    标题中的“fib.rar_fib”和描述中提到的“Fib数列”指的是著名的斐波那契数列(Fibonacci sequence)。斐波那契数列是一个数学上的数列,由意大利数学家列奥纳多·斐波那契在解决兔子繁殖问题时引入。数列的定义是...

    基于FIB技术攻击芯片主动屏蔽层.pdf

    芯片安全设计是现代电子技术中的一个重要方面,尤其在智能卡、金融支付以及信息安全等领域,芯片的安全性能直接关系到数据保护和系统稳定。在芯片设计中,为了抵御物理攻击,常常采用主动屏蔽层来防御侵入式物理探测...

    fib model code 2020新动向

    在土木工程和混凝土结构设计领域,fib Model Code 2020(Fédération Internationale du Béton,国际混凝土联合会发布的模型规范)代表了国际上的先进准则。Model Code 2020是针对混凝土结构的设计指南,总结了...

    Fib_dynamicprogramming_

    标题"Fib_dynamicprogramming_"表明我们将探讨使用动态规划解决斐波那契数列问题。斐波那契数列是计算机科学中的一个经典例子,其定义是:每个数是前两个数的和,通常以0和1开始,即F(0) = 0,F(1) = 1,对于n &gt; 1,...

    fib:Github顶级语言的性能基准

    在Github上使用顶级语言进行递归斐波那契基准测试 前10名:JavaScript,Java,Python,Ruby,Php,C ++,C#,C,... fib(n - 1) + fib(n - 2) end puts fib(46) 这是Crystal版本: def fib(n : UInt64) return 1_u6

    用汇编语言,并且递归求菲波那契函数FIB(N).zip

    标题中的“用汇编语言,并且递归求菲波那契函数FIB(N)”表明了我们要探讨的主题是使用汇编语言实现菲波那契数列的递归算法。菲波那契数列是一个数学概念,其中每个数字是前两个数字的和,通常以0和1开始:0, 1, 1, 2,...

    fib斐波那契出列

    斐波那契数列在计算机科学中是一种经典的算法问题,其定义非常简单:第0项是0,第1项是...通过深入研究和实践这个"fib"示例,开发者可以更好地掌握并行编程技巧,这对于在现代多核处理器环境中编写高性能软件至关重要。

    linux forward的实现 Linux IP数据流 FIB

    8. **性能优化**:为了提高转发效率,Linux内核使用了如Netfilter、conntrack等机制,缓存连接状态,减少对路由表的查询次数。 深入理解Linux Forwarding和FIB,对于网络管理员和系统工程师来说至关重要,它可以...

Global site tag (gtag.js) - Google Analytics