gpt4 book ai didi

ruby - 为什么尾递归 gcd 比 rubinius 的 while 循环更快

转载 作者:数据小太阳 更新时间:2023-10-29 07:07:44 27 4
gpt4 key购买 nike

我有这两个 gcd 函数的实现:

def gcd1(a,b)
if a==b
a
elsif a>b
if (a%b)==0
b
else
gcd1(a%b,b)
end
else
if (b%a)==0
a
else
gcd1(a,b%a)
end
end
end
def gcd2(a,b)
if(a==b)
return a
elsif b>a
min,max=a,b
else
min,max=b,a
end
while (max%min)!=0
min,max=max%min,min
end
min
end

函数 gcd1 是尾递归的,而 gcd2 使用 while 循环。

我已经验证 rubinius 通过对阶乘函数进行基准测试来执行 TCO,只有阶乘函数基准测试显示递归版本和迭代版本是“相同的”(我使用了基准测试 ips)。

但对于上述情况,基准测试表明 gcd1 至少比 gcd2 快两倍(递归比迭代快两倍,甚至更快)。

我用来做基准测试的代码是这样的:

Benchmark.ips do |x|
x.report "gcd1 tail recursive" do
gcd1(12016,18016)
end
x.report "gcd2 while loop" do
gcd2(12016,18016)
end
x.compare!
end

结果:

Warming up --------------------------------------
gcd1 tail recursive 47.720k i/100ms
gcd2 while loop 23.118k i/100ms
Calculating -------------------------------------
gcd1 tail recursive 874.210k (± 7.1%) i/s - 4.343M
gcd2 while loop 299.676k (± 6.6%) i/s - 1.503M

Comparison:
gcd1 tail recursive: 874209.8 i/s
gcd2 while loop: 299676.2 i/s - 2.92x slower

我正在运行 Arch linux x64,处理器 i5-5200 2.2 GHZ 四核。

ruby 实现是 Rubinius 3.40。

那么递归如何才能比循环更快呢?

更新

只是说斐波那契有同样的情况:尾递归版本至少是循环版本的两倍,我用于斐波那契的程序:http://pastebin.com/C8ZFB0FR

最佳答案

在您使用的示例中,它只需要 3 次调用/循环就可以得到答案,所以我认为您实际上没有在测试正确的东西。尝试使用两个连续的斐波那契数(例如第 2000 和 2001),结果应该相差不大。

(抱歉,我还没有发表评论的名誉)。

编辑: 我终于设法安装了 [一部分] rubinius 并设法重新创建了您所指的现象。这不是关于递归,而是关于多重赋值。如果你改变

      while n>0
a,b=b,a+b
n-=1
end

      while n>0
t=a
a=b
b=t+b
n-=1
end

while 循环版本应该(稍微)执行得更快。原来的GCD程序也是如此,即替换

        min,max=max%min,min

        t=min
min=max%t
max=t

是事情。

ruby-2.1 不是这种情况,即 while 循环似乎更快,只是在您提供的形式中。

希望对您有所帮助!

关于ruby - 为什么尾递归 gcd 比 rubinius 的 while 循环更快,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37912024/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com