代码之家 › 专栏 › 技术社区 › Styne.John.

使用动态增长表[duplicate]在R中进行记忆

rstudio r

0

Styne.John. · 技术社区 · 7 年前

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

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中实现回忆录。我对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))

0 回复 | 直到 9 年前

1

10

Roland 9 年前

首先,如果您需要一个高效的实现,请使用R factorial 作用不要自己写。那么,阶乘是理解递归的一个很好的练习:

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

myfactorial(10)
#[1] 3628800

使用此函数时,仅当您打算重复使用该函数时,备忘录才有用。可以使用闭包在R中实现备忘录化。哈德利在书中解释了这些 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 ,我们只对if条件和查找进行计时。正如您也可以看到的,R的实现(主要是用C编写的)速度更快。

一个更好(更容易)的例子实现了斐波那契数。在这里,算法本身得益于记忆。

#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