为什么这些记忆化函数不同？

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

第一种策略非常快，因为它重用了递归结果，而第二种策略只有在先前看过完全相同的输入时才会很快。

能有人向我解释一下这是为什么吗？

- kmace

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)时已被记忆化。

有效的方法是在定义函数后稍后进行函数记忆化。因此，仅将函数fib()重新定义为fib <- memoise(fib)即可奏效。

- Stibu

---

跟进：假设您已经定义了 fib - 如何进行记忆化？在函数体中替换内容吗？ - Frank

“Recall”在避免这些情况方面非常有用。如果你在R中编写递归函数，那么应该使用“Recall”。 - Dason

@Dason 哦，太酷了，我不知道有这样的功能。如果我理解正确，似乎memoise包没有设置来处理这种情况。我看到fib <- function(n) {if (n < 2) return(1); Recall(n - 2) + Recall(n - 1)}和ffib <- memoise(fib)的时间相同。 - Frank

这是因为内部的斐波那契数已经被计算过了吗？我知道内部的斐波那契数没有被记忆化，但我很难理解为什么不这样做？ - kmace

fib的记忆化版本存储在fib_not_so_fast中。fib本身不会作为一个记忆化函数被存储。 - Stibu