logo标签列表

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

rvector
4
我有一个向量列表，例如 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]
你能展示一下你使用的实际代码吗？ - talat
@beginneR 我已经添加了它。 - yliueagle
你的向量是否总是包含整数？如果是，那么并集的范围是多少（这里是1到7）？请提供有关列表大小和向量长度的详细信息。 - flodel
@flodel 不只是整数。这里只是一个例子。实际上是字符串向量。unique( unlist(vecs) ) > 1e4; 但如果您有关于整数的好主意，那么字符串可以用整数命名并且它也能工作。 - yliueagle
3个回答
4
请尝试在您的大型数据集上执行此操作。根据您在评论中的澄清，我从字符向量开始。我还假设向量不包含重复项（如果有，可以通过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]

如果您的初始列表非常大，导致速度过慢，那么我建议您分块运行，然后再对结果进行操作。

1
在进行一些基准测试后，我们可以看到您只需稍微修改原始代码即可获得良好的加速。使用%in%和any比使用setdiff和length更有效率。
# Your code
fun1 <- function(vecs){
  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 ##check whether vecs[[i]] is part of vecs[[j]]

    }
  vecs = vecs[!toRemove]
  return(vecs)
}

# flodel's code
fun2 <- function(vecs){
  vlevels <- unique(unlist(vecs))
  nlev    <- length(vlevels)
  fvecs   <- lapply(vecs, factor, levels = vlevels)
  vtabs <- vapply(fvecs, tabulate, integer(nlev), nbins = nlev)
  num.match <- crossprod(vtabs)
  vlen <- sapply(vecs, length)
  is.subset.mat <- num.match == vlen
  diag(is.subset.mat) <- FALSE
  is.subset <- rowSums(is.subset.mat) > 0L
  out <- vecs[!is.subset]
  return(out)  
}

# slight modification
fun3 <- function(vecs){
  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( any(vecs[[i]] %in% vecs[[j]])  ) toRemove[i] = 1 ##check whether vecs[[i]] is part of vecs[[j]]

    }
  vecs = vecs[!toRemove]
  return(vecs)
}

microbenchmark(fun1(vecs), fun2(vecs), fun3(vecs), times=100L)
Unit: microseconds
       expr     min       lq      mean   median       uq     max neval
 fun1(vecs) 154.919 166.4245 179.62297 172.5880 180.3950 356.681   100
 fun2(vecs) 220.255 231.5555 279.99874 237.7185 290.9335 609.398   100
 fun3(vecs)  50.544  54.0370  64.86082  57.3250  64.5155 291.345   100
测试大数据是有意义的。我已经尝试过使用 alphabet <- do.call(paste0, expand.grid(letters, letters)); vecs <- replicate(1000, sample(alphabet, sample(1:300, 1), FALSE), simplify = FALSE) 进行测试，分别需要28.86、0.61和12.37的时间。 - flodel
我认为你应该使用 all 而不是 any。此外，你的代码和 OP 的代码只测试了 "vecs[i] 是否是 vec[j] 的子集"；它还应该测试 "vecs[j] 是否是 vec[i] 的子集"。 - flodel
@flodel，你是正确的，我忽略了一个点。一旦数据变得更大，你的函数确实执行得更快。 - cdeterman
0

我认为以下类似的代码应该可以工作。它将给你一个列表，其中包含那些是其他向量子集的向量。它将是自身的子集 - 所以我只对那些是至少两个向量的子集（即自身和另一个）进行操作。感谢https://stat.ethz.ch/pipermail/r-help/2005-March/068491.html提供的%in%函数。

dfSubsets <- list()

ds <- lapply(vecs,function(x){
        subsets = 0
        lapply( vecs, function(y){
            if(all(x %in% y)){subsets <<- subsets + 1}
        })
        if(subsets > 1){
            dfSubsets <<- c(dfSubsets,list(x))
        }
}
)

dfSubsets

如果您想要一个那些向量是子集的索引列表，请告诉我。
我相信dplyr也可能有所帮助，但我不熟悉它。
通常应用会提高效率 - 当然，如果您只关心它是否是一个向量的子集，有时使用for循环和break会更快，但您无法预先知道。
此方法适用于字符串或整数。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接