寻找具有高交集的集合的最快算法

Question

我有大量的用户ID(整数),可能有数百万.这些用户都属于各种组(整数组),因此有大约1000万组.

为了简化我的示例并了解它的本质,我们假设所有组都包含20个用户ID.

我想找到交叉点为15或更大的所有整数集对.

我应该比较每一对吗？(如果我保留一个映射userID以设置成员资格的数据结构,则不需要这样做.)最快的方法是什么？也就是说,我的底层数据结构应该用于表示整数集？排序集,未分类---可以以某种方式散列帮助吗？我应该使用什么算法来计算集合交集)？我更喜欢与C/C++(特别是STL)相关的答案,但也欢迎任何更一般的算法见解.

更新 另外,请注意我将在共享内存环境中并行运行此功能,因此首选干净扩展到并行解决方案的提示.

另外,请注意绝大多数集合对的交集大小为0 ---这意味着使用将用户ID映射到集合的数据结构可能是有利的,以避免计算每对集合的交集.

Answer 1

我会完全按照您的建议行事:将用户映射到他们的小组.也就是说,我会为每个用户保留一个组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 ).考虑到你的问题,这可能比运行的组的天真成对比较要快得多O(G*G*U).