从大列表 (R) 中查找对之间交集的时间和内存有效方法

Question

我有一个长度为 N 的列表，每个列表元素是从某个更大的组中采样的 10 个字符串。我想找到每对非常相似的元素，比如共同 >=8 个字符串。 我可以使用 crossprod 对 N<10,000 执行此操作，但我运行内存不足，无法使用更大的 N。

这是一个示例，其中 N=1000，产生 6 个非常相似的对：

# make list x
set.seed(1)
N = 1000
x = lapply(1:N, function(x) sample(letters, 10))
names(x) = as.character(1:length(x))

# find pairwise intersect, store in square matrix N_intersect
N_intersect = x %>% stack() %>% table() %>% crossprod()
diag(N_intersect) = 0
N_intersect[lower.tri(N_intersect)] = 0

# find when N_intersect is over some threshold
result = which(N_intersect > 8, arr.ind = T)

result
    ind ind
111 111 375
705 705 708
48   48 771
317 317 797
566 566 883
705 705 958

但是由于crossprod的输出是一个NxN矩阵，对于大N它很快就会耗尽内存。我知道crossprod有稀疏方法，但这似乎只减少了大约内存~ 30%.

事实是，高度相似的元素的数量通常非常少，比如 1/1000 对。所以 我不需要存储来自 crossprod 的大方阵，但我想不出可以快速完成此操作的内存高效方法。 我可以检查每一对for 循环中的元素，但这需要几个小时。

Answer 1

回答我自己的问题以防对任何人有帮助。

我发现了一种检测列表 x 中相似对的方法，它的运行时间与 crossprod 大致相同，但最重要的是它不会耗尽内存。我通过将输入输入到 crossprod x %>% stack() %>% table() 来做到这一点，这是一个 Nxm 矩阵，其中 m 是可能的字符数。上例中的 m=26，因为我使用的是字母。每行代表 x 中的一个列表元素，其中 1 表示元素中的字母，0 表示元素中不包含的字母。

然后我的问题是“哪些行对至少有 9 个共享列为 1？”我通过 1) 子集列和 2) rowSums 为每一行回答了这个问题。这个方法是 f.new 我把它和老方法比较 f.crossprod:

f.crossprod = function(x, threshold) {
  # find intersection of each pair elements with crossprod
  # store in upper triangular square matrix
  N_intersect = x %>% stack() %>% table() %>% crossprod()
  diag(N_intersect) = 0
  N_intersect[lower.tri(N_intersect)] = 0
  
  # find when N_intersect is over some threshold
  result = which(N_intersect >= threshold, arr.ind = T) %>%
    as.data.frame() %>%
    `colnames<-`(c("row", "col"))
  rownames(result) = NULL
  return(result)
}

f.new = function(x, threshold) {
  x2 = t(table(stack(x)))
  result = list()
  for (ii in 3:nrow(x2)) {
    ia = which(x2[ii,]>0)
    cands = which(rowSums(x2[1:(ii-1),ia]) >= threshold)
    result[[ii]] = data.frame(row=cands, col=rep(ii, length(cands)))
  }
  result = do.call(rbind, result) %>% filter(!row==col)
  rownames(result) = NULL
  return(result)
}

我可以看到它们 return 相同的结果：

set.seed(1)
N = 1000
x = lapply(1:N, function(x) sample(letters, 10))
names(x) = as.character(1:length(x))

r1 = f.new(x, 9)
r2 = f.crossprod(x, 9)
identical(r1, r2)

> TRUE

时间是相似的，尽管 f.new 对于 N>5000 来说稍微快一些。最重要的是 f.new 没有问题 N>20000:

从大列表 (R) 中查找对之间交集的时间和内存有效方法

Time and memory efficient way to find intersection between pairs from a large list (R)

r

matrix

memory

memory-management