Daisy 函数的速度

Question

我正在努力提高我正在编写的函数的速度（用于相异性度量），它在数学上与欧几里德距离函数非常相似。但是，当我将我的函数与 cluster 包中的 daisy 函数中实现的函数进行计时时，我发现速度有很大差异，daisy 的性能要好得多。鉴于（我假设）由于需要在所有变量上将每个对象与其自身进行比较（其中 n 是对象数量，p 是变量的数量），我发现很难理解相对于我简单直接的实现，daisy 函数如何表现得如此之好（接近恒定时间，从我做过的几个实验来看）。我在下面展示了我用于实施和测试的代码。我曾尝试查看 r 实现 daisy 功能的源代码，但我发现它很难理解。我发现没有嵌套的 for 循环。非常感谢任何帮助理解为什么这个函数执行得如此之快以及我如何修改我的代码以具有类似速度的帮助。

euclidean <- function (df){
  
  no_obj <- nrow(df)
  
  dist <- array(0, dim = c(no_obj, no_obj))
  
  for (i in 1:no_obj){
    for (j in 1:no_obj){
      dist_v <- 0
      if(i != j){
        for (v in 1:ncol(df)){
          dist_v <- dist_v + sqrt((df[i,v] - df[j,v])^2)
        }
      }
      dist[i,j] <- dist_v
    }
  }
  return(dist)
}

data("iris")

tic <- Sys.time()
dst <- euclidean(iris[,1:4])
time <- difftime(Sys.time(), tic, units = "secs")[[1]]
print(paste("Time taken [Euclidean]: ", time))

tic <- Sys.time()
dst <- daisy(iris[,1:4])
time <- difftime(Sys.time(), tic, units = "secs")[[1]]
print(paste("Time taken [Daisy]: ", time))

Answer 1

一个选项：

 euclidean3 <- function(df) {
  require(data.table)
  n <- nrow(df)
  i <- CJ(1:n, 1:n) # generate all row combinations
  dl <- sapply(df, function(x) sqrt((x[i[[1]]] - x[i[[2]]])^2)) # loop over columns
  dv <- rowSums(dl) # sum values of columns
  d <- matrix(dv, n, n) # fill in matrix
  d
}
dst3 <- euclidean3(iris[,1:4])
all.equal(euclidean(iris[,1:4]), dst3) # TRUE

[1] "Time taken [Euclidean3]:  0.008"
[1] "Time taken [Daisy]:  0.002"

代码中的最大瓶颈是在循环中选择 data.frame 个元素 (df[j,v]))。也许将其更改为 matrix 也可以提高速度。我相信在 Whosebug 上可能会有更高效的方法，你只需要通过正确的关键字搜索...

Daisy 函数的速度

Speed of Daisy Function

performance

r

similarity

r-daisy