位图
今天我们所介绍的数据结构叫做位图,在谈什么是位图之前我们先来看一道"非常简单的题":有40亿个无符号的整型数据,现在给定一个目标数字,判断这个数字是否在这40亿数据中。题目看起来确实非常简单,有的同学说直接遍历一遍不就ok了吗?还有的同学给出了更高效的查找方式就是将这些数字排序然后进行二分查找。但是,这是有问题的,问题并不在于你搜索这个数字的效率问题,而是你在遍历也好排序也罢,这些数字在内存中放的下么?
一个整型int就是4个字节,10亿个int差不多已经需要4G的内存了,40亿个int就是16G。所以这里方法行不通的根本原因实际上是内存不够,但是我们今天的讲的位图却能很好的帮助我们处理这个问题。
位图模型
既然根本原因是这些数据用int放不下,那么是否有更小的东西标记这些数字呢?没错,有的同学想到了,char只占一个字节或许能表示一个数字,但是随着数字位数的增多,依旧不可能使用一个字符表示一个数字,这就意味着小于4G内存还是不能解决这个问题。
其实说到这里,我们的问题就转化为如何使用更小的内存单元来标记一个数字,而在程序中我们最小的访问单位的bit位,所以现在我们一起来看使用比特位如何标记(映射)这些数据。
现在我们发现,4个字节本来只能存储一个int,而现在使用位图我们就存了(映射)32个数字,意味着16G/32约等于500m左右我们就能映射这些数据,那么这些数据是怎么映射到位图种的呢?接着看。
设计位图
为了方便,我们将位图用一个数组表示,让vector帮我们开辟一段连续的空间,我们只负责将数据设置或者移除就行。
class BitMap
{
public:
BitMap(size_t range)
{
//右移5位相当于除以32,加1是因为小于32的数字如果与32相除则得到0
_bitTable.resize((range >> 5) + 1);
}
private:
vector<int> _bitTable;
};
1
2
3
4
5
6
7
8
9
10
11
12
位图元素的设置
void SetBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
_bitTable[index] |= (1 << num);
}
1
2
3
4
5
6
7
来看看为什么需要size_t index = x >> 5和size_t num = x % 32两步操作:我们看看要映射5和32这俩个数
5表示防在第1个整型空间的第5位上,32则表示放在第2个整型空间第一位上。而**bitTable[index] |= (1 << num)**能保证把第num位上的数字设置为1,其余数字保持不变。
位图元素的移除
比较简单,需要知道的是**~(1 << num)**表示出了num位为0,其余位都为1.
void RemoveBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
_bitTable[index] &= ~(1 << num);
}
1
2
3
4
5
6
7
位图元素的查找
这个没啥好说的,很简单,说到这里,你的位图也就实现完了,非常简单把
bool TestBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
return _bitTable[index] & (1 << num);
}
1
2
3
4
5
6
7
完整代码:
class BitMap
{
public:
BitMap(size_t range)
{
_bitTable.resize((range >> 5) + 1);
}
//标识一个数字在位图中的位置
void SetBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
_bitTable[index] |= (1 << num);
}
//取消数字在位图当中的标识.
void RemoveBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
_bitTable[index] &= ~(1 << num);
}
bool TestBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
return _bitTable[index] & (1 << num);
}
private:
vector<int> _bitTable;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
拓展
现在将问题修改为让你寻找出40亿个数据中出现过两次的数据,此时我们就需要使用两位来标记同一个数据了。
N位位图的实现如下:
class NBitMap
{
public:
NBitMap(size_t range)
{
_bitTable.resize((range >> 4) + 1);
}
void SetBit(size_t x)
{
size_t index = x >> 4;
size_t num = x % 16;
num *= 2;
bool first = _bitTable[index] & (1 << num);
bool second = _bitTable[index] & (1 << (num + 1));
if (!(first && second))
{
_bitTable[index] += (1 << num);
}
}
bool TestBit(size_t x)
{
size_t index = x >> 4;
size_t num = x % 16;
num *= 2;
return (_bitTable[index] >> num) & 0x03;
}
private:
vector<int> _bitTable;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
相关推荐
BMP 位图 显示原理 BMP 位图 显示原理 BMP 位图 显示原理
Oracle 数据库的位图索引原理与应用.pdf
透明位图 背景透明 VC代码 ; 注释清晰,代码简洁一目了然,附带透明位图原理说明文档。
源码 博文链接:https://smallsmile.iteye.com/blog/777572
图像处理\用Visual C++显示位图 的原理与方法.pdf
透明位图,在MFC里面的应用很广,介绍了一下原理,以及分步的实现,主要函数的应用
MTK6226__CPU原理角位图
我自己整理的可能比较乱,大家可以根据需要摘取。
那个数值,如果可以,则此数值即为符合8位位图原理,否则,不符合。第二,用12 位的编码来表示一个任意的32 位数是不可能的,只能通过循环 右移八位二进制数偶数位来得到一部分32 位数,其余的无法表示的32 位数,...
用Visual C++显示位图的原理与方法 <<电脑编程技巧与维护 >>2001年01期 王丰 <br>一、介绍 在VC++环境下显示位图并不是什么新技术,但本文仍然在此"老调重弹"的原因是:(1)这一技术十分重要,它是图像编程的...
本文详细介绍了位图“马赛克化”的原理,并以BMP位图为例,讨论了马赛克特校的编程实现,并在VC6.0下实现了不同色素下位图马赛克特效演示。
印刷原理公式位图PPT学习教案.pptx
PiCon一个Pilosa高性能分布式位图索引的基于文本的简单控制台
位图的结构原理和调色板原理,包括windows中位图的数据结构,可以详细了解位图。
vc++编写的bmp位图组合成avi动画源代码例子 vc++书籍上的经典例子保证可以使用
DDR4台式机内存条原理图,用于内存条维修的第一手好资料
PIC单片机与CAN总线进行通讯的原理图 引脚接线 硬件连接图
VB制作基于BMP位图的图标工具栏,把一些基于位图格式的图标添加到工具栏窗口上,美化工具栏,更显专业,也有利于操作,具体是怎么实现的呢?这个VB源码会演示实现原理,推荐下载。
Delphi:Delphi创建和生成位图的实例,可以统计生成的做做位图颜色值,帮助初学者理解Delphi创建位图的原理。
冶金熔炼原理及工艺讲义,第一章 活度及氧位图-修订.ppt