java - 创建位矩阵和扫描集列的有效方法

Question

这是我当前的问题，我有许多 Bloom 过滤器，我想将它们构造成一个矩阵，比如：

[0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]
...
[1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0]

每列都将派生自 BitSet，除了循环所有行并比较每个索引之外，是否有更有效的方法来查找所有位设置为 1 的列？

是否有任何数据结构可以帮助我解决这个问题？

Answer 1

假设您正在寻找哪些列包含一个，现在每列包含多少个，循环遍历它们似乎是最好的主意。

如果您使用一些短路逻辑来实现循环，那么您将获得更好的平均运行时间。

就像是：

for (int column = 0; column < width; column++) {
    for (int row = 0; row < height; row++) {
        if (array[column][row] == 1) {
            list.append(column);
            break;  // move on to the next column because we don't care what's 
                    // left in this column as we already found our '1'

使用此代码，您将获得（如果每个都是）的最坏情况的运行时间 （是 的总数），这非常好。bit0nnbits

但是，除非您非常不走运，否则由于短路逻辑，您将获得更好的运行时间。

上述适用于位数组，但是，BitSets它们本身具有一些有用的功能。

ABitSet包含以下函数：length()它返回具有设置位 + 1 的最高索引（或者0如果没有设置位），nextSetBit(index)并且返回下一个设置位的索引（index -> end包含）。

所以你的代码很容易是这样的：

int index = 0;

while (index < BitSet.length()) {
    index = BitSet.nextSetBit(index);
    list.append(index);
    index++;
}