1. 什么是位图?
位图就是 bitmap 的缩写所谓 bitmap, 就是用每一位来存放某种状态, 适用于大规模数据, 但数据状态又不是很多的情况通常是用来判断某个数据存不存在的在 STL 中有一个 bitset 容器, 其实就是位图
所以我们可以了解到, 位图就是一个只用每一位来保存数的状态的结构
2. 位图的用处?
位图主要用于海量数据处理, 索引, 数据压缩等方面有广泛应用
3. 位图的结构
关于位图的结构, 类似于哈希, 位图就是一个用每一位的 0,1 来表示一个数的状态
比如, 我们现在有一个文件, 这个文件中有数 1,5,4294967295 我们就把第 1 位, 第 5 位, 第 4294967295 位改为状态 1
4. 位图题目操练
给 4 0 亿个不重复的无符号整数, 没排过序给一个无符号整数, 如何快速判断一个数是否在这 4 0 亿个数中
题目分析: 这是一道关于海量数据查找的题, 其实这道题, 我们就可以和哈希表联系在一起, 为何说是海量数据呢, 对于一个 40 亿整数, 我们如果要存的话, 按照无符号整数来存储, 那么下来, 大概就需要 40 亿 * 4 这么些字节, 下来大概就是 16G 的 内存
对于现在的 64 位机, 普遍标配内存也就是 4-8G 的内存, 显而易见, 16G 是没有办法一次性处理的那么我们如何是好? 进行拆分? 这样显然也是不好的, 怎么拆, 还有效率问题
所以在这里我们采取一种新的思路, 这种思路就是位图
位图结构定义
- typedef struct BitMap
- {
- size_t* _bits;
- size_t _range;
- }BitMap;
位图相关接口
- void BitMapInit(BitMap *bm,size_t range) // 初始化
- {
- assert(bm);
- bm->_bits = NULL;
- bm->_range = range;
- bm->_bits = (size_t *)malloc(sizeof(char)*bm->_range/8);
- assert(bm->_bits);
- memset(bm->_bits,0,sizeof(char)*bm->_range/8);
- }
- void BitMapSet(BitMap *bm,size_t x)// 标记相应位
- {
- size_t num = x>>5;
- size_t bit = x%32;
- bm->_bits[num] |=(1<<bit);
- }
- void BitMapReset(BitMap *bm,size_t x)// 恢复相应位
- {
- size_t num = x>>5;
- size_t bit = x%32;
- bm->_bits[num] &= (~(1<<bit));
- }
- int BitMapTest(BitMap *bm,size_t x)
- {
- size_t num = x>>5;
- size_t bit = x%32;
- if ((1<<bit)&bm->_bits[num])
- return 0;
- return -1;
- }
测试案例及结果截图:
- void TestBitMap()
- {
- BitMap bm;
- BitMapInit(&bm,-1);
- BitMapSet(&bm,5);
- BitMapSet(&bm,6);
- BitMapSet(&bm,7);
- BitMapSet(&bm,8);
- BitMapSet(&bm,-1);
- printf("%d\n",BitMapTest(&bm,4));
- printf("%d\n",BitMapTest(&bm,5));
- printf("%d\n",BitMapTest(&bm,6));
- printf("%d\n",BitMapTest(&bm,7));
- printf("%d\n",BitMapTest(&bm,8));
- printf("%d\n",BitMapTest(&bm,-1));
- }
这道题中位图结构代码不难, 注意理解思路, 必须熟练掌握位运算
5. 总结
优缺点:
(1)可读性差
(2)位图存储的元素个数虽然比一般做法多, 但是存储的元素大小受限于存储空间的大小位图存储性质: 存储的元素个数等于元素的最大值比如, 1K 字节内存, 能存储 8K 个值大小上限为 8K 的元素 (元素值上限为 8K , 这个局限性很大!) 比如, 要存储值为 65535 的数, 就必须要 65535/8=8K 字节的内存要就导致了位图法根本不适合存 unsigned int 类型的数(大约需要 2^32/8=5 亿字节的内存)
(3)位图对有符号类型数据的存储, 需要 2 位来表示一个有符号元素这会让位图能存储的元素个数, 元素值大小上限减半 比如 8K 字节内存空间存储 short 类型数据只能存 8K*4=32K 个, 元素值大小范围为 -32K~32K
来源: http://blog.csdn.net/qq_38646470/article/details/79427038