我有大量的用户id(整数),可能有数百万。这些用户都属于不同的组(整数集),因此大约有1000万个组。
为了简化我的示例并了解其本质,我们假设所有组都包含20个用户id。
我想找到所有的整数集的交集大于等于15的对。
我应该比较每一组吗?(如果我保留一个将用户id映射到设置成员身份的数据结构,这是不必要的。)最快的方法是什么?也就是说,我的底层数据结构应该用来表示整数集吗?排序集,未排序---散列有什么帮助吗?我应该用什么算法来计算集合交集呢?我更喜欢与C/C++(特别是STL)相关的答案,但也欢迎任何更一般的算法洞察力。
更新
另外,请注意,我将在共享内存环境中并行运行这个程序,因此最好使用干净地扩展到并行解决方案的思想。
另外,请注意,绝大多数集合对的交集大小为0,这意味着使用将用户id映射到集合的数据结构可能有利于避免计算每对集合的交集。
最佳答案
我会按照你的建议做:将用户映射到他们的组。也就是说,我会为每个用户保留一个组id列表。然后我将使用以下算法:
foreach group:
map = new Map<Group, int> // maps groups to count
foreach user in group:
foreach userGroup in user.groups:
map[userGroup]++
if( map[userGroup] == 15 && userGroup.id > group.id )
largeIntersection( group, userGroup )
假设每个组平均包含
G
个用户,并且这些用户平均属于U
个组,那么这将在g
中运行。考虑到你的问题,这可能比在O( G*U*g )
中运行的组的简单成对比较快得多。关于algorithm - 查找高交集的最快算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/2697183/