（速度挑战）有没有更快的方法来计算通用汉明距离的距离矩阵？

Question

我正在寻找一种更有效的方法来获取以汉明距离表示的距离矩阵。

背景

我知道有一个函数hamming.distance()来自e1071包，用于计算距离矩阵，但我怀疑当涉及到具有许多行的大矩阵时，它可能会非常缓慢，因为它应用了嵌套的for循环进行计算。

到目前为止，我在下面的代码中有一种更快的方式（见methodB）。然而，它仅适用于二进制域，即{0,1}^n。当遇到由超过2个元素组成的域时，即{0,1,2,...,K-1}^n时，它是不可用的。从这个意义上说，methodB不适用于通用哈明距离。

目标

我的目标是找到一种具有以下特点的方法：

• 仅由基本R函数组成（不使用Rcpp重新编写函数以加速）
• 对于特殊情况k=2，比我的方法methodB()更快
• 可以推广到任何正整数k
• 优于来自e1071包的hamming.distance()的速度

我的代码

library(e1071)
# vector length, i.e., number of matrix
n <- 7
# number of elements to consist of domain {0,1,...,k-1}^n
k <- 2
# matrix for computing hamming distances by rows
m <- as.matrix(do.call(expand.grid,replicate(n,list(0:k-1))))

# applying `hamming.distance()` from package "e1071", which is generic so it is available for any positive integer `k`
methodA <- function(M) hamming.distance(M)
# my customized method from base R function `dist()`, which is not available for cases `k >= 2`
methodB <- function(M) as.matrix(round(dist(M,upper = T,diag = T)**2))

基准测试结果如下

microbenchmark::microbenchmark(
  methodA(m),
  methodB(m),
  unit = "relative",
  check = "equivalent",
  times = 50
)

Unit: relative
       expr      min       lq   mean   median       uq      max neval
 methodA(m) 33.45844 33.81716 33.963 34.30313 34.92493 14.92111    50
 methodB(m)  1.00000  1.00000  1.000  1.00000  1.00000  1.00000    50

感谢预先评价！

请提供需要翻译的具体内容。

- ThomasIsCoding

---

这可能会引起您的兴趣：https://stackoverflow.com/questions/59942412/find-the-hamming-distance-between-string-sequences#comment106005537_59942412 - chinsoon12

@chinsoon12，谢谢你提供的信息，我会查看它。 - ThomasIsCoding

Answer 1

我发现了这个博客，其中有四篇关于计算海明矩阵的文章。我不想为它声名远扬，但也许你可以看一下。 https://johanndejong.wordpress.com/2015/10/02/faster-hamming-distance-in-r-2/

hamming <- function(X) {
  D <- (1 - X) %*% t(X)
  D + t(D)
}

> microbenchmark::microbenchmark(
+   methodB(m),
+   hamming(m),
+   unit = "relative",
+   times = 50
+ )
Unit: relative
       expr    min       lq     mean   median       uq      max neval
 methodB(m) 1.0000 1.000000 1.000000 1.000000 1.000000 1.000000    50
 hamming(m) 1.2502 1.299844 1.436486 1.301461 1.302033 4.607748    50

注：我没有足够的声望只能将此留言作为评论。

- arohland

Answer 2

methodM <- function(x) {
  xt <- t(x)
  sapply(1:nrow(x), function(y) colSums(xt != xt[, y]))
}
microbenchmark::microbenchmark(
  methodB(m), methodM(m),
  unit = "relative", check = "equivalent", times = 50
)
# Unit: relative
#       expr  min       lq     mean   median       uq      max neval cld
# methodB(m) 1.00 1.000000 1.000000 1.000000 1.000000 1.000000    50  a 
# methodM(m) 1.25 1.224827 1.359573 1.219507 1.292463 4.550159    50   b

- minem

---

谢谢你的回答！是的，你的方法很快，并且可以扩展到k>2的情况。你有没有比我methodB()更快的想法，适用于特殊情况k = 2？ - ThomasIsCoding

@ThomasIsCoding，它可能不会更快，因为它没有使用低级优化函数“dist”。此外，这会计算所有距离，理想情况下，我们希望使用更好的算法，仅计算上（下）三角形部分的值。 - minem

是的，我明白了，也许我们现在使用基本R已经达到了速度极限。 - ThomasIsCoding

Answer 3

你尝试使用过 Rcpp 吗？我之前也遇到了类似的问题！请看这里的答案：https://stackoverflow.com/a/60067825/3237589。

- Sudaraka

---

谢谢，但我想使用基本的R（而不是Rcpp），正如我在帖子中所述。 - ThomasIsCoding