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 <wdun...@tibco.com> Date: Thursday, September 3, 2009 6:41 pm Subject: RE: [R] Recursion is slow To: Bryan Keller <bskel...@wisc.edu>, r-help@r-project.org > Bill Dunlap > TIBCO Software Inc - Spotfire Division > wdunlap tibco.com > > > -----Original Message----- > > From: r-help-boun...@r-project.org > > [mailto:r-help-boun...@r-project.org] On Behalf Of Bryan Keller > > Sent: Thursday, September 03, 2009 2:11 PM > > To: r-help@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@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. > > ______________________________________________ R-help@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.
