[R] extremely slow recursion in R?
Joerg van den Hoff
j.van_den_hoff at fz-rossendorf.de
Fri Aug 25 13:52:04 CEST 2006
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
More information about the R-help
mailing list