Fast canonical indexing of elements in array

Question

Given two arrays of elements:

aaabbccdefaa

zzzccddafgzz

I want to check whether these two arrays are equivalent up to a relabeling.

My strategy is to map them into a canonical form and then check whether they share the same canonical form:

# Convert aaabbccdefaa -> 000112234500
canonical <- function(input){
  output <- input
  labels <- unique(input)
  nlabels <- length(labels)
  for (i in 1:nlabels){
    output[grep(labels[i], input)] <- i
  }
  return(output)
}

# try it
input <- c("a","a","a","b","b","c","c","d","e","f","a","a")
canonical(input)

> [1] "1" "1" "1" "2" "2" "3" "3" "4" "5" "6" "1" "1"

Can this R function be faster?

Answer 1

First, why return a vector of characters when the output data is clearly about integers? Instead of initializing

output <- input

i.e., a vector of the same class as input (character), you should have used:

output <- integer(length(input))

to pre-allocate a vector of integers. Integers use less memory; you will also save time avoiding unnecessary conversions from integer to character.

Second, grep is for regular expression matching. When you do grep("a", x), you are checking if x contains an "a" which is not the same as asking if x is exactly "a". In your case, you want exact equality so having used == in output[input == labels[i]] <- i would have been more appropriate. Even better, there is the match function. It is vectorized so you can avoid the for loop and just do:

canonical2 <- function(input){
   labels <- unique(input)
   match(input, labels)
}

Last, you could look into factors. Your code is equivalent to doing:

canonical3 <- function(input) {
   labels <- unique(input)
   as.integer(factor(input, levels = labels))
}

Comparing speeds:

library(microbenchmark)
input <- sample(letters, 1e4, replace = TRUE)

identical(as.integer(canonical(input)), canonical2(input))
# [1] TRUE
identical(canonical2(input), canonical3(input))
# [1] TRUE

microbenchmark(canonical(input), canonical2(input), canonical3(input))

# Unit: microseconds
#               expr       min         lq     median         uq       max neval
 #  canonical(input) 47669.384 49870.0695 51615.3475 53604.0700 65261.986   100
#  canonical2(input)   492.921   529.9210   589.2805   635.7925   966.853   100
#  canonical3(input)   526.412   582.8405   638.5455   718.9310  3821.143   100