c# bitarray 索引的正位

Question

我有一个长度相当大 (500,000) 的 c# BitArray，我正在尝试获取数组中所有正位集的索引。目前我正在通过以下方式实现这一目标:

public int[] GetIndexesForPositives()
{
    var idIndexes = new int[GetPositiveCount + 1];
    var idx = 0;
    for (var i = 0; i < Length; i++)
        {
            if (Get(i))
            {
                idIndexes[idx++] = i;
            }
        }
    return idIndexes;
}

我创建了一个已知正位大小的空数组，然后遍历该位数组并将索引值添加到返回数组。

这意味着我必须在数组上执行 500,000 次循环，而且速度并不快。 (大约需要 15 毫秒)。

我知道 BitArray 在幕后使用整数数组(我用它来编写 GetPositiveCount 函数 - 通过我从堆栈中取出的算法)，我想知道是否也有算法可以做到这一点？

Answer 1

如果您可以从 BCL 中换出 BitArray 以支持“自己滚动”，您可以做得更好。您可以执行以下几项操作:

1. 跳过没有位设置的 64 block
2. 对于确实有位的 64 block ，仅枚举 1 位而不是使用 x & (x - 1) 枚举所有位，找到您最喜欢的快速 2log here (使用朴素的 64 步方法不会提供任何加速)
3. 保留一个额外的位数组，用于存储每个 64 位 block 是否为非零。将项目符号 2 中的技术应用于那个位数组，一次性跳过整个零范围。
4. 对巨大的位数组递归地应用第 3 点

所有这四种方法只有在位数组被认为是稀疏的情况下才有用，如果它不是稀疏的，最坏的情况仍然是 O(n)。如果应用项目符号 3 直到顶部是单个 ulong，那么它可以在 O(1) 中确定整个位数组是否为空。