r - 使用 data.table 优化具有唯一节点的节点匹配目标

Question

我有 2 组节点，由 id1 和 id2 表示。 我有一个 data.table 包含对节点对的惩罚——键(id1，id2)，值是惩罚。

我如何有效地将 data.table 范围内的节点对以最小的惩罚使每个节点(id1 和 id2)出现一次？

简单示例:

输入数据表:

dtIn <- data.table(
    id1 = rep(letters[1:3], each=3)
  , id2 = rep(1:3, 3)
  , penalty = 1:9
)
setkey(dtIn, id1, id2)

print(dtIn)
   id1 id2 penalty
1:   a   1       1
2:   a   2       2
3:   a   3       3
4:   b   1       4
5:   b   2       5
6:   b   3       6
7:   c   1       7
8:   c   2       8
9:   c   3       9

期望的输出数据表:

   id1 id2 penalty
1:   a   1       1
2:   b   2       5
3:   c   3       9

我知道如何实现编写循环的算法:按罚分排序，循环遍历记录，如果先前没有匹配的节点，则按顺序挑选每一对。请参阅下面的代码。

当然，对于我的真实大小的数据，这样的循环运行起来慢得令人无法忍受。

逻辑上正确但性能太差的手动循环函数:

manualIter <- function(dtIn) {
  setkey(dtIn, penalty, id1, id2) # Enusred ordered by penalty.
  id1Match <- NULL; id2Match <- NULL; pen <- NULL;
  for (i in seq_len(nrow(dtIn))) {
    if (!(dtIn$id1[i] %in% id1Match) && !(dtIn$id2[i] %in% id2Match)) {
      id1Match <- c(id1Match, dtIn$id1[i])
      id2Match <- c(id2Match, dtIn$id2[i])
      pen <- c(pen, dtIn$penalty[i])
    }
  }
  # Build the return data.table for the matching ids.
  dtf <- data.table(id1 = id1Match, id2 = id2Match, penalty = pen)
  setkey(dtf, id1, id2)
  return(dtf)
}

那么问题是如何有效地向量化这个算法？

Answer 1

更新了答案。我不确定您是否可以对此进行矢量化。我认为这本质上是一个递归问题。我的回答很简单(给定数据按惩罚排序):

dtOut <- list()
dtOut[[1]] <- dtIn[1]
i <- 2
while(dtIn[, .N] > 0) {
  dtIn <- dtIn[!(id1 == dtOut[[i - 1]][, id1] | id2 == dtOut[[i - 1]][, id2])]
  if(dtIn[, .N] < 1) break
  dtOut[[i]] <- dtIn[1]
  i <- i + 1
}
dtOut <- rbindlist(dtOut)