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

问题描述 投票:5回答:1

我看到如果我以两种不同的方式对函数使用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,真的很快,因为它重用了递归结果,而stratagy 2只有在之前看到过确切的输入时才会很快。

有人能解释一下为什么会这样吗?

r memoization memoise
1个回答
5
投票

我认为原因很简单。在慢的情况下,函数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)并因此被记忆。

© www.soinside.com 2019 - 2024. All rights reserved.