建设凡科网站,丰台建设公司网站,哪里有网站制作价格,广州网站推广对于海量数据这个词#xff0c;大家不难理解吧。主要是针对给定的数据量特别大#xff0c;占用内存特别大的情况。那么和位图有什么关系呢。看下面一个腾讯的海量数据的例子吧。
例#xff1a;给40亿个不重复的无符号整数#xff0c;没排过序。给一个无符号整数#xff0…对于海量数据这个词大家不难理解吧。主要是针对给定的数据量特别大占用内存特别大的情况。那么和位图有什么关系呢。看下面一个腾讯的海量数据的例子吧。
例给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中。 对于这道题我们给了40亿个不重复的无符号整数一个整数是4个字节那么就是40*4160亿个字节大概是16G的内存。显然在内存上时存不下的。那么我们怎么来查找呢。既然是不重复就说明整数要么就不出现要么就出现一次。整数的最大值是42亿多即2^32。此时我们就可以用每一位来表示这个数存在或者不存在。如果将32位为一个编号时原本16G的数据使用位图可以节省到500M的空间。大概我们刚刚学过哈希表用访问地址的方法来快速的查找出地址对应的值。这里也一样用到了哈希表中的新的解决海量数据的方法---位图。
那么问题来了什么是位图呢
我们用每一位标志这个数存在的状态设为0不存在和1存在 位图的基本结构
是一个size_t类型的vector数组
vectorsize_t _array; 位图的基本函数 对于判断一个无符号整数是否存在这40亿个数中。
1需要存入这40亿个数使用Set将对应的40亿个位置为1
2使用Test将判断某个位是否为0或1
注位图只是考虑了整数类型
位图的实现代码vs2013 #pragma once
#includeiostream
using namespace std;
#includevector//位图的每一位的0,1标志这个数存在或不存在的状态
class BitMap
{
public:BitMap(size_t Size 1024){_array.resize(Size/321);}~BitMap(){}public://将这个数存在的状态置为1void Set(const size_t value){size_t index value5;size_t bit value % 32;_array[index] | (1bit);}//将这个数不存在的状态置为0void Reset(const size_t value){size_t index value5;size_t bit value % 32;_array[index] (~(1bit));}//测试某个数是否出现过bool Test(const size_t value){size_t index value5;size_t bit value % 32;return (_array[index] (1bit));}
private:vectorsize_t _array;
};void BitMapTest()
{BitMap bm(size_t(-1)); //64位系统下表示的整数的最大值bm.Set(10);bm.Set(100);bm.Set(20);bm.Set(500);coutbm.Test(10)endl;coutbm.Test(200)endl;coutbm.Test(500)endl;coutbm.Test(40)endl;
}运行结果
