算法问题:给定一个大集合A,和海量的小集合B,如何最快速找到B中有哪些集合属于A的子集?

# 假定:
1. 有元素b1,b2.。。。bn,n达到10万+级别。
1. 有海量集合B,每个集合由上述元素构成,可能一个集合只有2~4个元素

问:
给定一个较大的集合A(可能包含10~100个上述元素),如何用最快速的方法找到B中有哪些集合属于A?
谢谢!

2个回答

遍历大集合所有的数据,然后依次从所有小集合里面删除这个元素
遍历完成后,所有为空的小集合就是A的子集

caozhy
贵阳老马马善福专业维修游泳池堵漏防水工程 回复V_Dream: hash没有什么意义。你再怎么至少也要遍历一次大集合
3 个月之前 回复
cowboy421
V_Dream 回复贵阳老马马善福专业维修游泳池堵漏防水工程: 额,我的意思是小集合的个数是大量的,能否对这些小集合做文章,您是想着小集合里面的元素个数很小,LogN和N没差别
3 个月之前 回复
caozhy
贵阳老马马善福专业维修游泳池堵漏防水工程 回复V_Dream: 没有,因为你小集合,所以LogN和N没有什么差异,而大集合只遍历1次,已经最简
3 个月之前 回复
cowboy421
V_Dream 这种挨个遍历的时间复杂度还是比较高的,能否通过对B的集合进行一些诸如hash或者树结构的组织后再进行查找
3 个月之前 回复

假设总的元素数量不多,比如是128/256以内,可以先对每个元素编号,对应一个二进制位,然后将每个集合用几个64位二进制整数来表示,最后用A & B[i] == B[i]来判断是否是子集。

这样做,主要的计算消耗可能是前面的编码过程,需要逐个比对,确定集合中的元素对应的二进制位置。这里可以根据元素特征,寻找优化的办法,比如用哈希表,比如先用最开始的几个字节,转换成整数,做索引。

bobhuang
bobhuang 回复V_Dream: 这样的话,换个思路:类似哈希表,用某种变换,比如CRC,将A中的元素变换,存入哈希表。B的时候,先做同样变换,对应表项是否存在,可以快速判断B中的元素是否可能在A里(不精确匹配,但是如果不在哈希表,则肯定不是子集)。在所有元素都在哈希表中的基础上,再做精确比对。如果变换的代价比直接比对小很多,带来的收益还是可以的。
3 个月之前 回复
cowboy421
V_Dream 谢谢!我也是考虑过这种,但是现在元素数量有10万级别,无法用一个64bit的整型来描述一个集合
3 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问