是尾巴呼叫優化所有解釋此性能差異

Question

我看到了三種不同的方式來編寫斐波那契函數的遞歸形式：數學內聯，數學內聯結果緩存和一個使用尾遞歸。我知道使用memoization將O（N）算法轉換爲O（1），緩存後的答案。但我無法理解tail call優化如何能夠提供如此大的幫助。我的印象是它可能會阻止一些副本或類似的東西。它幾乎和O（1）一樣快。 Ruby在做什麼讓這麼快？

這裏是數學內聯慢天真的實現。這顯然是最慢的O（N）時間，然後當在O（N^2）時間的顯示中循環時。

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 
} 

時報紅寶石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=rubyweekly）

這裏是一個memoizes答案版本，這很明顯爲什麼這對我來說很快。一旦它已經做任何以下請求運行在O數學（1）的時間，所以當包括在一個循環中它它仍然運行在O（N）時間在最壞的情況下：

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)}" 
    } 
} 

時報紅寶石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=rubyweekly）

的這個版本尾部調用遞歸版本的運行幾乎瞬間：

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）

Answer 1

尾遞歸是不是這裏的區別。實際上，Ruby並沒有做任何事情來優化尾部調用。

不同之處在於，天真算法在每次調用時遞歸調用兩次，給出了O（2 ⁿ）的性能，這意味着隨着N增加，運行時間呈指數增長。尾調用版本以線性時間運行。

Answer 2

TL; DR：正如Chuck已經提到的，Ruby沒有TCO。但是，執行一次遞歸而不是兩次會對您使用多少堆棧以及完成多少次迭代產生重大影響。有了這個答案，我只想指出，在某些時候，memoization版本比迭代版本更好。注意：我不是一個紅寶石程序員。它可能不是慣用代碼。

試驗表明迭代的方法是如此之快就可以從頭開始一樣快，產生的1..50 FIB爲您的記憶化版本重用計算在每一個方法調用上述3

我覺得1 ..50的速度如此之快，以至於看看迭代實際上是否更快，並不是一個可靠的方法。我改變了memopization版本：

# Initialize the memoization array. 
@scratchpad = [] 

# Calculate the nth Fibonacci number, f(n). 
def fibo (n) 
    if n <= 1 
    return n 
    end 
    if @scratchpad[n].nil? 
    @scratchpad[n] = fibo(n-1) + fibo(n-2) 
    end 
    return @scratchpad[n] 
end 

我再變循環到這一點：

(1..5000).each { |number| 
    fibo(number) # no need to time character output 
} 

這裏是我的計算機上的結果：

Iteration: 6.260000 0.010000 6.270000 ( 6.273362) 
Memoization: 0.000000 0.000000 0.000000 ( 0.006943) 

我用：

ruby -v 
ruby 1.9.3p194 (2012-04-20 revision 35410) [x86_64-linux] 

增加memoiza版本到1..50000仍然比迭代版本快得多。原因是迭代每次都從頭開始，而memoization版本有一個更無效的算法，但memoization使它只能爲每個數字遞歸最多兩次，因爲我們有fib(n-1)和fib(n-2) in the array when calculating fib（n）`。

當然最慢的有O(fib(n))。迭代有O(n)。隨着記憶的fib(n-2)是免費的，當計算fib(n-1)，所以我們回到O(n)，但在你的測試中，你計算之前的斐波那契數字，因此在實踐中，從1..x每個單獨的迭代是O(1)。如果你從最高的數字開始，第一次迭代將是O(n)，並且接下來的每一次將是O(1)。