C++:从位构建迭代器

Question

我有一个位图,并希望返回设置位位置的迭代器.现在我只是走完整个位图,如果设置了位,那么我提供下一个位置.我相信这可以更有效地完成:例如,为单字节中的每个位组合构建静态数组并返回位置向量.这不能用于整个int,因为数组太大了.但也许有更好的解决方案？你知道任何智能算法吗？

Answer 1

我可以提出几个想法.

• 结果是现代CPU具有用于在32位或64位字中查找下一个设置位的专用指令.
• 我非常喜欢你从准备好的高效的每字节迷你迭代器构建整个位图的迭代器的想法,这真的很酷,我很惊讶我以前从未见过它!
• 如果您的位图非常稀疏,您可以用其他形式表示它,例如平衡树,其中迭代算法是众所周知的.
• 如果你的位图稀疏但是有密集的区域(这听起来很奇怪,但我遇到的情况确实如此),使用小型(32位或64位)位图的平衡树并使用组合迭代算法对于一棵树和一个单词的位.
• 为了避免显式树的内存开销,请使用隐式树,就像规范的heapsort算法一样.之后你的位集合是准备,不会被突变,建立在它的上面是"金字塔",其中电平(N + 1)[I] =电平(N)[2*I] | 电平(N)[2*I + 1].这将允许您快速跳过bitset的无人区域,并且迭代将以类似于迭代常规二叉树的方式完成.你也可以从字节等开始构建一个居住的金字塔:这一切都取决于你的bitset稀疏程度.
• 有一个众所周知的比特技巧,用于查找单词中前导零的数量; 例如,请参阅java标准库的代码:
• 通过使用被动迭代器而不是活动迭代器,你可能会获得很多性能,ti而不是begin()和operator ++(),为你的bitset提供foreach(F)函数,其中F有operator().如果需要提前终止的被动迭代,请使F的operator()返回一个布尔值,表示是否请求终止.

编辑:我无法抗拒尝试为字节准备迭代器的方法.我在C#2.0中编写了一个代码生成器,它生成以下形式的代码:

IEnumerable<int> bits(byte[] bytes) {
    for(int i=0; i<bytes.Length; ++i) {
        int oi=8*i;
        switch(bytes[i]) {
            ....
            case 74: yield return oi+1; yield return oi+4; yield return oi+6; break;
            ....
        }
    }
}

我将其随机50%填充字节数组(10Mb)的位数与完全不使用迭代器的代码的性能进行了比较,并且包含两个循环:

for (int i = 0; i < bytes.Length; ++i) {
    byte b = bytes[i];
    for (int j = 7; j >= 0; --j) {
        if (((int)b & (1 << j)) != 0) s++;
    }
}

第二个代码片段比第一个代码片段快1.66倍(~1.5s vs~2.5s).我认为稀疏位数组甚至可能使第一个代码优于第二个代码.