对巨大数据集进行重复连接

Question

需要将几个各有 2 列的矩阵组合起来，如下所示

matrix1
1,3
1,5
3,6

matrix2
1,4
1,5
3,6
3,7

output
1,3,1
1,4,1
1,5,2
3,6,2
3,7,1

输出中的第三列是在所有矩阵中出现一对的次数。我编写了一些代码来执行此操作

require(data.table)

set.seed(1000)
data.lst <- lapply(1:200, function(n) { x <- matrix(sample(1:1000,2000,replace=T), ncol=2); x[!duplicated(x),] })

#method 1
pair1.dt <- data.table(i=integer(0), j=integer(0), cnt=integer(0))
for(mat in data.lst) {
    pair1.dt <- rbind(pair1.dt, data.table(i=mat[,1],j=mat[,2],cnt=1))[, .(cnt=sum(cnt)), .(i,j)]
}

#method 2
pair2.dt <- data.table(i=integer(0), j=integer(0), cnt=integer(0))
for(mat in data.lst) {
    pair2.dt <- merge(pair2.dt, data.table(i=mat[,1],j=mat[,2],cnt=1), by=c("i","j"), all=T)[, 
        cnt:=rowSums(.SD,na.rm=T), .SDcols=c("cnt.x","cnt.y")][, c("cnt.x","cnt.y"):=NULL]
}

cat(sprintf("num.rows  =>  pair1: %d,  pair2: %d", pair1.dt[,.N], pair2.dt[,.N]), "\n")

在实际问题中，每个矩阵都有数十百万行，并且可能有 30-40% 的重叠。我正在尝试找出最快的方法来做到这一点。我尝试使用 Matrix::sparseMatrix。虽然这要快得多，但我遇到了错误“尚不支持长向量”。我这里有几种不同的基于 data.table 的方法。我正在寻找加快此代码速度的建议和/或建议替代方法。

Answer 1

首先，制作它们的data.tables:

dt.lst = lapply(data.lst, as.data.table)

堆叠。为了进行比较，以下是涉及堆叠的快速方法:

res0 = rbindlist(dt.lst)[, .(n = .N), by=V1:V2]

OP 表示这是不可行的，因为 rbindlist 生成的中间结果太大。

首先枚举。对于小范围的值，我建议先枚举它们:

res1 = CJ(V1 = 1:1000, V2 = 1:1000)[, n := 0L]
for (k in seq_along(dt.lst)) res1[ dt.lst[[k]], n := n + .N, by=.EACHI ] 

fsetequal(res0, res1[n>0]) # TRUE

OP 表明有 1e12 个可能的值，所以这似乎不是一个好主意。相反，我们可以使用

res2 = dt.lst[[1L]][0L]
for (k in seq_along(dt.lst)) res2 = funion(res2, dt.lst[[k]])
res2[, n := 0L]
setkey(res2, V1, V2)
for (k in seq_along(dt.lst)) res2[ dt.lst[[k]], n := n + .N, by=.EACHI ]     

fsetequal(res0, res2) # TRUE

这是给定示例的三个选项中最慢的一个，但鉴于OP的担忧，对我来说似乎是最好的。

在循环中成长。最后...

res3 = dt.lst[[1L]][0L][, n := NA_integer_][]
for (k in seq_along(dt.lst)){
  setkey(res3, V1, V2)
  res3[dt.lst[[k]], n := n + .N, by=.EACHI ]
  res3 = rbind(
    res3, 
    fsetdiff(dt.lst[[k]], res3[, !"n", with=FALSE], all=TRUE)[, .(n = .N), by=V1:V2]
  )
} 

fsetequal(res0, res3) # TRUE

在 R 中，强烈建议不要在循环内增长对象，而且效率低下，但这允许您在单个循环而不是两个循环中完成此操作。

其他选项和注释。我怀疑您最好使用哈希。这些可以在 hash 包中找到，也可以通过 Rcpp 包找到。

fsetequal、fsetdiff 和 funion 是该软件包的开发版本中最近添加的内容。在 data.table 项目的官方网站上查找详细信息。

顺便说一句，如果每个矩阵中的条目不同，您可以将上面的 .N 替换为 1L 并删除 by=.EACHI 和 all=TRUE。