我面临一个问题，其中对于多个单词，我调用 HashMultimap (Guava) 来检索一组整数。结果集分别有 10、200 和 600 个项目。我需要计算这三个（或四个，或五个......）集合的交集，并且我需要多次重复整个过程（我有很多单词集合）。然而，我所经历的是，平均而言，这些集合交集需要很长时间来计算（从 0 到 300 毫秒），如果我查看数十万组单词，我的程序需要很长时间才能完成。
有没有更快的方法来实现这一点，特别是考虑到我正在处理（可排序的）整数？
非常感谢！
问问题
2522 次
3 回答
7
如果您能够将您的集合表示为位数组（位图），则可以用 AND 操作将它们相交。您甚至可以实现它以并行运行。
举个例子（使用 jlordo 的问题）：如果 set1 是 {1,2,4} 而 set2 是 {1,2,5}
然后您的第一组将表示为：00010110（为 1、2 和 4 设置的位）。您的第二组将表示为：00100110（为 1、2 和 5 设置的位）。
如果你将它们和在一起，你会得到：00000110（为 1 和 2 设置的位）
当然，如果您有更大范围的整数，那么您将需要更多字节。位图索引的优点在于每个可能的元素只占用一位，因此占用的空间相对较小。
例如，在 Java 中，您可以使用 BitSet 数据结构（但不确定它是否可以并行执行操作）。
于 2013-01-15T11:54:41.603 回答
1
基于位图的解决方案的一个问题是，即使集合本身非常小，但包含非常大的数字（甚至无界），检查位图也会非常浪费。
例如，另一种方法是对两组进行排序、合并并检查重复项。这可以在 O(nlogn) 时间复杂度和额外 O(n) 空间复杂度中完成，给定集合大小为 O(n)。
您应该选择与您的问题描述相匹配的解决方案（输入范围、预期的集合大小等）。
于 2013-01-15T12:21:54.793 回答
0
帖子http://www.censhare.com/en/aktuelles/censhare-labs/yet-another-compressed-bitset描述了具有集合操作（联合、减号和交集）的有序原始长集的实现。以我的经验，它对于密集或稀疏的价值群体非常有效。
于 2013-02-23T07:29:05.977 回答