Java获取BitSet交集基数的最快方法

Question

下面的函数需要两个BitSets,复制第一个(它不能被覆盖),将副本与第二个(按位AND)相交并返回结果的基数.

public int getIntersectionSize(BitSet bits1, BitSet bits2) {
    BitSet copy = (BitSet) bits1.clone();
    copy.and(bits2);
    return copy.cardinality();
}

我对这段代码加速感兴趣吗？这个功能被称为十亿次,所以即使是微秒加速也是有道理的,而且我对最快的代码感到好奇.

Answer 1

这是一个替代版本，但我不确定它是否真的更快，取决于nextSetBit.

public int getIntersectionsSize(BitSet bits1, BitSet bits2) {
   int count = 0;
   int i = bits1.nextSetBit(0);
   int j = bits2.nextSetBit(0);
   while (i >= 0 && j >= 0) {
      if (i < j) {
         i = bits1.nextSetBit(i + 1);
      } else if (i > j) {
         j = bits2.nextSetBit(j + 1);
      } else {
         count++;
         i = bits1.nextSetBit(i + 1);
         j = bits2.nextSetBit(j + 1);
      }
   }
   return count;
}

上面是可读版本，希望对编译器来说足够好，但我猜你可以手动优化它：

public int getIntersectionsSize(BitSet bits1, BitSet bits2) {
   int count = 0;
   for (int i = bits1.nextSetBit(0), j = bits2.nextSetBit(0); i >= 0 && j >= 0; ) {
      while (i < j) {
         i = bits1.nextSetBit(i + 1);
         if (i < 0)
            return count;
      }
      if (i == j) {
         count++;
         i = bits1.nextSetBit(i + 1);
      }
      while (j < i) {
         j = bits2.nextSetBit(j + 1);
         if (j < 0)
            return count;
      }
      if (i == j) {
         count++;
         j = bits2.nextSetBit(j + 1);
      }
   }
   return count;
}