[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, [EMAIL PROTECTED]
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
______________________________________________
R-devel@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-devel
