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

Question

下面的函数接收两个 BitSet，复制第一个（不要覆盖它），与第二个进行交集计算（按位与），并返回结果的基数。

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

我想知道这段代码是否可以加速？该函数被调用了数十亿次，因此即使微秒级别的加速也有意义，而且我对最快的可能代码很感兴趣。

- Brandon McHomery

---

一个想法：你可以尝试避免创建一个新的BitSet，因为你只是要扔掉它。 - Andy Turner

需要更多信息：调用十亿次大约需要多长时间？你能否更改你的算法，不需要调用十亿次吗？ - Andy Turner

我没有检查BitSet的内部，但可能可以一次性完成所有操作，而不是先进行“and”，然后再进行“cardinality”尝试在手动执行“and”的同时计算基数？ - Mateusz Dymczyk

@MateuszDymczyk 看起来 intersects 方法可以被改进来实现这个功能，只需将 (a & b) != 0 替换为 Long.countBits(a & b) 并求和即可。但是这需要访问私有变量 words。 - Andy Turner

传统智慧认为，与其追求最快的方式，不如开发一种正确的方式，它能够读取并易于维护。执行速度优化是你在基准测试证明你的解决方案是性能瓶颈后深入探究的事情（大多数情况下，它并不是）。 - scottb

Answer 1

如果您要多次使用每个BitSet，创建与每个BitSet对应的long数组可能是值得的。 对于每个BitSet：

long[] longs = bitset.toLongArray();

接下来，您可以使用以下方法，避免创建克隆的 BitSet 的开销。（假设两个数组的长度相同）。

int getIntersectionSize(long[] bits1, long[] bits2) {
    int nBits = 0;
    for (int i=0; i<bits1.length; i++)
        nBits += Long.bitCount(bits1[i] & bits2[i]);
    return nBits;
}

- James Trimble

Answer 2

这里有一个替代版本，但我不确定它是否真的更快，取决于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;
}

- maraca

---

如果您想使用BitSet功能，我认为您的版本可能是最好的。对于“稀疏” BitSets，上述方法可能也不错。如果您需要的话，我可以将其删除。 - maraca

@maraca 这样做会更慢，因为你是逐位处理的，而 BitSet 内部是按字处理的，所以例如 and 的操作次数要小得多。 - Mateusz Dymczyk

@MateuszDymczyk，对于“稀疏”BitSet（大多数位都为false），还能更好吗？ - maraca

对于非常稀疏的集合，@maraca 很可能是正确的。 - Mateusz Dymczyk

@BrandonMcHomery 你可以尝试实现Andy Turner的想法，但是因为你需要在两个bitSets上都调用toLongArray并且克隆它们，所以我猜也不会更快。 - maraca

Answer 3

最近我一直在寻找解决方案，这是我想到的：

int intersectionCardinality(final BitSet lhs, final BitSet rhs) {
    int lhsNext;
    int retVal = 0;
    int rhsNext = 0;

    while ((lhsNext = lhs.nextSetBit(rhsNext)) != -1 &&
            (rhsNext = rhs.nextSetBit(lhsNext)) != -1) {
        if (rhsNext == lhsNext) {
            retVal++;
            rhsNext++;
        }
    }

    return retVal;
}

也许有人想花时间比较这里的不同解决方案并发布结果...

- Yossi Farjoun