R 中的阶乘记忆

Question

我写这个函数是为了求一个数的阶乘

fact <- function(n) {
    if (n < 0){
      cat ("Sorry, factorial does not exist for negative numbers", "\n")
    } else if (n == 0){
      cat ("The factorial of 0 is 1", "\n")
    } else {
    results = 1
    for (i in 1:n){
      results = results * i
    }
    cat(paste("The factorial of", n ,"is", results, "\n"))
    }
}

现在我想在 R 中实现 Memoization。我对 R 有基本的想法并尝试使用它们来实现。但我不确定这是前进的方向。你能否也详细说明这个话题。预先感谢。记忆阶乘

    fact_tbl <- c(0, 1, rep(NA, 100))
    fact_mem <- function(n){
          stopifnot(n > 0)
          if(!is.na(fib_tbl[n])){
           fib_tbl[n]
    } else {
       fact_tbl[n-1] <<- fac_mem(n-1) * n
     }
   }

   print (fact_mem(4))

Answer 1

首先，如果你需要一个高效的实现，使用R的factorial函数。不要自己写。然后，阶乘是理解递归的一个很好的练习：

myfactorial <- function(n) {
  if (n == 1) return(1)
  n * myfactorial(n-1)
}

myfactorial(10)
#[1] 3628800

只有当您打算重复使用该功能时，记忆功能才有用。您可以使用闭包在 R 中实现记忆。 Hadley 在 his book.

中解释了这些

createMemFactorial <- function() {
  res <- 1
  memFactorial <- function(n) {
    if (n == 1) return(1)

    #grow res if necessary
    if (length(res) < n) res <<- `length<-`(res, n)

    #return pre-calculated value
    if (!is.na(res[n])) return(res[n])

    #calculate new values
    res[n] <<- n * factorial(n-1)
    res[n]
  }
  memFactorial
}
memFactorial <- createMemFactorial()

memFactorial(10)
#[1] 3628800

它真的更快吗？

library(microbenchmark)
microbenchmark(factorial(10),
               myfactorial(10), 
               memFactorial(10))
#Unit: nanoseconds
#             expr  min     lq    mean median     uq   max neval cld
#    factorial(10)  235  264.0  348.02  304.5  378.5  2463   100 a  
#  myfactorial(10) 4799 5279.5 6491.94 5629.0 6044.5 15955   100   c
# memFactorial(10)  950 1025.0 1344.51 1134.5 1292.0  7942   100  b

请注意，microbenchmark 计算函数（默认）100 次。由于我们在测试 memFactorial 时存储了 n = 10 的值，因此我们仅对 if 条件和查找计时。正如您还看到的那样，主要用 C 编写的 R 的实现速度更快。

一个更好（也更容易）的示例实现斐波那契数列。这里算法本身受益于记忆。

#naive recursive implementation
fib <- function(n)  {
  if(n == 1 || n == 2) return(1)
  fib(n-1) + fib(n-2)
}

#with memoization
fibm <- function(n)  {
  if(n == 1 || n == 2) return(1)

  seq <- integer(n)
  seq[1:2] <- 1

  calc <- function(n) {
    if (seq[n] != 0) return(seq[n])
    seq[n] <<- calc(n-1) + calc(n-2)
    seq[n]
  }

  calc(n)
}

#try it:
fib(20)
#[1] 6765
fibm(20)
#[1] 6765

#Is memoization faster?
microbenchmark(fib(20),
               fibm(20))
#Unit: microseconds
#     expr      min       lq       mean    median        uq       max neval cld
# fib(20)  8005.314 8804.130 9758.75325 9301.6210 9798.8500 46867.182   100   b
#fibm(20)    38.991   44.798   54.12626   53.6725   60.4035    97.089   100  a

R 中的阶乘记忆

Factorial Memoization in R

r

memoization

factorial