What is the internal data structure of a list & is preallocation useful?
I understand it is useful to preallocate a vector or a matrix, because
they are always stored in a contiguous memory block.
However, in terms of a list, it can contains elements of difference length
and modes. So my first guess is that a list might merely contains pointers
to the true address of its elements. (Otherwise, an minor update e.g.
myList <- list(a=1:2, b=4:20); myList$a <- 1:4 would require copy the
whole list rather than modify only a). Am I correct here?
Since a list can be accessed via indices, it doesn't seem to be
implemented as a hashtable, so, does myList$a (element lookup by name)
have time complexity O(n) instead of O(1)?
Here comes to preallocation. How does it look like for a list? Does it
only preallocate the memory for the pointers? If that's the case, I don't
see any use since there won't be much data copying for pointers anyway.
For example
myList <- list()
myList$a <- 1:100000
myList$b <- 1:100001
myList$c <- 1:100002
myList$d <- 1:100003
would this be very inefficient compared to
myList<-list(a=1:100000,b=1:100001,c=1:100002,d=1:100003) due to no
preallocation? Or no noticeable performance difference at all no matter
how large a,b,c,d are because the first one copies only pointers a few
times more?
No comments:
Post a Comment