如何高效寻找矩阵A每行在矩阵B中的最邻近行？

假设我有如下两个矩阵A（对应代码中的m1）和B（对应代码中的m2）：

set.seed(123)
m1 = matrix(runif(10*5), nrow = 10, ncol = 5)
m2 = matrix(runif(10*5), nrow = 10, ncol = 5)

我需要为矩阵A的每一行，找到矩阵B中与之最接近的行。目前我可通过双重循环实现该功能，代码如下：

for(i in 1:nrow(m1)){
  dist = 9999
  index = -1
  for(j in 1:nrow(m2)){
    test = sqrt(sum(abs(m1[i,]-m2[j,])))
    
    if (test < dist) {
      dist = test
      index = j
    }
  }
  print(index)
}

但当矩阵行数达到百万级时，该方法耗时极长，求更高效的实现方案。

R中的双重循环天生效率低下，尤其是处理百万级数据时，以下几种方法可大幅提升性能：

方法1：矢量化矩阵运算优化 #

你使用的是曼哈顿距离的平方根（sqrt(sum(abs(x-y)))），可以通过矩阵运算批量计算所有行对的距离，再提取最小值对应的索引。这种方法避免了循环，利用R的底层矢量化运算加速：

# 计算所有m1行与m2行的曼哈顿距离（无需平方根，比较大小不影响结果）
manhattan_dist <- t(apply(m1, 1, function(x) colSums(abs(t(m2) - x))))
# 提取每行距离最小的m2行索引
closest_indices <- apply(manhattan_dist, 1, which.min)

注：若必须保留平方根，在colSums外层添加sqrt()即可，但去掉平方根能进一步节省计算时间。

方法2：专用近邻搜索包（超大数据量首选） #

当行数达到百万级，矢量化矩阵运算可能因内存占用过高无法运行，此时可使用基于KD-Tree/Ball-Tree的近邻搜索包，这类包由C++实现，内存效率与计算速度远优于原生循环：

使用RANN包 #

# 安装包（首次使用）
# install.packages("RANN")
library(RANN)

# 搜索每个m1行在m2中的最近1个邻居
nn_result <- nn2(data = m2, query = m1, k = 1)
# 获取最近邻索引
closest_indices <- nn_result$nn.idx[,1]

使用distances包 #

# 安装包（首次使用）
# install.packages("distances")
library(distances)

# 计算曼哈顿距离并提取最近邻索引
dist_obj <- distances(m1, m2, distance = "manhattan")
closest_indices <- which.min(dist_obj, dimension = "rows")

方法3：分块处理（内存不足时） #

若矩阵过大导致内存耗尽，可将m1分块处理，每次计算一部分行的结果后合并：

block_size <- 10000  # 每次处理1万行，可根据内存调整
total_rows <- nrow(m1)
closest_indices <- integer(total_rows)

for (i in seq(1, total_rows, block_size)) {
  end <- min(i + block_size - 1, total_rows)
  block_m1 <- m1[i:end, ]
  # 用RANN处理分块数据
  nn_result <- nn2(data = m2, query = block_m1, k = 1)
  closest_indices[i:end] <- nn_result$nn.idx[,1]
}

内容的提问来源于stack exchange，提问作者MGP