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 < [EMAIL PROTECTED] > wrote:
From: Joerg van den Hoff [mailto: [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Cc: [EMAIL PROTECTED], [email protected]
Date: Fri, 25 Aug 2006 13:52:04 +0200
Subject: Re: [R] extremely slow recursion in R?
Thomas Lumley wrote:<br>> On Thu, 24 Aug 2006, Jason Liao wrote:<br>> <br>>> I
recently coded a recursion algorithm in R and ir ran a few days<br>>> without
returning any result. So I decided to try a simple case of<br>>> computing
binomial coefficient using recusrive relationship<br>>><br>>> choose(n,k) =
choose(n-1, k)+choose(n-1,k-1)<br>>><br>>> I implemented in R and Fortran 90
the same algorithm (code follows).<br>>> The R code finishes 31 minutes and the
Fortran 90 program finishes in 6<br>>> seconds. So the Fortran program is 310
times faster. I thus wondered if<br>>> there is room for speeding up recursion
in R. Thanks.<br>>><br>> <br>> Recursive code that computes the same case many
times can often be sped up <br>> by memoization, eg<br>> <br>>
memo<-new.env(hash=TRUE)<br>> chewse<-function(n,k) {<br>> if (n==k)
return(1)<br>> if(k==1) return(n)<br>> <br>>
if(exists(paste(n,k),memo,inherits=FALSE))<br>>
return(get(paste(n,k),memo))<br>>
rval<-chewse(n-1,k)+chewse(n-1,k-1)<br>>
assign(paste(n,k),rval,envir=memo)<br>> return(rval)<br>> }<br>> <br>>
This idea was discussed in an early Programmers' Niche article by Bill <br>>
Venables in R News.<br>> <br>> However, I'm surprised that you're surprised
that compiled Fortran 90 is <br>> 310 times faster than interpreted R. That
would be about what I would <br>> expect for code that isn't making use of
vectorized functions in R.<br>> <br>> <br>> -thomas<br>><br><br>maybe
someone's interested:<br>I made the same observation of seemingly very slow
recursion recently: <br>just for fun I used the (in)famously
inefficient<br><br>fib <- function(n = 1) {<br> if (n < 2)<br> fn <-
1<br> else<br> fn <- fib(n - 1) + fib(n - 2)<br> fn<br>}<br><br>for
calculating the fibonacci numbers and compared `fib(30)' (about <br>1.3e6
recursive function calls ...) to some other languages (times in
sec):<br><br>language time<br>==============<br>C !
0.034 (compiled, using integers)<br>Ocaml 0.041 (compiled, using
integers)<br>Ocaml 0.048 (interpreted, using integers)<br>C
0.059 (compiled, using floats)<br>Lua 1.1<br>ruby 3.4<br>R
21<br>octave 120<br><br>apart from octave (which seems to have a _real_
issue with recursive <br>function calls), R is by far the slowest in this list
and still a factor <br>7-20 slower than the interpreter based Lua and ruby. the
speed loss <br>compared to C or Ocaml is about a factor of 350-600 here (Ocaml
keeps <br>its speed more or less in this simple example even in 'script mode',
<br>which is remarkable, I think (and it usually loses only a factor of
<br>about 7 or so in script mode compared to the compiled variant)<br><br>for
the specialists the bad performance of R in this situation might not <br>be
surprising, but I was not aware that recursive function calls are <br>seemingly
as expensive as explicit loops (where the execution time rati!
o
<br>of R to C again is of the same order, i.e. =~ 400).<br><br>of course, such
comparsions don't make too much sense: the reason to use <br>R will definitely
not be its speed (which, luckily, often does not <br>matter), but the
combination of flexible language, the number of <br>available libraries and the
good 2D
graphics.<br><br><br><br>joerg<br><br>______________________________________________<br>[email protected]
mailing list<br>https://stat.ethz.ch/mailman/listinfo/r-help<br>PLEASE do read
the posting guide http://www.R-project.org/posting-guide.html<br>and provide
commented, minimal, self-contained, reproducible code.<br>
______________________________________________
[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.
