# 假定:
1. 有元素b1,b2.。。。bn,n达到10万+级别。
1. 有海量集合B,每个集合由上述元素构成,可能一个集合只有2~4个元素
问:
给定一个较大的集合A(可能包含10~100个上述元素),如何用最快速的方法找到B中有哪些集合属于A?
谢谢!
遍历大集合所有的数据,然后依次从所有小集合里面删除这个元素
遍历完成后,所有为空的小集合就是A的子集
假设总的元素数量不多,比如是128/256以内,可以先对每个元素编号,对应一个二进制位,然后将每个集合用几个64位二进制整数来表示,最后用A & B[i] == B[i]来判断是否是子集。
这样做,主要的计算消耗可能是前面的编码过程,需要逐个比对,确定集合中的元素对应的二进制位置。这里可以根据元素特征,寻找优化的办法,比如用哈希表,比如先用最开始的几个字节,转换成整数,做索引。