[R] extremely slow recursion in R?

Fri Aug 25 16:28:23 CEST 2006

i tried fib(30):

R: 8.99s
Python (interpreted): 0.96s
Python (interpreted but using psyco library): 0.03s
C++: 0.015s

cheers
Damien

 --- On Fri 08/25, Joerg van den Hoff < j.van_den_hoff at fz-rossendorf.de > wrote:
From: Joerg van den Hoff [mailto: j.van_den_hoff at fz-rossendorf.de]
To: tlumley at u.washington.edu
     Cc: jg_liao at yahoo.com, r-help at stat.math.ethz.ch
Date: Fri, 25 Aug 2006 13:52:04 +0200
Subject: Re: [R] extremely slow recursion in R?

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 at 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.