[R] Recursion is slow
Bryan Keller
bskeller at wisc.edu
Fri Sep 4 04:57:53 CEST 2009
Bill,
Thanks for the great tips for speeding up functions in your response. Those are really useful for me. Even with the improvements the recursion is still many times slower than I need it to be in order to make it useful in R. I may just have to suck it up and call a compiled language.
Bryan
-------------
Bryan Keller, Doctoral Student/Project Assistant
Educational Psychology - Quantitative Methods
The University of Wisconsin - Madison
----- Original Message -----
From: William Dunlap <wdunlap at tibco.com>
Date: Thursday, September 3, 2009 6:41 pm
Subject: RE: [R] Recursion is slow
To: Bryan Keller <bskeller at wisc.edu>, r-help at r-project.org
> Bill Dunlap
> TIBCO Software Inc - Spotfire Division
> wdunlap tibco.com
>
> > -----Original Message-----
> > From: r-help-bounces at r-project.org
> > [mailto:r-help-bounces at r-project.org] On Behalf Of Bryan Keller
> > Sent: Thursday, September 03, 2009 2:11 PM
> > To: r-help at r-project.org
> > Subject: [R] Recursion is slow
> >
> > The following recursion is about 120 times faster in C#. I
> > know R is not known for its speed with recursions but I'm
> > wondering if anyone has a tip about how to speed things up in R.
> >
> > #"T" is a vector and "m" is a number between 1 and sum(T)
> >
> > A <- function(T,m) {
> > lt <- length(T)
> >
> > if (lt == 1) {
> > if (0 <= m & m <= T[1]) {
> > return(1)
> > } else {
> > return(0)
> > }
> > }
> > R <- 0
> > for (u in 0:T[lt]) {
> > R <- (R+(A(T[1:(lt-1)],(m-u))))
> > }
> > return(R)
> > }
> >
>
> For starters, remove all repeated calculations from
> the for loop. Then vectorize the length(T)==2 case
> to avoid a lot of calls to the scalar case. Finally,
> I noticed that the answer was independent of the
> order of T and that putting it in reverse sorted order
> was the faster order, so I did that. I use default
> values of arguments so you don't have to supply
> derived values when you start but the recursions
> don't have to recompute some things.
>
> B <- function(T,m,lt=length(T), Tsorted = rev(sort(T))) {
> if (lt == 1L) {
> R <- as.integer(m <= Tsorted && 0L <= m)
> } else if (lt == 2L) {
> mu <- m - (0:Tsorted[2L])
> R <- sum(mu <= Tsorted[1L] & 0L <= mu)
> } else {
> R <- 0L
> lt1 <- lt-1L
> T1 <- Tsorted[1:lt1]
> for (mu in m-(0:Tsorted[lt])) {
> R <- R + B(unused, mu, lt1, T1)
> }
> }
> R
> }
>
> E.g.,
>
> > system.time(A( c(20,40,35,21,31), 100))
> user system elapsed
> 13.23 0.08 12.93
> > system.time(B( c(20,40,35,21,31), 100))
> user system elapsed
> 0.35 0.00 0.33
> > A( c(20,40,35,21,31), 100)
> [1] 193363
> > B( c(20,40,35,21,31), 100)
> [1] 193363
>
> Bill Dunlap
> TIBCO Software Inc - Spotfire Division
> wdunlap tibco.com
>
> > -------------
> > Bryan Keller, Doctoral Student/Project Assistant
> > Educational Psychology - Quantitative Methods
> > The University of Wisconsin - Madison
> >
> > ______________________________________________
> > R-help at r-project.org 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.
> >
More information about the R-help
mailing list