0

我正在努力提高我正在编写的函数的速度（用于差异度量），它在数学上与欧几里得距离函数非常相似。但是，当我将我的函数与包中实现的函数进行比较时daisy，cluster我发现速度上有很大差异，daisy性能要好得多。鉴于（我假设）O(n x p)由于需要在所有变量上将每个对象与自身进行比较（其中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))
4

1 回答 1

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也可以提高速度。我相信在stackoverflow上可能有更高效的方法，你只需要通过正确的关键字搜索......

于 2021-07-02T08:29:07.487 回答