免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 6524 | 回复: 16

[算法] 位图bitmap的高效查找 [复制链接]

论坛徽章:
1
IT运维版块每日发帖之星
日期:2015-09-11 06:20:00
发表于 2013-08-27 16:51 |显示全部楼层
本帖最后由 linuxchyu 于 2013-08-28 14:01 编辑

位图通常用来判断一个元素是否包含在一个集合中,但是,我们也可以换一种用法,比如寻找一个不包含在集合中的一个元素。现一个有1e6以上或1e9级别bit的位图,有什么高效的方法查找第一个为0或为1的位(不要遍历)?

目前有一个想法,就是分层的方法,为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上按序查找效率提高了很多。


大家有没有比这更好的解决办法?

论坛徽章:
4
水瓶座
日期:2013-09-06 12:27:30摩羯座
日期:2013-09-28 14:07:46处女座
日期:2013-10-24 14:25:01酉鸡
日期:2014-04-07 11:54:15
发表于 2013-08-28 13:55 |显示全部楼层
建一个反向记录就可以了拉, 你这bitmap是线性全量的, 建一个(下标->0/1)的有序结构(比如map)就可以解决了啊, 没多少内存.

论坛徽章:
1
IT运维版块每日发帖之星
日期:2015-09-11 06:20:00
发表于 2013-08-28 14:04 |显示全部楼层
回复 2# linux_c_py_php


具体怎么操作呢?如果bitmap达到1e9级别以上,那消耗的内存也挺多的吧

论坛徽章:
4
水瓶座
日期:2013-09-06 12:27:30摩羯座
日期:2013-09-28 14:07:46处女座
日期:2013-10-24 14:25:01酉鸡
日期:2014-04-07 11:54:15
发表于 2013-08-28 14:49 |显示全部楼层
哥, map是稀疏存储, 就算真的是1e9级别, 最多也不超5G内存, 这点内存对于线上生产服务器九牛一毛.

觉得内存不行就leveldb, 一旦压力也没有.

论坛徽章:
1
IT运维版块每日发帖之星
日期:2015-09-11 06:20:00
发表于 2013-08-28 14:58 |显示全部楼层
回复 4# linux_c_py_php
如果是一般的应用,问题好解决,我这个是在opencl的kernel里操作,用那些东西不方便

   

论坛徽章:
4
水瓶座
日期:2013-09-06 12:27:30摩羯座
日期:2013-09-28 14:07:46处女座
日期:2013-10-24 14:25:01酉鸡
日期:2014-04-07 11:54:15
发表于 2013-08-28 15:23 |显示全部楼层
额, 那的确, 你这种多阶的方案也许更好.

论坛徽章:
1
2015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2013-08-30 17:42 |显示全部楼层
你这个分层处理很好。

论坛徽章:
1
技术图书徽章
日期:2014-03-06 15:32:30
发表于 2013-08-31 07:34 |显示全部楼层
你的上层就别用位图了,用计数。最下一层是位图,上边每一层中元素的计数值都是下一层对应一组元素的累加和。顶层就是一个DWORD

论坛徽章:
1
IT运维版块每日发帖之星
日期:2015-09-11 06:20:00
发表于 2013-08-31 09:50 |显示全部楼层
回复 8# selfrun


    一个DWORD不能找到底层第一个为0的位吧

论坛徽章:
1
技术图书徽章
日期:2014-03-06 15:32:30
发表于 2013-08-31 23:23 来自手机 |显示全部楼层
9# linuxchyu


    λ1Gbit,nnλ128M档n-114Mn256bit1257512bit12561λ512kn-2232*256bitn-132128k256kn-3316*32*256bit1128/16=8k,24kn-4316*16*32*256bit18k/16=5121.5k,n-5416*16*16*32*256bit132128DWORDbitδδn-1λ256bit,256bit01,4int64,-1int64,uint646ζλ
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP