位图原理及实现 – 海量数据处理标配

下午的时候写了一下位运算的:位运算 – 初见
我个人感觉如果对位运算不是很熟的话可以先看一下上面那个

位图原理及实现 - 海量数据处理标配

位图 – 数据结构

为什么要位图?上一篇里面有个例子,是这样的:
你要给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); 	} 

先把这个构造函数看懂了,不然下面就一团晕。

新元素插入

读取到一个数据,自然是要插入到位图中

	void SetBit(size_t x) 	{ 		size_t index = x >> 5; 		size_t num = x % 32;  		_bitTable[index] |= (1 << num); 	} 

如果是为了去重,在这里就可以动手脚了,不过本着“单一职责原则”,我就不动手脚了。

来看看为什么需要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 	} 

位图元素查找

可用于查找,也可用于查重。

bool TestBit(size_t x) { 	size_t index = x >> 5; 	size_t num = x % 32;  	return _bitTable[index] & (1 << num); } 

这些功能也差不多够用了,接下来组装一下。

完整代码

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; }; 

找出二次出现的数据

此时我们就需要使用两位来标记同一个数据了。

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; }; 

思考

如何分辨一次出现、二次出现与多次出现的数据?

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 位图原理及实现 – 海量数据处理标配

提供最优质的资源集合

立即查看 了解详情