当前位置: 首页 > >

【位图】位图实现,处理大数据

发布时间:

定义

位图法就是bitmap的缩写。所谓bitmap,就是用每一位来存放某种状态,适用于大规模数据,但数据状态又不是很多的情况。


通常是用来判断某个数据存不存在的。


例如,要判断一千万个人的状态,每个人只有两种状态:男人,女人,可以用0,1表示。那么就可以开一个int数组,一个int有32个位,就可以表示32个人。操作的时候可以使用位操作。


位图实现

unsigned int bit[N];

在这个数组里面,可以存储 N * sizeof(int) * 8个数据,但是最大的数只能是N * sizeof(int) * 8 - 1。假如,我们要存储的数据范围为0-15,则我们只需要使得N=1,这样就可以把数据存进去。如下图:



数据为【5,1,7,15,0,4,6,10】,则存入这个结构中的情况为:



代码实现

C++STL中给出bitmap类,提供了很多方法
http://www.cplusplus.com/reference/bitset/bitset/


class BitMap
{
public:
BitMap()
{}
BitMap(size_t size)
{
//1一个字节8个bit,int4个字节,32个bit
//所以_table中1一个元素可以表示32个数据
_table.resize((size >> 5) + 1);
}
//置1
void Set(int data)
{
//ByteNO是表示在table数组中那个元素
size_t ByteNo = data >> 5; //相当于除以32
//bitNo是表示在int字节32位bit中那个bit位。
size_t BitNo = data % 32;
_table[ByteNo] |= (1 << BitNo); //置1
}
//置0
void ReSet(int data)
{
size_t ByteNo = data >> 5; //相当于除以32
size_t BitNo = data % 32;
_table[ByteNo] &= ~(1 << BitNo); //置0
}
//判断是否存在
bool Test(int data)
{
size_t ByteNo = data >> 5; //相当于除以32
size_t BitNo = data % 32;
if (_table[ByteNo] & (1 << BitNo))
return true;
return false;
}
private:
vector _table;
};

位图缺点
可读性差位图存储的元素个数虽然比一般做法多,但是存储的元素大小受限于存储空间的大小。位图存储性质:存储的元素个数等于元素的最大值。比如, 1K 字节内存,能存储 8K 个值大小上限为 8K 的元素。(元素值上限为 8K ,这个局限性很大!)比如,要存储值为 65535 的数,就必须要 65535/8=8K 字节的内存。要就导致了位图法根本不适合存 unsigned int 类型的数(大约需要 2^32/8=5 亿字节的内存)。位图对有符号类型数据的存储,需要 2 位来表示一个有符号元素。这会让位图能存储的元素个数,元素值大小上限减半。 比如 8K 字节内存空间存储 short 类型数据只能存 8K*4=32K 个,元素值大小范围为 -32K~32K
位图应用

1、给定100亿个整数,设计算法找到只出现一次的整数 。


解决方法


将100亿个数分拆成1000份文件,再将每份文件里使用位图,并用两位bit表示数字出现的次数,00存出现0次的数,01存放出现1次的数,10存放出现多次的数,11舍弃,再将1000份中出现一次的数全部合并到一个文件里存放即可。


2、给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集


解决方法


将第一个文件里的数用哈希映射到1000个文件中,将第二个文件用同样的哈希映射到另1000个文件中,然后比较每个哈希映射相同的文件即


3、1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数


解决方法:其实和问题1是一样的


将100亿个数分拆成1000份文件,再将每份文件里使用位图,并用两位bit表示数字出现的次数,00存出现0次的数,01存放出现1次的数,10存放出现2次的数,11舍弃,再将1000份中出现次数不超过二的数全部合并到一个文件里存放即可


4、给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中


可以考虑使用位图bitmap,1个bit存储一个数字,那么40亿数据需要40亿bit 大约就是500M内存。
1M=1024*1024 * 8bit 大概8千万


用一个bit位来表示这个数据是否存在,1表示存在,0表示不存在。


5、使用位图法进行整形数组排序


首先遍历数组,得到数组的最大最小值,然后根据这个最大最小值来缩小bitmap的范围。这里需要注意对于int的负数,都要转化为unsigned int来处理,而且取位的时候,数字要减去最小值。



友情链接: