[R] complexity of operations in R

[Bert Gunter]

Thanks, Bill, but:

> system.time(z1 <-f(n=1e5,pre=TRUE))
   user  system elapsed
   0.32    0.00    0.32
> system.time(z2 <- as.list(seq_len(1e5)))
   user  system elapsed
      0       0       0
> identical(z1,z2)
[1] TRUE

So the point is not to use an R level loop at all.

-- Bert

On Thu, Jul 19, 2012 at 9:21 AM, William Dunlap <wdunlap at tibco.com> wrote:
> Preallocation of lists does speed things up.  The following shows
> time quadratic in size when there is no preallocation and linear
> growth when there is, for size in the c. 10^4 to 10^6 region:
>> f <- function(n, preallocate) { v <- if(preallocate)vector("list",n) else list() ; for(i in seq_len(n)) v[[i]] <- i ; v }
>> identical(f(17,pre=TRUE), f(17,pre=FALSE))
> [1] TRUE
>> system.time(f(n=1e4, preallocate=FALSE))
>    user  system elapsed
>   0.324   0.000   0.326
>> system.time(f(n=2e4, preallocate=FALSE)) # 2x n, 4x time
>    user  system elapsed
>   1.316   0.012   1.329
>> system.time(f(n=4e4, preallocate=FALSE)) # ditto
>    user  system elapsed
>   5.720   0.028   5.754
>>
>> system.time(f(n=1e4, preallocate=TRUE))
>    user  system elapsed
>   0.016   0.000   0.017
>> system.time(f(n=2e4, preallocate=TRUE)) # 2x n, 2x time
>    user  system elapsed
>   0.032   0.004   0.036
>> system.time(f(n=4e4, preallocate=TRUE)) # ditto
>    user  system elapsed
>   0.068   0.000   0.069
>>
>> system.time(f(n=4e5, preallocate=TRUE)) # 10x n, 10x time
>    user  system elapsed
>   0.688   0.000   0.688
>
> Above 10^6 there is some superlinearity
>> system.time(f(n=4e6, preallocate=TRUE)) # 10x n, 20x time
>    user  system elapsed
>  11.125   0.052  11.181
>
> Bill Dunlap
> Spotfire, TIBCO Software
> wdunlap tibco.com
>
>
>> -----Original Message-----
>> From: r-help-bounces at r-project.org [mailto:r-help-bounces at r-project.org] On
>> Behalf Of Bert Gunter
>> Sent: Thursday, July 19, 2012 9:11 AM
>> To: Hadley Wickham
>> Cc: r-help at r-project.org
>> Subject: Re: [R] complexity of operations in R
>>
>> Hadley et. al:
>>
>> Indeed. And using a loop is a poor way to do it anyway.
>>
>> v <- as.list(rep(FALSE,dotot))
>>
>> is way faster.
>>
>> -- Bert
>>
>> On Thu, Jul 19, 2012 at 8:50 AM, Hadley Wickham <hadley at rice.edu> wrote:
>> > On Thu, Jul 19, 2012 at 8:02 AM, Jan van der Laan <rhelp at eoos.dds.nl> wrote:
>> >> Johan,
>> >>
>> >> Your 'list' and 'array doubling' code can be written much more efficient.
>> >>
>> >> The following function is faster than your g and easier to read:
>> >>
>> >> g2 <- function(dotot) {
>> >>   v <- list()
>> >>   for (i in seq_len(dotot)) {
>> >>     v[[i]] <- FALSE
>> >>   }
>> >> }
>> >
>> > Except that you don't need to pre-allocate lists...
>> >
>> > Hadley
>> >
>> > --
>> > Assistant Professor / Dobelman Family Junior Chair
>> > Department of Statistics / Rice University
>> > http://had.co.nz/
>> >
>> > ______________________________________________
>> > 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.
>>
>>
>>
>> --
>>
>> Bert Gunter
>> Genentech Nonclinical Biostatistics
>>
>> Internal Contact Info:
>> Phone: 467-7374
>> Website:
>> http://pharmadevelopment.roche.com/index/pdb/pdb-functional-groups/pdb-
>> biostatistics/pdb-ncb-home.htm
>>
>> ______________________________________________
>> 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.



-- 

Bert Gunter
Genentech Nonclinical Biostatistics

Internal Contact Info:
Phone: 467-7374
Website:
http://pharmadevelopment.roche.com/index/pdb/pdb-functional-groups/pdb-biostatistics/pdb-ncb-home.htm