r - R中的快速并行二分距离计算
问题描述
使用并行化 Rcpp 后端的 R 中二分距离的最快计算是什么?
parallelDist
是一个很棒的包,带有 cpp 后端并支持多线程,但不支持二分距离计算(据我所知)。
用于parallelDist()
二分距离矩阵计算。 这涉及计算 m1:m1 和 m2:m2 以及 m1:m2 - 非常低效。
library(parallelDist)
bipartiteDist <- function(matrix1,matrix2){
matrix12 <- rbind(matrix1,matrix2)
d <- parallelDist(matrix12)
d <- as.matrix(d)[(1:nrow(matrix1)),((nrow(matrix1)+1):(nrow(matrix1)*2))]
d
}
matrix1 <- abs(matrix(rnorm(1000),10,100000))
matrix2 <- abs(matrix(rnorm(1000),10,100000))
dist <- bipartiteDist(matrix1, matrix2)
当超过 3 个内核可用时,这种方法比 pDist 或纯 R 实现更快。
pdist
非常适合计算二分距离,但不支持多线程。
并行二分距离计算的任何快速实现?
解决方案
该wordspace dist.matrix()
函数支持二分距离的并行计算。
wordspace
对标parallelDist
matrix1 <- abs(matrix(rnorm(1000),100,100000))
matrix2 <- abs(matrix(rnorm(1000),100,100000))
library(rbenchmark)
library(parallelDist)
library(wordspace)
bipartiteDist_parallelDist <- function(matrix1,matrix2){
matrix12 <- rbind(matrix1,matrix2)
d <- parallelDist(matrix12, method = "euclidean")
d <- as.matrix(d)[(1:nrow(matrix1)),((nrow(matrix1)+1):(nrow(matrix1)*2))]
d
}
bipartiteDist_wordspace <- function(matrix1,matrix2){
wordspace.openmp(threads = wordspace.openmp()$max)
dist.matrix(matrix1,matrix2, byrow = TRUE, method = "euclidean", convert = FALSE)
}
benchmark("parallelDist" = {
bd1 <- bipartiteDist_parallelDist(matrix1,matrix2)
},
"wordspace" = {
bd2 <- bipartiteDist_wordspace(matrix1,matrix2)
},
replications = 1,
columns = c("test", "replications", "elapsed",
"relative", "user.self", "sys.self"))
plot(bd1,bd2) # yes, both methods give near-identical results
基准测试结果:
test replications elapsed relative user.self sys.self
1 parallelDist 1 2.120 12.184 126.145 0.523
2 wordspace 1 0.174 1.000 3.749 0.252
我使用了 80 个线程。
进一步提高速度的框架
作者wordspace
承认强调低内存负载超过速度,因此额外的速度增益是可能的(来源)。
例如,这是欧几里得距离的一般框架:
bipartiteDist3 <- function(matrix1,matrix2){
m1tm2 <- tcrossprod(matrix1,matrix2)
sq1 <- rowSums(matrix1^2)
sq2 <- rowSums(matrix2^2)
out0 <- outer(sq1, sq2, "+") - 2 * m1tm2
sqrt(out0)
}
我对针对稀疏矩阵优化的并行解决方案非常感兴趣。据我所知,wordspace
不会针对稀疏性进行优化。例如,有 tcrossprod、rowSums 和外部函数等价物的可并行稀疏矩阵实现。
推荐阅读
- excel-formula - 在 Excel 中使用 y,m,d 从年龄计算出生日期
- javascript - 向 html 添加选项
- jenkins - Jenkins“Pipeline Stage View”插件不屏蔽密码
- python - .get() 仅当 value 不是 None
- apache - TLS 1.3 和 SSLVerifyClient 不起作用,但它适用于 TLS 1.2
- c# - 如何在路径字符串中放置空格?
- recursion - 如何使用递归就地反转 Rust 字符串?
- python - 在 Windows 平台上安装 OpenEXR 时出错
- google-sheets - 谷歌表格 - 如果 A 列文本包含 B 列和 C 列中的关键字,则计数
- android - 如何使用数据库检查器获取查询执行时间?