设置交集的更快方法

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数据结构(不确定它是否可以并行执行操作).