优化瓶颈距离矩阵的并行计算效率方法探讨

首先明确：TDA中的瓶颈距离是对称的，即bottleneck(a,b,DIM)和bottleneck(b,a,DIM)结果完全一致，且同一持久化图自身的瓶颈距离为0。利用这个特性，我们可以直接只计算矩阵的一半元素（如上三角区域），再填充对称部分，彻底避免重复计算——这种方案比记忆化更高效（并行环境下记忆化还会有缓存同步的额外开销）。

优化后的并行实现代码 #

library(foreach)
library(doParallel)

CreateBottleneckDistanceMatrixParallel <- function(PD, DIM = 0:2) {
  n <- length(PD)
  cat("Creating Output Matrix of Size", n, "x", n, "\n")
  
  # 生成仅需计算的索引对：仅i < j的组合（对角线i=j直接设为0，无需计算）
  idx_pairs <- expand.grid(i = 1:n, j = 1:n)
  idx_pairs <- idx_pairs[idx_pairs$i < idx_pairs$j, ]
  
  # 并行计算目标索引对的瓶颈距离
  results <- foreach(k = 1:nrow(idx_pairs), .combine = rbind) %dopar% {
    i <- idx_pairs$i[k]
    j <- idx_pairs$j[k]
    dist_val <- TDA::bottleneck(PD[[i]], PD[[j]], DIM)
    data.frame(i = i, j = j, dist = dist_val)
  }
  
  # 初始化距离矩阵，对角线默认设为0
  dist_matrix <- matrix(0, nrow = n, ncol = n)
  
  # 填充计算结果到对称位置
  for (k in 1:nrow(results)) {
    i <- results$i[k]
    j <- results$j[k]
    dist_matrix[i, j] <- results$dist[k]
    dist_matrix[j, i] <- results$dist[k]
  }
  
  dist_matrix
}

关键优化点说明 #

• 直接减半计算量：从原方案的n²次计算降到n(n-1)/2次，彻底消除重复计算的资源浪费。
• 并行效率保留：通过单循环并行处理目标索引对，避免嵌套foreach的冗余逻辑，同时充分利用多核心资源。
• 对称填充逻辑：利用瓶颈距离的对称性，将单次计算结果同步填充到矩阵的(i,j)和(j,i)位置，保证矩阵的对称性要求。

关于记忆化方案的补充 #

如果后续有跨场景重复计算的需求，也可以用memoise实现记忆化，但并行环境下需注意缓存共享问题，且效率不如上述对称优化方案（仍会触发n²次函数调用，仅重复调用会读取缓存）。示例代码如下：

library(memoise)
library(cachem)

# 创建内存缓存（集群并行场景需改用分布式缓存如Redis）
cache <- cachem::cache_mem(max_size = 1e9)

# 对bottleneck函数做记忆化包装
memo_bottleneck <- memoise(TDA::bottleneck, cache = cache)

# 基于记忆化的矩阵生成函数
CreateBottleneckDistanceMatrixMemo <- function(PD, DIM = 0:2) {
  n <- length(PD)
  cat("Creating Output Matrix of Size", n, "x", n, "\n")
  x <- foreach(b = PD, .combine = 'cbind') %:%
    foreach(a = PD, .combine = 'c') %dopar% {
      memo_bottleneck(a, b, DIM)
    }
  x
}

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