thr3ads.net - R help - [R] extremely slow recursion in R? [Aug 2006]

If this information is useful, please help other people find it:
Share via:

Jason Liao

2006-Aug-24 20:05 UTC

[R] extremely slow recursion in R?

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.

Jason

R code

my.choose = function(n,k)
{  
  if(k>n) value = 0.
  else if(k==0) value = 1.
  else if(k==n) value = 1.
  else value = my.choose(n-1,k) + my.choose(n-1, k-1)

  value
}

print(date())
my.choose(30,15)
print(date())



Fortran code

  recursive function choose(n, k) result(value)
  implicit none
  integer n, k
  double precision value
  if(k>n) then
    value = 0.
  elseif(k==0) then
    value = 1.
  else if(k==n) then
    value = 1.
  else
    value = choose(n-1, k) + choose(n-1, k-1)
  end if
  end function
  
  program main
    write(*,*) choose(30, 15)
  end program

Jason Liao, http://www.geocities.com/jg_liao
Department of Epidemiology and Biostatistics
Drexel University School of Public Health
245 N. 15th Street, Mail Stop 660
Philadelphia, PA 19102-1192
phone 215-762-3934

Gabor Grothendieck

2006-Aug-24 20:15 UTC

head link

[R] extremely slow recursion in R?

There was some discussion here:
http://finzi.psych.upenn.edu/R/Rhelp02a/archive/73646.html

On 8/24/06, Jason Liao <jg_liao at yahoo.com>
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.
>
> Jason
>
> R code
>
> my.choose = function(n,k)
> {
>  if(k>n) value = 0.
>  else if(k==0) value = 1.
>  else if(k==n) value = 1.
>  else value = my.choose(n-1,k) + my.choose(n-1, k-1)
>
>  value
> }
>
> print(date())
> my.choose(30,15)
> print(date())
>
>
>
> Fortran code
>
>  recursive function choose(n, k) result(value)
>  implicit none
>  integer n, k
>  double precision value
>  if(k>n) then
>    value = 0.
>  elseif(k==0) then
>    value = 1.
>  else if(k==n) then
>    value = 1.
>  else
>    value = choose(n-1, k) + choose(n-1, k-1)
>  end if
>  end function
>
>  program main
>    write(*,*) choose(30, 15)
>  end program
>
> Jason Liao, http://www.geocities.com/jg_liao
> Department of Epidemiology and Biostatistics
> Drexel University School of Public Health
> 245 N. 15th Street, Mail Stop 660
> Philadelphia, PA 19102-1192
> phone 215-762-3934
>
> ______________________________________________
> 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.
>

MARK LEEDS

2006-Aug-24 20:21 UTC

head link

[R] extremely slow recursion in R?

i'm sure someone else will explain the recursion issue but , as far as your 
program running a few days, you don't have to wait this long. if you are in 
windows and do
a ctrl  alt delete and then click on processes, if the memory usage being 
used by that R process  is staying EXACTLY the same and not moving at all, 
this is a sign
( atleast i have found this to be true for my cases. i guess it may not 
always hold ) that nothing is happening and your job has gone into never 
never land or has somehow become frozen.



----- Original Message ----- 
From: "Jason Liao" <jg_liao at yahoo.com>
To: <r-help at stat.math.ethz.ch>
Sent: Thursday, August 24, 2006 4:05 PM
Subject: [R] extremely slow recursion in R?

>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.
>
> Jason
>
> R code
>
> my.choose = function(n,k)
> {
>  if(k>n) value = 0.
>  else if(k==0) value = 1.
>  else if(k==n) value = 1.
>  else value = my.choose(n-1,k) + my.choose(n-1, k-1)
>
>  value
> }
>
> print(date())
> my.choose(30,15)
> print(date())
>
>
>
> Fortran code
>
>  recursive function choose(n, k) result(value)
>  implicit none
>  integer n, k
>  double precision value
>  if(k>n) then
>    value = 0.
>  elseif(k==0) then
>    value = 1.
>  else if(k==n) then
>    value = 1.
>  else
>    value = choose(n-1, k) + choose(n-1, k-1)
>  end if
>  end function
>
>  program main
>    write(*,*) choose(30, 15)
>  end program
>
> Jason Liao, http://www.geocities.com/jg_liao
> Department of Epidemiology and Biostatistics
> Drexel University School of Public Health
> 245 N. 15th Street, Mail Stop 660
> Philadelphia, PA 19102-1192
> phone 215-762-3934
>
> ______________________________________________
> 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.
>

Thomas Lumley

2006-Aug-24 23:05 UTC

head link

[R] extremely slow recursion in R?

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
tlumley at u.washington.edu	University of Washington, Seattle

Damien Moore

2006-Aug-25 14:28 UTC

head link

[R] extremely slow recursion in R?

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:<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 ratio
<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>R-help
at stat.math.ethz.ch 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>

Apparently Analagous Threads

Search for more seemingly similar threads

R help - Aug 2006 - extremely slow recursion in R?

[R] extremely slow recursion in R?

[R] extremely slow recursion in R?

[R] extremely slow recursion in R?

[R] extremely slow recursion in R?

[R] extremely slow recursion in R?

Apparently Analagous Threads