我有一个应用程序,我有许多集.一组可能是
{4,7,12,18}个
唯一数字,并且都小于50.
然后我有几个数据项:
1 {1,2,4,7,8,12,18,23,29}
2 {3,4,6,7,15,23,34,38}
3 {4,7 ,12,18}
4 {1,4,7,12,13,14,15,16,17,18}
5 {2,4,6,7,13,15}
数据项1,3和4与集合匹配,因为它们包含集合中的所有项目.
我需要设计一个超快速的数据结构来识别数据项是否是集合的成员包括属于集合的所有成员(因此数据项是集合的超集).我目前最好的估计表明将会少于50,000套.
我当前的实现将我的集合和数据作为无符号64位整数和存储在列表中的集合.然后检查一个数据项我遍历列表进行((set&data)== set)比较.它的工作原理和节省空间但速度很慢(O(n))而且我很乐意用一些内存来换取一些性能.有没有人对如何组织这个有更好的想法？
编辑:
非常感谢所有的答案.看起来我需要提供有关该问题的更多信息.我首先得到集合,然后逐个获取数据项.我需要检查数据项是否与其中一个集匹配.
这些集很可能是"块状的",例如对于给定的问题,1,3和9可能包含在95%的集合中; 我可以提前预测到这一点(但不是很好).
对于那些建议记忆的人:这就是memoized函数的数据结构.这些集代表已经计算过的一般解决方案,数据项是函数的新输入.通过将数据项与一般解决方案相匹配,我可以避免大量处理.
假设我们在某处存储了数万亿个集合.每个集合的域都是相同的.它也是有限的和离散的.因此,每个集合可以存储为相对较短长度的比特字段(例如:0000100111 ...)(例如:1024).也就是说,位域中的位X指示项目X(1024个可能的项目)是否包括在给定集合中.
现在,我想设计一个存储结构和算法来有效地回答查询:数据存储中的哪些集合将Y设置为子集.集合Y本身不存在于数据存储中,并在运行时指定.
现在解决这个问题的最简单方法是将数据存储器中每组的位字段与集合Y的位字段逐一进行AND运算,选择其AND结果与Y的位域匹配的位.
我怎样才能加快速度呢？是否有树结构(索引)或一些智能算法,允许我执行此查询而无需AND每个存储集的位域？
是否有数据库已经支持大型集合上的此类操作？