海量数据处理第二谈-----位图BitMap
成都创新互联公司服务项目包括莫力达网站建设、莫力达网站制作、莫力达网页制作以及莫力达网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,莫力达网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到莫力达省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!
位图的概念:
在C++中,位图是以位来表示整数的结构,普通的整数一个数需要用4个字节来表示,我们可以换种思想,在整个整数的集合范围内,某个整数存在与否,只有两种情况,在或者不在,那么,我们可以考虑只用一个bit位,来表示该整数存在的状态,从而达到节省内存的目的。
位图实例分析:
给一个实际的例子,给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中
我们可以简单计算一下,40亿个整数全部放到内存,需要160亿个字节,粗略计算,大致需要16G的内存,如果我们把每个整数是否出现,转换成用一位来表示它存在的状态,需要5亿个字节,也就是大约500M的内存,对于计算机而言,对内存的节省亦常地重要,这就是位图的一个重要应用。
位图模拟实现:
首先我们考虑位图的结构,实际上也是对数组的封装,只不过我们这里需要的是以bit位为单位进行存放,每一位的状态只有0和1两种,这里用来表示该整数是否在位图内。
我们以一个×××为例,在一个×××的空间,存储【1 6 9 4 12 10】这些数,存储结果应该如下:
这个只给出了两个字节,全可以表示上面的6个整数。
关于位图的底层,这里我们使用vector来模拟实现。
#include#include using namespace std; class BitMap { public: BitMap(const size_t& range) { int sz = (range >> 5) + 1; _vec.resize(sz); } void BitSet(const size_t& x) { int index = x >> 5; // index是x对应位所在的下标 int num = x % 32; // num是x对应该×××的第多少位 _vec[index] |= 1 << num; } void BitReSet(const size_t& x) { int index = x >> 5; // index是x对应位所在的下标 int num = x % 32; // num是x对应该×××的第多少位 _vec[index] &= (~(1 << num)); } bool BitTest(const size_t& x) { int index = x >> 5; // index是x对应位所在的下标 int num = x % 32; // num是x对应该×××的第多少位 return _vec[index] & (1 << num); } protected: vector _vec; };
位图的实现实际上就是进行一系列的位操作,通过位操作找到该×××对应的位,下面给出一组简单的测试用例
void TestBitMap() { BitMap mp(100); mp.BitSet(1); mp.BitSet(2); mp.BitSet(11); mp.BitSet(22); cout << "test --<1>" << mp.BitTest(1) << endl; cout << "test --<2>" << mp.BitTest(2) << endl; cout << "test --<11>" << mp.BitTest(11) << endl; cout << "test --<22>" << mp.BitTest(22) << endl<" << mp.BitTest(1) << endl; cout << "test --<2>" << mp.BitTest(2) << endl; cout << "test --<11>" << mp.BitTest(11) << endl; cout << "test --<22>" << mp.BitTest(22) << endl << endl; }
源码库中的位图:
在源码库中,有这样一个容器 bitset,和我们这里的bitmap性质基本是一样的,当然,功能要比上面实现的位图大得多。
A bitset is a special container class that is
designed to store bits (elements with only two possible values: 0 or 1,
true or false, ...).
The class is very similar to a
regular array, but optimizing for space allocation: each element occupies only
one bit (which is eight times less than the smallest elemental type in C++:
char).
Each element (each bit) can be accessed individually: for
example, for a given bitset named mybitset, the expression
mybitset[3] accesses its fourth bit, just like a regular array accesses
its elements.
Because no such small elemental type exists in most C++
environments, the individual elements are accessed as special references which
mimic bool elements:
库中提供了一系列的函数操作,除了set、reset、test之外,常用的还有filp<取反操作>,count<统计位为1的个数>。关于bitset的操作,都包含在
#include
的头文件中。
位图的分析与扩展:
位图的确用起来会很方便,但并不是任何情况下都需要使用到位图的,位图通常是为了处理大量数据,内存中不足以存放所有的数字才使用的一种数据结构,因为位图也有着一定的缺陷:
1> 它的可读性差
2> 位图在视图节约空间的时候,也伴随着一定的消耗,它要求给最大值和最小值之间的所有数都要占用一个bit位,当数据过于分散而数据量又不至太大的情况,位图其实是一种比较浪费空间的做法。如果最小值为10000,位图开辟出来的前10000个bit位其实就空了出来,没有利用到,之前我们举得例子,40亿个整数,因为无符号整数的最大值就到42.9亿左右,大部分的整数值确定都已经被取到,因此我们采用了位图来实现。
3> 当位图用来存储有符号整数时,有两种解决方案,一种是我们约定好最小值不再从0开始,所有的计算都需要减去有符号整数的最大值,另一种是这里采用两位来存储一个数,用两位来表示正数、负数、不存在三种状态。
试想,如果我们要求统计40亿个无符号整数中,出现两次以上的数该如何处理?
。。。。。。
同样,多加一位标志位,用两个bit位来进行处理,那这样的话,就需要我们自己来实现一个基本的两位为一个单元的位图结构。
除此之外,位图还可用来排序,判重,当然这里仅仅限于无符号整数,和上一节的哈希一样,受限于整数范围确实是个不好的地方,下一谈会提到字符串哈希算法与布隆过滤器,正是由于字符串哈希算法,才使得这些数据结构得以大范围的使用。
关于哈希算法: http://muhuizz.blog.51cto.com/11321490/1870717
-----muhuizz整理
本文名称:海量数据处理第二谈-----位图BitMap
转载来源:http://scyanting.com/article/ghopcc.html