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

Question

我有这两个 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，只有阶乘函数基准测试显示递归版本和迭代版本是"same-ish"（我使用了benchmark-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

Answer 1

在您使用的示例中，只需 3 calls/loops 即可得到答案，因此我认为您实际上没有在测试正确的东西。尝试使用两个连续的斐波那契数（例如第 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 循环似乎更快，只是在您提供的形式中。

希望对您有所帮助！

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

why tail recursive gcd is faster than while loop with rubinius

ruby

performance

tail-recursion

rubinius

更新