On Thu, 24 Aug 2006, Jason Liao wrote:
> I recently coded a recursion algorithm in R and ir ran a few days
> without returning any result. So I decided to try a simple case of
> computing binomial coefficient using recusrive relationship
>
> choose(n,k) = choose(n-1, k)+choose(n-1,k-1)
>
> I implemented in R and Fortran 90 the same algorithm (code follows).
> The R code finishes 31 minutes and the Fortran 90 program finishes in 6
> seconds. So the Fortran program is 310 times faster. I thus wondered if
> there is room for speeding up recursion in R. Thanks.
>
Recursive code that computes the same case many times can often be sped up
by memoization, eg
memo<-new.env(hash=TRUE)
chewse<-function(n,k) {
if (n==k) return(1)
if(k==1) return(n)
if(exists(paste(n,k),memo,inherits=FALSE))
return(get(paste(n,k),memo))
rval<-chewse(n-1,k)+chewse(n-1,k-1)
assign(paste(n,k),rval,envir=memo)
return(rval)
}
This idea was discussed in an early Programmers' Niche article by Bill
Venables in R News.
However, I'm surprised that you're surprised that compiled Fortran 90 is
310 times faster than interpreted R. That would be about what I would
expect for code that isn't making use of vectorized functions in R.
-thomas
Thomas Lumley Assoc. Professor, Biostatistics
[EMAIL PROTECTED] University of Washington, Seattle
______________________________________________
[email protected] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
