为什么这些记忆功能不同？

Question

我发现如果我以两种不同的方式在一个函数上使用 memoise，我会得到两种不同的行为，我想了解其中的原因。

# 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 非常快，因为它重用了递归结果，而策略 2 仅在之前已经看到确切输入的情况下才快。

谁能给我解释一下这是为什么？

Answer 1

我觉得原因很简单。在缓慢的情况下，函数 fib_not_as_fast 被记忆。在函数内部，调用了 fib，这是 not 记忆的。更详细地说：当您计算 fib_not_so_fast(24) 时，在函数内部您有 fib(22) + fib(23)。这两个都没有记忆

然而，在 fib_fast 中，您也在递归中使用记忆版本。因此，在这种情况下，fib_fast(24) 需要评估 fib_fast(22) + fib_fast(23)。当您计算 fib_fast(23) 并因此被记忆时，这两个函数调用都已经发生。

有效的方法是在函数定义后记忆它。因此，只需将函数 fib() 重新定义为 fib <- memoise(fib) 即可。

为什么这些记忆功能不同？

why are these memoised functions different?

r

memoization

memoise