尾部呼叫优化是所有可以解释这种性能差异的原因吗? [英] Is Tail Call optimization all that explains this performance difference

问题描述

我看到了三种不同的方式编写Fibonacci函数的递归形式:使用数学内联，使用数学内联进行结果缓存和一种使用尾部递归处理.我知道在缓存答案后，使用备忘录可以将O(N)算法转换为O(1).但是我不明白尾部调用优化可以如何提供帮助.我的印象是，它可能会阻止几份拷贝或类似的事情.它几乎与O(1)一样快. Ruby在做什么，这使速度如此之快?

I saw three different ways to write the recursive form of a Fibonacci function: With the math inline, With the math inline with result caching and one Using tail recursion with. I understand using memoization converts an O(N) algorithm to an O(1) after the answers are cached. But I fail to understand how tail call optimization can help this much. I was under the impression it might prevent a few copies or something like that. It is nearly as fast as the O(1). What is Ruby doing that makes this so fast?

这是使用数学内联的缓慢幼稚的实现.显然，这是运行时间最慢的O(N)时间，然后在显示时以O(N ^ 2)时间循环显示.

Here is the slow naive implementation with math inline. It is clearly the slowest running O(N) time, and then when looped as in the display in O(N^2) time.

puts Benchmark.measure {
  # Calculate the nth Fibonacci number, f(n).
  def fibo (n)
    if n <= 1
      return n
    else
      value = fibo(n-1) + fibo(n-2)
      return value
    end
  end

  # Display the Fibonacci sequence.
  (1..40).each do |number|
    puts "fibo(#{number}) = #{fibo(number)}"
  end
}

Ruby时代1.9.3:55.989000 0.000000 55.989000(55.990000)
时报JRuby 1.7.9:51.629000 0.000000 51.629000(51.629000)
来源( http://rayhightower.com/blog/2014/04/12/recursion-and-memoization/?utm_source = ruby​​weekly )

Times Ruby 1.9.3: 55.989000 0.000000 55.989000 ( 55.990000)
Times JRuby 1.7.9: 51.629000 0.000000 51.629000 ( 51.629000)
source( http://rayhightower.com/blog/2014/04/12/recursion-and-memoization/?utm_source=rubyweekly )

这里是记住答案的版本，很清楚为什么对我来说这么快.完成数学运算后，以下任何请求都将在O(1)时间内运行，因此，当它包含在循环中时，在最坏的情况下仍会在O(N)时间内运行:

Here is the version which memoizes answers, it is clear why this is fast to me. Once it has done the math any following request runs in O(1) time, so when it included in a loop it still runs in O(N) time in the worst case:

puts Benchmark.measure {
  # Fibonacci numbers WITH memoization.

  # Initialize the memoization array.
  @scratchpad = []
  @max_fibo_size = 50
  (1..@max_fibo_size).each do |i|
    @scratchpad[i] = :notcalculated
  end

  # Calculate the nth Fibonacci number, f(n).
  def fibo (n)
    if n > @max_fibo_size
      return "n must be #{@max_fibo_size} or less."
    elsif n <= 1
      return n
    elsif @scratchpad[n] != :notcalculated
      return @scratchpad[n]
    else
      @scratchpad[n] = fibo(n-1) + fibo(n-2)
      return @scratchpad[n]
    end
  end

  # Display the Fibonacci sequence.
  (1..40).each { |number|
    puts "fibo(#{number}) = #{fibo(number)}"
  }
}

次Ruby 1.9.3:0.000000 0.000000 0.000000(0.025000)
时代JRuby 1.7.9:0.027000 0.000000 0.027000(0.028000)
来源( http://rayhightower.com/blog/2014/04/12/recursion-and-memoization/?utm_source = ruby​​weekly )

Times Ruby 1.9.3: 0.000000 0.000000 0.000000 ( 0.025000)
Times JRuby 1.7.9: 0.027000 0.000000 0.027000 ( 0.028000)
Source( http://rayhightower.com/blog/2014/04/12/recursion-and-memoization/?utm_source=rubyweekly )

该版本的尾调用递归版本几乎立即运行:

The version tail call recursion version of this runs pretty much instantly:

puts Benchmark.measure {
  # Calculate the nth Fibonacci number, f(n). Using invariants
  def fibo_tr(n, acc1, acc2)
    if n == 0
      0
    elsif n < 2
      acc2
    else
      return fibo_tr(n - 1, acc2, acc2 + acc1)
    end
  end

  def fibo (n)
    fibo_tr(n, 0, 1)
  end 

  # Display the Fibonacci sequence.
  (1..50).each do |number|
    puts "fibo(#{number}) = #{fibo(number)}"
  end
}

红宝石倍数1.9.3:0.000000 0.000000 0.000000(0.021000)
时代JRuby 1.7.9:0.041000 0.000000 0.041000(0.041000)
来源( https://gist.github.com/mvidaurre/11006570 )

Times Ruby 1.9.3: 0.000000 0.000000 0.000000 ( 0.021000)
Times JRuby 1.7.9: 0.041000 0.000000 0.041000 ( 0.041000)
Source ( https://gist.github.com/mvidaurre/11006570 )

推荐答案

尾递归在这里没有区别.实际上，Ruby并没有做任何优化尾调用的操作.

Tail recursion is not the difference here. In fact, Ruby does not do anything to optimize tail calls.

区别在于，朴素算法每次被调用都会递归调用两次，从而获得O(2 ⁿ )性能，这意味着运行时间随着N的增加呈指数增长.尾声呼叫版本以线性时间运行.

The difference is that the naive algorithm recursively calls itself twice each time it's called, giving O(2ⁿ) performance, which means the runtime goes up exponentially as N increases. The tail-call version runs in linear time.

这篇关于尾部呼叫优化是所有可以解释这种性能差异的原因吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！