Anyone have a clue why assigning to a list field in a RefClass is so much slower
than assigning to a plain old list?
For example, given a list of length N, if I want to assign a value to each
entry, then the running time is quadratic in N.
That is, refclass$a.list[[i]] <- value is much much slower than a.list[[i]]
<- value.
Here are numbers of inserts per second for different sized lists.
"Ordinary" refers to just assigning to a list. "Outside"
and "Inside" refer to modifying a list field directly or via a method.
(The increasing rate for "ordinary" is just because it's so fast
and there's poor precision for small Ns.)
INSERTS PER SECOND
Outside Inside Ordinary
100 5000.000 25000.000 100000.0
200 5405.405 18181.818 200000.0
400 4040.404 14814.815 200000.0
800 3041.825 9876.543 400000.0
1600 2133.333 7339.450 533333.3
3200 1753.425 4377.565 533333.3
You can see that the rate for inserts decreases dramatically as the size of the
list increases.
Quadratic running time might happen for i=1:N if there was a copy operation up
to i each time. But why is this happening for refClasses? And is there any
workaround?
Pardon my quick hacky R, but here's what generated the timings above:
tg <-
setRefClass('tg',
fields = list(tags = "list",n="integer"),
methods=list(
initialize=function(n) {
n <<- n
reset()
},
reset=function() {
tags <<- list()
tags[1:n] <<- list(rep(list(),n))
},
set=function() {
reset()
for (i in 1:length(tags)) { tags[[i]] <<- 'foo'}
}
)
)
Ns <- c(100L,200L,400L,800L,1600L,3200L)
z<-
lapply(Ns, function(n) {
t <- tg$new(n)
c(system.time(for (i in 1:n) { t$tags[[i]] <- 'foo' })[3],
system.time(t$set())[3],
system.time({tags <- list(); tags[1:n] <- list(rep(list(),n)); for (i
in 1:n) { tags[[i]] <- 'foo' }})[3]
)
})
df <- as.data.frame(t(as.data.frame(z)));
rownames(df) <- Ns
colnames(df) <- c('Outside','Inside','Ordinary')
print(Ns/df)
df$x <- Ns
qplot(x,Outside,df)
[[alternative HTML version deleted]]