相关疑难解决方法(0)

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

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

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

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

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

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

在一些博客和lucene网站中，我知道lucene在倒排索引中使用数据结构“跳过列表”。但我对此有一些困惑。

1：一般情况下，跳过列表可能会在内存中使用，而倒排索引则存储在磁盘中。那么lucene在索引搜索时如何使用它呢？只是将其扫描到磁盘上还是将其加载到内存中？

2：skip list的插入操作符经常使用random(0,1)来决定是否插入到下一级，但是在lucene的介绍中，似乎每一项都是固定的间隔，那么lucene如何创建不同或不不同的“skip list”呢？

如果我错了，请纠正我。