java - 更快的集合交集方法

Question

我面临一个问题，对于多个单词，我调用 HashMultimap (Guava) 来检索一组整数。生成的集合分别包含 10、200 和 600 个项目。我需要计算这三个(或四个，或五个......)集合的交集，并且我需要多次重复整个过程(我有很多单词集合)。然而，我所经历的是，平均而言，这些集合交集的计算时间很长(从 0 到 300 毫秒)，如果我查看数十万个单词集，我的程序需要很长时间才能完成。

是否有任何更快的方法来实现这一点，特别是考虑到我正在处理(可排序的)整数？

非常感谢!

Answer 1

如果您能够将集合表示为位数组(位图)，则可以使用 AND 运算将它们相交。您甚至可以实现它以并行运行。

举个例子(使用jlordo的问题):如果set1是{1,2,4}并且set2是{1,2,5}

那么您的第一组将表示为:00010110(位设置为 1、2 和 4)。您的第二组将表示为:00100110(位设置为 1、2 和 5)。

如果将它们与在一起，您将得到:00000110(为 1 和 2 设置的位)

当然，如果您有更大的整数范围，那么您将需要更多的字节。位图索引的优点在于，它们每个可能的元素只占用一位，因此占用相对较小的空间。

例如，在 Java 中，您可以使用 BitSet 数据结构(但不确定它是否可以并行操作)。