Given two arrays of elements:aaabbccdefaa zzzccddafgzzI 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 -> 000112234500canonical <- function(input){  output <- input  labels <- unique(input)  nlabels <- length(labels)  for (i in 1:nlabels){    output[grep(labels[i], input)] <- i  }  return(output)}# try itinput <- 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 1Can this R function be faster? 
Fast canonical indexing of elements in array
performance;combinatorics;r
First, why return a vector of characters when the output data is clearly about integers? Instead of initializingoutput <- inputi.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] TRUEidentical(canonical2(input), canonical3(input))# [1] TRUEmicrobenchmark(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