r - (速度挑战)根据通用汉明距离计算距离矩阵的任何更快的方法？

Question

我正在寻找一种更有效的方法来根据 Hamming distance 获取距离矩阵.

背景

我知道 e1071 包中有一个函数 hamming.distance() 可以计算距离矩阵，但我怀疑它在涉及大型矩阵时可能会非常慢有很多行，因为它应用了嵌套的 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

提前感谢!

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

PS:我没有足够的声望，无法将此作为评论。