Q:

Very slow assignment to vector when unnamed (becoming named) in R

my code hit a performance snag that I could reproduce in this snippet
rm (z)
z = c()
system.time({z[as.character(1:10^5)] = T})
user  system elapsed 
48.716   0.023  48.738 

I tried to pre-allocate z with
z = logical(10^5)

but it makes no difference.
Then I pre-allocated names with 
names(z) = character(10^5)

Still no speed difference.
system.time({z[as.character(1:10^5)] = T})
user  system elapsed 
50.345   0.035  50.381 

If I repeat the test, with or without pre-allocations, speed is back to reasonable levels (more than 100X faster).
system.time({z[as.character(1:10^5)] = T})
user  system elapsed 
0.037   0.001   0.039 

Finally I found a not-quite-workaround:
names(z) = as.character(1:10^5)
system.time({z[as.character(1:10^5)] = T})
user  system elapsed 
0.035   0.001   0.035 

To go back to the slow time, you can rm(z) and initialize it in a different way, but even changing names back to something else flips the time back to slow.
I am saying this is not quite a workaround because I don't understand why it works so it's hard to generalize to the actual use case where I don't know the names in advance. Of course given the two orders of magnitude difference, one suspects that some non-vectorized or interpreter-heavy operation is involved, but you can see my code is loop free and doesn't invoke any interpreted code that I can think of. Then trying with smaller vectors, I saw that the execution time grows much faster than linear, maybe quadratic, which points to something else. The question is what is the reason for this speed behavior and what is the solution to make it faster.
Platform is OS X mt lion with R 15.2. Thanks
Antonio

A:

I can speculate what is going on, since the timings below seem to go along my assumption.
Here are the three relevant runs:
# run 1 - slow
rm (z)
n <- 3*10^4
z <- vector("logical", n)
system.time({
z[as.character(1:n)] <- T
})
#    user  system elapsed 
#    5.08    0.00    5.10

# run 2 - fast
rm (z)
n <- 3*10^4
z <- vector("logical", n)
system.time({
names(z) <- as.character(1:n)
z[as.character(1:n)] <- T
})
#    user  system elapsed 
#    0.03    0.00    0.03 

# run 3 - slow again
rm (z)
n <- 3*10^4
z <- vector("logical", n)
system.time({
for (i in 1:n) names(z)[i] <- as.character(i)
z[as.character(1:n)] <- T
})
#    user  system elapsed 
#    6.10    0.00    6.09 

Run #3 is what I think is happening in the background, or at least something to that effect: While doing the assignment by name, R is looking for the names one at a time and if no found, assigning it at the end of the names vector. Doing this one at a time is what is killing it...

You also pointed out that pre-assigning the names as follows names(z) <- character(1:n) was not helping. Hehe, see that character(1:n) returns "" so it is not setting the names like you thought. No surprise it is not helping much. You meant to use as.character instead of character.

Finally, you ask what is the solution to make this faster? I'd say you have already found one (Run#2). You can also do:
keys   <- as.character(1:n)
values <- rep(T, n)
z <- setNames(values, keys)

A:

This seems quite fun. It does seem that R is extending the vector one element at a time for each unmatched name. Here we (a) choose only the last value, in case names are duplicated and then (b) update existing named elements and (c) append new elements
updateNamed <-
    function(z, z1)
{
    z1 <- z1[!duplicated(names(z1), fromLast=TRUE)] # last value of any dup
    idx <- names(z1) %in% names(z)                  # existing names...
    z[ names(z1)[idx] ] <- z1[idx]                  # ...updated
    c(z, z1[!idx])                                  # new names appended
}

Which works like this
> z <- setNames(logical(2), c("a", 2))
> updateNamed(z, setNames(c(TRUE, FALSE, TRUE, FALSE), c("a", 2, 2, "c")))
    a     2     c
 TRUE  TRUE FALSE   

and is faster
> n <- 3*10^4
> z <- logical(n)
> z1 <- setNames(rep(TRUE, n), as.character(1:n))
> system.time(updateNamed(z, z1))
   user  system elapsed
  0.036   0.000   0.037

It's worth thinking carefully about how names are being used, e.g., appending to a previously unnamed vector
> length(updateNamed(z, z1))
[1] 60000

while updating (with the 'last' value) a named vector
> length(updateNamed(z1, !z1))
[1] 30000

and also that as mentioned on ?"[<-" that zero-length strings "" are not matched.
> z = TRUE; z[""] = FALSE; z

 TRUE FALSE

