线性总和分配/R中的匈牙利方法性能

Question

我需要加快为每个条目找到最佳距离的过程。我正在使用 gower.dist 来自 statmatch 和 solve_lsap 来自 clue> clue> clue package> solve> solve_lsap 。 Gower距离根本不需要时间，但是，LSAP求解器需要太长时间，而我需要运行它的次数。

有没有一种方法可以使用并行计算更快地进行此运行，或者只是使其一部分并行运行 [链接到线索github] adagio 和 rcpphungarian （两个都较慢）。

示例数据：

> dim(gowerdist)
[1]  4309 10366

solve_LSAP(gowerdist, maximum = FALSE)

Answer 1

线索:: SOLVE_LSAP 使用匈牙利算法。 Jonker and Volgenant（1987）算法，在 ，更有效。

我测试了矩阵的简化版本，以在几秒钟而不是分钟内获得结果。运行时间的差异可能会随着较大的矩阵而增加。

gower <- read.csv("GowerDistance.csv")
dim(gower)
gowerMat <- as.matrix(gower)
gow1 <- gowerMat[1:2400, 1:4800]

tictoc::tic()
clue <- clue::solve_LSAP(gow1, maximum = FALSE)
tictoc::toc()
# 67.95 sec elapsed

tictoc::tic()
td <- TreeDist::LAPJV(gow1)
tictoc::toc()
# 20.24 sec elapsed

graphAlignment :: linearassignment（） 还使用LAPJV算法，但只能应用于方形矩阵。 （解决方法是在具有极高值的矩阵中添加额外的行。）

另一种选择是 /a>;这没有指定使用哪种算法，但要慢得多

tictoc::tic()
lps <- lpSolve::lp.assign(gowerMat[1:800, 1:1600]) # much smaller matrix
tictoc::toc()
# 364.67 sec elapsed

Answer 2

如果您可以将问题转换为在整数上运行而不是双打，则应该更快。不确定在所有用例中都有多大的实用性，但这可能是一种选择。仍然不是快速燃烧，但绝对是一个改进。

gowerdist_all <- readr::read_csv("GowerDistance.csv")

gowerdist1 <- as.matrix(gowerdist_all[,-1])

gowerdist2 <- as.matrix(gowerdist_all[,-1]) * 10000
mode(gowerdist2) <- "integer"

这需要548秒。

tictoc::tic()
z <- clue::solve_LSAP(gowerdist1, maximum = FALSE)
tictoc::toc()
# 547.92 sec elapsed

圆形作为整数需要116秒。

tictoc::tic()
z <- clue::solve_LSAP(gowerdist2, maximum = FALSE)
tictoc::toc()
# 115.64 sec elapsed