Thomas Lumley wrote:
> 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
>
maybe someone's interested:
I made the same observation of seemingly very slow recursion recently:
just for fun I used the (in)famously inefficient
fib <- function(n = 1) {
if (n < 2)
fn <- 1
else
fn <- fib(n - 1) + fib(n - 2)
fn
}
for calculating the fibonacci numbers and compared `fib(30)' (about
1.3e6 recursive function calls ...) to some other languages (times in sec):
language time
==============
C 0.034 (compiled, using integers)
Ocaml 0.041 (compiled, using integers)
Ocaml 0.048 (interpreted, using integers)
C 0.059 (compiled, using floats)
Lua 1.1
ruby 3.4
R 21
octave 120
apart from octave (which seems to have a _real_ issue with recursive
function calls), R is by far the slowest in this list and still a factor
7-20 slower than the interpreter based Lua and ruby. the speed loss
compared to C or Ocaml is about a factor of 350-600 here (Ocaml keeps
its speed more or less in this simple example even in 'script mode',
which is remarkable, I think (and it usually loses only a factor of
about 7 or so in script mode compared to the compiled variant)
for the specialists the bad performance of R in this situation might not
be surprising, but I was not aware that recursive function calls are
seemingly as expensive as explicit loops (where the execution time ratio
of R to C again is of the same order, i.e. =~ 400).
of course, such comparsions don't make too much sense: the reason to use
R will definitely not be its speed (which, luckily, often does not
matter), but the combination of flexible language, the number of
available libraries and the good 2D graphics.
joerg
______________________________________________
R-help@stat.math.ethz.ch 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.
