有关位图bitmap的高效查找

OSC创始人 发布于 2013/08/27 16:40
阅读 1K+
收藏 4
比如一个有1e6个bit级别的位图,有什么高效的方法查找第一个为0的位?
加载中
0
子矜
子矜
多线程+内存映射
0
OSC创始人
OSC创始人

引用来自“布尔道长”的答案

多线程+内存映射
有没有算法级别的优化?
0
中山野鬼
中山野鬼
_u32 get_pos64(_u64 *p,_u32 len){
    _u32 b = len;
    while (len){
        if (*p++ == 0xffff ffff ffff ffffull){
              break;
        }
        len--;
    }
    return b - len;
}

_u8 get_posb(_u64 d){
    _u8 *p8 = (_u8*)(&d);
    _u8 re = 0;
    _u8 d8;
    while (*p8 == 0xff){
       p8++;
       re+= 8;
       if (re >= 64) {return re;} //error
    }
    d8 = *p8;
    while (d8 & 0x3f){
        d8 <<= 1;
        re++;
    }
    return re;
}

上面的代码,先判断64位的数据中是否包含0,返回64位宽度的位置。下面的代码,是针对一个64位的数据区,检测0出现的位置。这里是按照 低位在前的方式看字节存储的模式。而每个字节中,最先出现的bit在最高位。

_u8 _64 的意思是,8位宽整型, 64位宽整型。不通环境,64位宽的定义不一样,我就用我的类型定义来描述了。能说请问题就行。哈。你需要自己额外改。

0
OSC创始人
OSC创始人

引用来自“中山野鬼”的答案

_u32 get_pos64(_u64 *p,_u32 len){
    _u32 b = len;
    while (len){
        if (*p++ == 0xffff ffff ffff ffffull){
              break;
        }
        len--;
    }
    return b - len;
}

_u8 get_posb(_u64 d){
    _u8 *p8 = (_u8*)(&d);
    _u8 re = 0;
    _u8 d8;
    while (*p8 == 0xff){
       p8++;
       re+= 8;
       if (re >= 64) {return re;} //error
    }
    d8 = *p8;
    while (d8 & 0x3f){
        d8 <<= 1;
        re++;
    }
    return re;
}

上面的代码,先判断64位的数据中是否包含0,返回64位宽度的位置。下面的代码,是针对一个64位的数据区,检测0出现的位置。这里是按照 低位在前的方式看字节存储的模式。而每个字节中,最先出现的bit在最高位。

_u8 _64 的意思是,8位宽整型, 64位宽整型。不通环境,64位宽的定义不一样,我就用我的类型定义来描述了。能说请问题就行。哈。你需要自己额外改。

谢谢你的回答,不过这也算是按序遍历吧?如果bitmap的位非常多的话,应该也挺耗时的。
0
中山野鬼
中山野鬼

引用来自“大大师兄”的答案

引用来自“中山野鬼”的答案

_u32 get_pos64(_u64 *p,_u32 len){
    _u32 b = len;
    while (len){
        if (*p++ == 0xffff ffff ffff ffffull){
              break;
        }
        len--;
    }
    return b - len;
}

_u8 get_posb(_u64 d){
    _u8 *p8 = (_u8*)(&d);
    _u8 re = 0;
    _u8 d8;
    while (*p8 == 0xff){
       p8++;
       re+= 8;
       if (re >= 64) {return re;} //error
    }
    d8 = *p8;
    while (d8 & 0x3f){
        d8 <<= 1;
        re++;
    }
    return re;
}

上面的代码,先判断64位的数据中是否包含0,返回64位宽度的位置。下面的代码,是针对一个64位的数据区,检测0出现的位置。这里是按照 低位在前的方式看字节存储的模式。而每个字节中,最先出现的bit在最高位。

_u8 _64 的意思是,8位宽整型, 64位宽整型。不通环境,64位宽的定义不一样,我就用我的类型定义来描述了。能说请问题就行。哈。你需要自己额外改。

谢谢你的回答,不过这也算是按序遍历吧?如果bitmap的位非常多的话,应该也挺耗时的。
这是最简单也是最高效的做法了。任何其他做法也需要扫瞄一边的。哈。
子矜
子矜
原来ull是一个类型! 懂了~ull=unsigned long long 好久不写C 这些看起来像天书了
中山野鬼
中山野鬼
回复 @布尔道长 : 无符号长整型
子矜
子矜
要找第一个 看来是的从头开始遍历~ 唯一能做到的是 如果中间某个地方找到了 那么后面的就不用找了~
子矜
子矜
0xffff ffff ffff ffffull full都出来了~ 硬是没看懂
0
泡不烂的凉粉
泡不烂的凉粉
很多的位, 只能是顺序遍历. 具体上,牵扯到对齐, 还有大端小端问题. 如果是个作业题, 看来实现代码还真的是有难度.
0
OSC创始人
OSC创始人

引用来自“中山野鬼”的答案

引用来自“大大师兄”的答案

引用来自“中山野鬼”的答案

_u32 get_pos64(_u64 *p,_u32 len){
    _u32 b = len;
    while (len){
        if (*p++ == 0xffff ffff ffff ffffull){
              break;
        }
        len--;
    }
    return b - len;
}

_u8 get_posb(_u64 d){
    _u8 *p8 = (_u8*)(&d);
    _u8 re = 0;
    _u8 d8;
    while (*p8 == 0xff){
       p8++;
       re+= 8;
       if (re >= 64) {return re;} //error
    }
    d8 = *p8;
    while (d8 & 0x3f){
        d8 <<= 1;
        re++;
    }
    return re;
}

上面的代码,先判断64位的数据中是否包含0,返回64位宽度的位置。下面的代码,是针对一个64位的数据区,检测0出现的位置。这里是按照 低位在前的方式看字节存储的模式。而每个字节中,最先出现的bit在最高位。

_u8 _64 的意思是,8位宽整型, 64位宽整型。不通环境,64位宽的定义不一样,我就用我的类型定义来描述了。能说请问题就行。哈。你需要自己额外改。

谢谢你的回答,不过这也算是按序遍历吧?如果bitmap的位非常多的话,应该也挺耗时的。
这是最简单也是最高效的做法了。任何其他做法也需要扫瞄一边的。哈。
目前有一个想法,就是分层的方法,为bitmap再制作一上层bitmap,如果下层的bitmap的一个字节或4个字节中含有0(或1),则其上层bitmap对应的位就置为0(或1)如果需要的话还可以增加一层bitmap。
举个例子,开始一个bitmap位为如下:
00101010  11111111  11111111  01000000 00000000 11111000

则为它添加的上层bitmap(如果下层bitmap的一个字节含有0,则上层bitmap对应的位就是0,否则为1)就应该是:011000

在查找原始bitmap第一个为0的位时,首先按序查找上层的bitmap首先为0的位,然后在其下层的bitmap中对应的字节按序遍历就可以找到原来bitmap中首先为0的位了,这样,相比在原始的bitmap上按序查找效率提高了很多。

0
泡不烂的凉粉
泡不烂的凉粉

大概步骤是, 至少定义一个联合类型.  是一个字符串和一个 ull 数组的联合. 1e6 还不算很大.

首先将位图数据填充进联合串里. 之后顺序匹配数组值, 直接取反操作, 非零为找到.否则继续. 每次为找到情况下,计数器增加64. 找到,就根据大小端,分4次找到具体所在字节. 每次计数器增加8.(突然想到也可以忽略大小端,直接用char类型来匹配, 仍然每次计数器+8) 最后一个位移匹配,找到位置, 每次循环计数器+1.

0
中山野鬼
中山野鬼

引用来自“大大师兄”的答案

引用来自“中山野鬼”的答案

引用来自“大大师兄”的答案

引用来自“中山野鬼”的答案

_u32 get_pos64(_u64 *p,_u32 len){
    _u32 b = len;
    while (len){
        if (*p++ == 0xffff ffff ffff ffffull){
              break;
        }
        len--;
    }
    return b - len;
}

_u8 get_posb(_u64 d){
    _u8 *p8 = (_u8*)(&d);
    _u8 re = 0;
    _u8 d8;
    while (*p8 == 0xff){
       p8++;
       re+= 8;
       if (re >= 64) {return re;} //error
    }
    d8 = *p8;
    while (d8 & 0x3f){
        d8 <<= 1;
        re++;
    }
    return re;
}

上面的代码,先判断64位的数据中是否包含0,返回64位宽度的位置。下面的代码,是针对一个64位的数据区,检测0出现的位置。这里是按照 低位在前的方式看字节存储的模式。而每个字节中,最先出现的bit在最高位。

_u8 _64 的意思是,8位宽整型, 64位宽整型。不通环境,64位宽的定义不一样,我就用我的类型定义来描述了。能说请问题就行。哈。你需要自己额外改。

谢谢你的回答,不过这也算是按序遍历吧?如果bitmap的位非常多的话,应该也挺耗时的。
这是最简单也是最高效的做法了。任何其他做法也需要扫瞄一边的。哈。
目前有一个想法,就是分层的方法,为bitmap再制作一上层bitmap,如果下层的bitmap的一个字节或4个字节中含有0(或1),则其上层bitmap对应的位就置为0(或1)如果需要的话还可以增加一层bitmap。
举个例子,开始一个bitmap位为如下:
00101010  11111111  11111111  01000000 00000000 11111000

则为它添加的上层bitmap(如果下层bitmap的一个字节含有0,则上层bitmap对应的位就是0,否则为1)就应该是:011000

在查找原始bitmap第一个为0的位时,首先按序查找上层的bitmap首先为0的位,然后在其下层的bitmap中对应的字节按序遍历就可以找到原来bitmap中首先为0的位了,这样,相比在原始的bitmap上按序查找效率提高了很多。

你这个实际是做索引的方法,如果你要这么折腾,还不如游程编码呢。反正你想一次算清楚,下次别重复算。哈。我以为你要个对未知空间的单次分析算法呢。
0
中山野鬼
中山野鬼

引用来自“看能不能改个名”的答案

大概步骤是, 至少定义一个联合类型.  是一个字符串和一个 ull 数组的联合. 1e6 还不算很大.

首先将位图数据填充进联合串里. 之后顺序匹配数组值, 直接取反操作, 非零为找到.否则继续. 每次为找到情况下,计数器增加64. 找到,就根据大小端,分4次找到具体所在字节. 每次计数器增加8.(突然想到也可以忽略大小端,直接用char类型来匹配, 仍然每次计数器+8) 最后一个位移匹配,找到位置, 每次循环计数器+1.

哈。你这种方法也常用。64个64位宽的整型数组;不过注意摆放位置了,字节顺序和字节内的bits顺序,通常是反过来的。所以,a[i] != ~(1<<i);
中山野鬼
中山野鬼
回复 @看能不能改个名 : 高端的毛线,编的标准“地板”码。哈
泡不烂的凉粉
泡不烂的凉粉
回复 @中山野鬼 : 你那太高端, 不懂,祝你顺利.我去看电影去
中山野鬼
中山野鬼
回复 @看能不能改个名 : 哈,在debug一个上下文无关的语法解析器。
泡不烂的凉粉
泡不烂的凉粉
还没睡呢. 看来怎俩作息时间有一拼
返回顶部
顶部