Пересекающихся много пар целочисленных векторов

Question

У меня есть list из integervector S:

set.seed(1) 
l <- list(g1=as.integer(runif(10,1,100)), 
      g2=as.integer(runif(5,1,100)), 
      g3=as.integer(runif(5,1,100)), 
      g4=as.integer(runif(8,1,100))) 

(в действительности это длинно 1000 в элементах и ​​средняя длина вектора элементов в 100s)

I хотите вычислить intersection по union между всеми парами элементов l и их соответствующими hypergeometric/fisher.testp-value.

Вот что я сейчас делаю:

1. Сначала я сгенерировать матрицу для хранения l индексы всех пар его элементов:

   idx.mat <- t(combn(1:length(l),2)) 
   

Эта часть довольно быстро и могут быть сделаны быстрее, используя combnPrim

2. Тогда я запускаю эту функцию, чтобы получить нужный мне результат:

   res.df <- do.call(rbind, lapply(1:nrow(idx.mat), function(i){ gi.length <- length(l[[idx.mat[i,1]]]) gj.length <- length(l[[idx.mat[i,2]]]) set.diff.1 <- length(setdiff(l[[idx.mat[i,1]]],l[[idx.mat[i,2]]])) set.diff.2 <- length(setdiff(l[[idx.mat[i,2]]],l[[idx.mat[i,1]]])) gi.gj.inter <- length(intersect(l[[idx.mat[i,1]]],l[[idx.mat[i,2]]])) gi.gj.union <- length(unique(c(l[[idx.mat[i,1]]],l[[idx.mat[i,2]]]))) p.value <- fisher.test(matrix(c(gi.length+gj.length- gi.gj.union,set.diff.1,set.diff.2,gi.gj.inter),nrow=2),alternative="greater")$p.value return(data.frame(gi=names(l)[idx.mat[i,1]], gj=names(l)[idx.mat[i,2]], gi.gj.inter=gi.gj.inter, gi.gj.union=gi.gj.union, gi.gj.iou=gi.gj.inter/gi.gj.union, gi.gj.iou.p.val=p.value, stringsAsFactors=F)) }))

Но для моего реального размера данных, это немного медленно.

Любая идея, как добиться этого быстрее?

Answer 1

Попробуйте представляя l как 1/0 матрицы:

max.val = max(sapply(l, max)) 
mat = do.call(rbind, lapply(l, function(x) {z = rep(0, max.val); z[x] = 1; z})) 

Теперь вы можете легко вычислить попарные пересечения и объединения фронт:

pair_intsct = mat %*% t(mat) 

pair_union = outer(rowSums(mat), rowSums(mat), '+') - pair_intsct