R devel - Mar 2007 - How to create a list that grows automatically

Dear R users

I would like to know if there is a way to create a list or an array (or
anything) which grows automatically as more elements are put into it. What I
want to find is something equivalent to an ArrayList object of Java
language. In Java, I can do the following thing:

// Java code
ArrayList myArray = new ArrayList();
myArray.add("object1");
myArray.add("object2");
....
// End of java code

Thanks in advance.

Young-Jin Lee

	[[alternative HTML version deleted]]

Young-Jin Lee asked:
> 
> I would like to know if there is a way to create a list or an array (or
> anything) which grows automatically as more elements are put into 
> it. 
>
???

I think this is the default behaviour of R arrays:

x <- vector(length=0)  # create a vector of zero length
x[1] <- 2
x[10] <- 3
x[length(x) + 1] <- 4
x # 2 NA NA ... 3 4

> What I want to find is something equivalent to an ArrayList 
> object of Java language. In Java, I can do the following thing:
> 
> // Java code
> ArrayList myArray = new ArrayList();
> myArray.add("object1");
> myArray.add("object2");
> ....
> // End of java code
> 
myArray <- vector(length=0)
myArray <- c(myArray, "object1")
myArray <- c(myArray, "object2")
myArray # array with 2 strings

Alberto Monteiro

This is a bad idea as it can greatly slow things down (the details
were discussed several times on this list). What you want to do is
define from the start the length of your vector/list, then grow it (by
a large margin) only if it becomes full.
lst <- vector(mode="list", length=100000)  #assuming 100k nodes are
enough
#populate the list, then remove the unused nodes if you care to
lst <- lst[sapply(lst, function(x) {!is.null(x)})]

> -----Original Message-----
> From: r-help-bounces at stat.math.ethz.ch
> [mailto:r-help-bounces at stat.math.ethz.ch] On Behalf Of Young-Jin Lee
> Sent: Friday, March 09, 2007 11:08 AM
> To: r-help
> Subject: [R] How to create a list that grows automatically
>
> Dear R users
>
> I would like to know if there is a way to create a list or an
> array (or
> anything) which grows automatically as more elements are put
> into it. What I
> want to find is something equivalent to an ArrayList object of Java
> language. In Java, I can do the following thing:
>
> // Java code
> ArrayList myArray = new ArrayList();
> myArray.add("object1");
> myArray.add("object2");
> ....
> // End of java code
>
> Thanks in advance.
>
> Young-Jin Lee
>
> [[alternative HTML version deleted]]
>
> ______________________________________________
> R-help at stat.math.ethz.ch 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.
>

> I would like to know if there is a way to create a list or an array (or
> anything) which grows automatically as more elements are put into it. What
I
> want to find is something equivalent to an ArrayList object of Java
> language. In Java, I can do the following thing:
>
> // Java code
> ArrayList myArray = new ArrayList();
> myArray.add("object1");
> myArray.add("object2");
> ....
> // End of java code
As others have mentioned, you can do this with lists in R.

However, there is an important difference between ArrayLists in Java
and Lists in R.  In Java, when an ArrayList grows past its bound, it
doesn't allocate just enough space, it allocates a lot more, so the
next time you allocate past the end of the array, there's space
already reserved.  This gives (IIRC) amortised O(n) behaviour.  R
doesn't do this however, so has to copy the entire array every time
giving O(n^2) behaviour.

Hadley

[Moved to R-devel for a technical comment.]

On Fri, 9 Mar 2007, hadley wickham wrote:
>> I would like to know if there is a way to create a list or an array (or
>> anything) which grows automatically as more elements are put into it.
What I
>> want to find is something equivalent to an ArrayList object of Java
>> language. In Java, I can do the following thing:
>>
>> // Java code
>> ArrayList myArray = new ArrayList();
>> myArray.add("object1");
>> myArray.add("object2");
>> ....
>> // End of java code
>
> As others have mentioned, you can do this with lists in R.
>
> However, there is an important difference between ArrayLists in Java
> and Lists in R.  In Java, when an ArrayList grows past its bound, it
> doesn't allocate just enough space, it allocates a lot more, so the
> next time you allocate past the end of the array, there's space
> already reserved.  This gives (IIRC) amortised O(n) behaviour.  R
> doesn't do this however, so has to copy the entire array every time
> giving O(n^2) behaviour.
In fact this is an implementation detail.  R has both 'length' and 
'truelength' fields in its headers for vectors (including lists) and
could
grow the allocation in the same way as you report Java does.  When I asked 
Ross what the intention had been (the 'truelength' field is almost
unused)
he mentioned this potential usage.  Given that these structures are opaque 
to all but R internal code it should not be hard to change R's scheme to 
over-allocate: to decide how much to do would be harder (but say rounding 
vectors in the large allocation class up to a VM page would get a 
noticeable benefit in some usages with a negligible impact on memory 
footprint).  Backwards compatibility of save() format would be an issue.

It seems the really inefficient uses are of the type

x <- NULL
for(i in 1:10000) x <- c(x, fn(i))

and those would be unaltered.

-- 
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