[R] filling a list faster

[Prof Brian Ripley]

On Fri, 13 Jul 2007, Philippe Grosjean wrote:

> If all the data coming from your iterations are numeric (as in your toy
> example), why not to use a matrix with one row per iteration? Also, do
> preallocate the matrix and do not add row or column names before the end
> of the calculation. Something like:
>
> > m <- matrix(rep(NA, 3*10^5), ncol = 3)
> > system.time(for(i in (1:10^5)) m[i, ] <- c(i,i+1,i))
>    user  system elapsed
>   1.362   0.033   1.424
>
> That is, about 1.5sec on my Intel Duo Core 2.33Mhz MacBook Pro, compared to:
>
> > l <- list("1"<-c(1,2,3))
> > system.time(for(i in (1:10^5)) l[[length(l)+1]] <- c(i,i+1,i))
>    user  system elapsed
> 191.629  49.110 248.454
>
> ... more than 4 minutes for your code.
>
> By the way, what is your "very fast machine", that is actually four
> times faster than mine (grrrrr!)?

He said 'over a minute', not how long exactly.
But it is not just the machine but also the OS: memory management on MacOS 
(it you are running MacOS) is known to be slow under some circumstances.
It took about 100s under 64-bit Linux on my 2.4Ghz Intel Core 2 Duo.

Preallocating the list helps here

l <- vector("list", 10^5)
system.time(for(i in (1:10^5)) l[[i]] <- c(i,i+1,i))

takes well under a second.

If you don't know the length and know an upper bound, just use that.
The storage allocated is only one pointer per element.  And if you don't 
even know an upper bound, start with a reasonable number and use

length(l) <- 1.5*length(l)

when you need to.

There are some ideas for doing this internally (R vectors have a LENGTH 
and TRUELENGTH field and so could over-allocate).  The problem is that 
they would penalize careful coding to ameliorate the effects of careless 
coding.  (One of the most basic points in S/R programming is that you 
avoid growing vectors.)

-- 
Brian D. Ripley,                  ripley at stats.ox.ac.uk
Professor of Applied Statistics,  http://www.stats.ox.ac.uk/~ripley/
University of Oxford,             Tel:  +44 1865 272861 (self)
1 South Parks Road,                     +44 1865 272866 (PA)
Oxford OX1 3TG, UK                Fax:  +44 1865 272595