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

Question

这是我当前的问题，我有许多布隆过滤器，我想将它们构造成一个矩阵，例如:

[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

假设您正在查找哪些列包含 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'

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

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

上面的方法适用于位数组，但是，BitSets 有自己的一些有用的功能。

BitSet 包含以下函数:length()，它返回设置位 + 1 的最高索引(如果存在，则返回 0没有设置位)和 nextSetBit(index) 返回从 index -> end 包含的下一个设置位的索引。

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

int index = 0;

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