如何使用快速傅里叶变换来加速在数据帧上应用嵌套循环？

Question

我有两个数据帧和一个相应的嵌套循环。我想要计算的内容在伪代码中看起来像这样：

foreach row1 in df1:
   SUM_row2_in_df2( my_function(row1, row2))

哪里

my_function(row1, row2) = PROD_over_col(exp(log(0.5) * (row2_col-row1_col)^2 )) 

这会产生 n 个值（数据帧 1 中的每一行一个值）。由于双循环，它的运行时间为 O(n^2)。有人告诉我可以使用快速傅里叶变换将运行时间减少到 O(n log n)。但是，我不确定如何做到这一点，因为我发现的示例不包含（不同的）数据帧。

这是我正在做的一些示例代码：

df1 <- data.frame(a=c(1,1,1,1,1,1,1,1), b=c(1,2,3,1,2,3,1,2), c=c(0,0,1,0,0,1,0,0))
df2 <- data.frame(a=c(1,2,1,2,1,2,1,2), b=c(1,2,3,1,2,3,1,2), c=c(0,0,1,0,0,1,0,0))

n <- nrow(df1)
p <- ncol(df1)

rbf.normal <- function(point, x) {
  exp(log(0.5) * (x-point)^2 )  
}

result <-c()

for (i in 1:n){
  row1 <- df1[i,]
  # sum over all results for df2
  result_i <- 0
  for (j in 1:n){
    row2 <- df2[j,]
    # calculate the kernel function for each column and multiply the results
    result_j <- 1
    for (d in 1:p){
      result_kernel <- rbf.normal(row1[[d]], row2[[d]])
      result_j <- result_j*result_kernel
    }
    result_i <- result_i + result_j
  }
  result <- c(result, result_i)
}

result

Answer 1

我不确定 FFT，但使用距离矩阵可以使计算速度更快：

library(Rfast)

(result2 <- rowsums(exp(log(0.5)*dista(as.matrix(df1), as.matrix(df2))^2)))
#> [1] 3.546875 3.625000 2.078125 3.546875 3.625000 2.078125 3.546875 3.625000
all.equal(result, result2)
#> [1] TRUE