[R] Re cursion is slow

[jim holtman]

Most of the time was being spent within the 'sapply' call.  Here is a
list from Rprof:

  0  18.4 root
  1.   18.4 system.time
  2. .   12.9 A1
  3. . .   12.9 sapply
  4. . . .   12.9 lapply
  5. . . . |   12.9 FUN
  6. . . . | .   12.9 sapply
  7. . . . | . .   12.9 lapply
  8. . . . | . . .   12.9 FUN
  9. . . . | . . . .   12.9 sapply
 10. . . . | . . . . |   12.8 lapply
 11. . . . | . . . . | .   12.8 FUN
 12. . . . | . . . . | . .   12.8 sapply
 13. . . . | . . . . | . . .   12.8 lapply
 14. . . . | . . . . | . . . .   12.8 FUN
 15. . . . | . . . . | . . . . |   12.7 sapply
 16. . . . | . . . . | . . . . | .   12.5 lapply
 17. . . . | . . . . | . . . . | . .   12.5 FUN
 18. . . . | . . . . | . . . . | . . .   12.4 sapply
 19. . . . | . . . . | . . . . | . . . .   10.8 lapply
 20. . . . | . . . . | . . . . | . . . . |   10.4 FUN
 21. . . . | . . . . | . . . . | . . . . | .    9.8 sapply
 22. . . . | . . . . | . . . . | . . . . | . .    4.3 unique
 23. . . . | . . . . | . . . . | . . . . | . . .    1.6 unique.default
 23. . . . | . . . . | . . . . | . . . . | . . .    1.5 unlist
 24. . . . | . . . . | . . . . | . . . . | . . . .    1.3 lapply
 22. . . . | . . . . | . . . . | . . . . | . .    4.0 lapply
 23. . . . | . . . . | . . . . | . . . . | . . .    2.4 FUN
 19. . . . | . . . . | . . . . | . . . .    1.1 unique
  2. .    5.3 A0
  3. . .    5.3 A0
  4. . . .    5.3 A0
  5. . . . |    5.3 A0
  6. . . . | .    5.2 A0
  7. . . . | . .    5.1 A0
  8. . . . | . . .    4.6 A0
  9. . . . | . . . .    3.3 A0

My guess is that you are at least 6 levels of calls down in the sapply
and within that, the 'unique' and 'lapply' split the time between
them.  Notice that for A0, it is the only function being recorded.

On Thu, Sep 3, 2009 at 5:23 PM, Ben Bolker<bolker at ufl.edu> wrote:
>
>
>
> Bryan Keller wrote:
>>
>> 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)
>> }
>>
>> -------------
>> 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.
>>
>>
>
> Can anyone tell me why my version takes TWICE AS LONG (to my surprise)?
>
>
> A0 <- 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+(A0(T[1:(lt-1)],(m-u))))
>  }
>  return(R)
> }
>
> A1 <- function(T,m) {
>  lt <- length(T)
>
>  if (lt == 1) {
>    return(as.numeric(0 <= m & m <= T[1]))
>  }
>  sum(sapply(m-(0:T[lt]),A1,T=T[-lt]))
> }
>
> system.time(a0 <- A0(1:8,20)) ## about 5 secs
> system.time(a1 <- A1(1:8,20)) ## about 11 secs
>
> --
> View this message in context: http://www.nabble.com/Recursion-is-slow-tp25284189p25284359.html
> Sent from the R help mailing list archive at Nabble.com.
>
> ______________________________________________
> 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.
>



-- 
Jim Holtman
Cincinnati, OH
+1 513 646 9390

What is the problem that you are trying to solve?