Given two arrays of elements:



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

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

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

Can this R function be faster?


1 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:

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.