これらのメモ機能はなぜ異なっていますか？

Question

2つの異なる方法でmemoiseを関数に使用すると、2つの異なる動作が得られ、その理由を理解したいと思います。正確な入力が前に見てきた場合stratagy 2が速いだけであるのに対し、それは、再帰的な結果を再利用するよう

# Non Memoised function 
fib <- function(n) { 
    if (n < 2) return(1) 
    fib(n - 2) + fib(n - 1) 
} 

system.time(fib(23)) 
system.time(fib(24)) 

library(memoise) 

# Memoisation stragagy 1 
fib_fast <- memoise(function(n) { 
    if (n < 2) return(1) 
    fib_fast(n - 2) + fib_fast(n - 1) 
}) 

system.time(fib_fast(23)) 
system.time(fib_fast(24)) 

# Memoisation strategy 2 
fib_not_as_fast <- memoise(fib) 

system.time(fib_not_as_fast(23)) 
system.time(fib_not_as_fast(24)) 

戦略1は、本当に速いです。

これがなぜ私に説明できますか？

Answer 1

理由は簡単だと思います。遅い場合は、関数fib_not_as_fastがメモされます。関数内でfibが呼び出され、ではなく、がメモされます。より詳細にするには、fib_not_so_fast(24)を計算するときは、関数内にfib(22) + fib(23)があります。これらの両方はメモされていません。

ただし、fib_fastでは、再帰処理でもメモ化されたバージョンを使用します。したがって、この場合、fib_fast(24)はfib_fast(22) + fib_fast(23)を評価する必要があります。これらの関数呼び出しは、fib_fast(23)と計算されてメモされているので、すでに発生しています。