Fast canonical indexing of elements in array 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 -&gt; 000112234500
canonical &lt;- function(input){
  output &lt;- input
  labels &lt;- unique(input)
  nlabels &lt;- length(labels)
  for (i in 1:nlabels){
    output[grep(labels[i], input)] &lt;- i
  }
  return(output)
}

# try it
input &lt;- c(&quot;a&quot;,&quot;a&quot;,&quot;a&quot;,&quot;b&quot;,&quot;b&quot;,&quot;c&quot;,&quot;c&quot;,&quot;d&quot;,&quot;e&quot;,&quot;f&quot;,&quot;a&quot;,&quot;a&quot;)
canonical(input)

&gt; [1] &quot;1&quot; &quot;1&quot; &quot;1&quot; &quot;2&quot; &quot;2&quot; &quot;3&quot; &quot;3&quot; &quot;4&quot; &quot;5&quot; &quot;6&quot; &quot;1&quot; &quot;1&quot;

Can this R function be faster?
First, why return a vector of characters when the output data is clearly about integers? Instead of initializing

output &lt;- input


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

output &lt;- 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]] &lt;- 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 &lt;- function(input){
   labels &lt;- unique(input)
   match(input, labels)
}


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

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


Comparing speeds:

library(microbenchmark)
input &lt;- 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