Factorial memoization in R

Question

ich diese Funktion hat eine Fakultät von Zahl zu finden

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

Jetzt möchte ich memoization in R. Ich habe Grundidee auf R implementieren und zu versuchen, sie zu implementieren. Aber ich bin mir nicht sicher, ob es so weiter geht. Könnten Sie bitte auch dieses Thema erläutern? Danke im Voraus. memoized Factorial

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

Vor allem, wenn Sie eine effiziente Implementierung benötigen, verwenden factorial Funktion des R. Schreibe es nicht selbst. Dann ist die Fakultät eine gute Übung für das Verständnis Rekursion:

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

myfactorial(10) 
#[1] 3628800 

Mit dieser Funktion memoization ist nur dann sinnvoll, wenn Sie beabsichtigen, immer wieder die Funktion zu verwenden. Sie können Memoization in R mithilfe von Closures implementieren. Hadley erklärt diese in 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 

Ist es tatsächlich schneller?

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 

Beachten Sie, dass microbenchmark die Funktionen (Standard) wertet das 100-fache. Da wir beim Test der memFactorial den Wert für n = 10 gespeichert haben, stellen wir nur die if Bedingungen und die Suche hier ein. Wie Sie ebenfalls sehen können, ist die Implementierung von R, die hauptsächlich in C geschrieben ist, schneller.

Ein besseres (und einfacheres) Beispiel implementiert Fibonacci-Zahlen. Hier profitiert der Algorithmus selbst von Memoization.

#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