r - 快速检查一个向量是否是另一个向量的一部分

Question

我有一个向量列表，比如 vecs = list(vec1=1:3, vec2=1:5, vec3=2:6, vec4=1:7) .我想删除所有列表成员，如果它包含在另一个列表成员中。例如，vecs$vec1是 vecs$vec2 的一部分, (或 vecs$vec4 )，所以我想删除它。

我想要一个非常快的实现，因为 length(vecs)非常大。我所做的是第一次排序 vecs按长度划分的成员 vecs = vecs[ order(unlist(lapply(vecs, length))) ] ，然后对于 check_member = vecs[i] , 检查它是否是 vecs[ i+1 ], vecs[ i+2 ]... 的一部分.有没有更好的策略？完整代码:

vecs = list(vec1=1:3, vec2=1:5, vec3=2:6, vec4=1:7, vec5=2:3)
vecs = vecs[ order(unlist(lapply(vecs, length))) ] ##sort by member length
vecs_len = length(vecs)
toRemove = numeric(vecs_len ) ##record whether to remove this member
for( i in 1:(vecs_len-1 ))
for( j in (i+1):(vecs_len ))
{
   if( length( setdiff(vecs[[i]],vecs[[j]]) )==0  ) {toRemove[i] = 1; break} ##check whether vecs[[i]] is part of vecs[[j]]

}
vecs = vecs[!toRemove]

Answer 1

请在您的大数据上尝试此操作。正如您在评论中所阐明的那样，我从字符向量开始。我还假设向量不包含重复项(如果有的话，很容易通过 lapply(vecs, unique) 修复)

vecs <- list(vec1=letters[1:3],
             vec2=letters[1:5],
             vec3=letters[2:6],
             vec4=letters[1:7])

首先，将您的数据转换为共享相同级别的因子(即整数)列表:

vlevels <- unique(unlist(vecs))
nlev    <- length(vlevels)
fvecs   <- lapply(vecs, factor, levels = vlevels)

然后，我将数据转换为 0 的矩阵和 1对于包含/不包含:

vtabs <- vapply(fvecs, tabulate, integer(nlev), nbins = nlev)
#      vec1 vec2 vec3 vec4
# [1,]    1    1    0    1
# [2,]    1    1    1    1
# [3,]    1    1    1    1
# [4,]    0    1    1    1
# [5,]    0    1    1    1
# [6,]    0    0    1    1
# [7,]    0    0    0    1

接下来，我计算叉积以查看两个向量共有多少个元素，并与每个向量的长度进行比较以确定第一个向量是否是第二个向量的子集。

num.match <- crossprod(vtabs)
vlen <- sapply(vecs, length)
is.subset.mat <- num.match == vlen
diag(is.subset.mat) <- FALSE
#       vec1  vec2  vec3  vec4
# vec1 FALSE  TRUE FALSE  TRUE
# vec2 FALSE FALSE FALSE  TRUE
# vec3 FALSE FALSE FALSE  TRUE
# vec4 FALSE FALSE FALSE FALSE

最后，我按行求和以判断每个向量是否是其他向量的子集:

is.subset <- rowSums(is.subset.mat) > 0L
# vec1  vec2  vec3  vec4 
# TRUE  TRUE  TRUE FALSE 

你只剩下过滤:

out <- vecs[!is.subset]

如果您的初始列表太大以至于太慢，那么我建议您逐块运行它，然后再次运行结果。