位图原理及实现 - 海量数据处理标配
下午的时候写了一下位运算的：位运算 - 初见
我个人感觉如果对位运算不是很熟的话可以先看一下上面那个
位图 - 数据结构
为什么要位图？上一篇里面有个例子，是这样的：
你要给1亿个int型数据去重（本篇不讲int以外的，int以外的等我学了布隆过滤器或者各位自行学习布隆过滤器之后再说），要怎么弄？
一般对于去重的思路就是：排序、遍历、去重。
那，就先讲这个排序。怎么排？看完上一篇的小伙伴都知道，用“位”来排序，快。
但是，时间是有了，空间呢？来算一笔账啊：一个int，4个字节，256个int是1k，大概25W个数据为1M，那1billion个数据，就是400M。
那2.5billion个数据就是1G了。
这动不动就要耗费这么大的内存来排个序，挺好。
而位图，就将大大地缩小这个，内存占用。
都知道，一个int是32个字节，那如果用每个字节来存一个数据，又当如何？
先不要问怎么实现的（映射），至少现在知道，一个int可以存32个数据，那么这个空间是不是被直接压缩了32倍。
那1亿个数据也不用400M的内存来排序了，只要25M，接受了这个观点，咱再继续往下。
位图设计
数据结构构造
为了方便，我们将位图用一个数组表示，让vector帮我们开辟一段连续的空间，我们只负责将数据设置或者移除就行。
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
先把这个构造函数看懂了，不然下面就一团晕。
新元素插入
读取到一个数据，自然是要插入到位图中
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，其余数字保持不变。
位图中元素移出
这个就比较直观了，如果位运算熟练的话
void RemoveBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32; _bitTable[index] &= ~(1 << num); //~(1 << num) ：除了num位为0，其余位都为1
}
- 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
找出二次出现的数据
此时我们就需要使用两位来标记同一个数据了。
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
思考
如何分辨一次出现、二次出现与多次出现的数据？
文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。
原文链接：lion-wu.blog.csdn.net/article/details/107258974
- 点赞
- 收藏
- 关注作者
评论（0）