广州敏城建设工程有限公司网站,北京房产网二手房源,医院网站队伍建设,wordpress图文并排位图
位图的概念
所谓位图#xff0c;就是用每一位来存放某种状态#xff0c;适用于海量数据#xff0c;数据无重复的场景。通常是用来判断某个数据存不存在的。
直接来看问题#xff1a; 给40亿个不重复的无符号整数#xff0c;没排过序。给一个无符号整数#xff0…位图
位图的概念
所谓位图就是用每一位来存放某种状态适用于海量数据数据无重复的场景。通常是用来判断某个数据存不存在的。
直接来看问题 给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在 这40亿个数中。 思路解决问题的方法可以使用位图来解决。把这40亿个数据映射在位图上将位图上对应的比特位置为1。然后拿着需要判断的数在位图上看看其对应的比特位是否为1如果是则存在否则为0。
具体做法
使用直接定址法这40亿个数据的值是几就把第几个比特位标记为1。因为40亿个整数大概需要16G内存而使用比特位我们只需使用char作为存储在vector上的类型每一个都是1bit大因此在vector上开辟2^32大小的空间表示数据大小范围一共512M。 开辟好空间后开始将每一个数据映射到位图上。每一个char对象为8bit于是让每一个值先确定自己在哪个char对象上然后确定映射在哪个比特位上。 x映射的值在第 x/8 个char对象上。 x映射的值在第 x%8 个比特位上。 所以我们可以根据上面的理论用代码简单实现位图
使用非模板参数N作为数据的个数。
开辟空间空间开辟的大小为N /8 1因为N个数据每8个为一组多开辟一组避免N不是8的整除。然后初始化为0。即位图上的比特位一开始全是0. //初始化空间初始值为0bitset(){_bits.resize((N 3) 1, 0);}
数据映射位图上的比特位先计算好数据所在的组别和比特位的位置然后将其置为1。置为1的操作是让这一个char对象组别的比特位与这个数据的比特位进行或运算。 void set(size_t x){size_t i x 3;//位于哪一个char对象上size_t j x % 8;//位于这个char对象上的哪个比特位上_bits[i] | (1 j);//通过或运算将x对应的比特位变为1}
将某个数据映射的比特位从1变回0同样的找到这个位置后然后这一组别的比特位与这个数据的比特取反后进行与运算。 void reset(size_t x){size_t i x 3;size_t j x % 8;_bits[i] (~(1 j));//通过与运算让x对应的比特位变为0}
判断一共数据是是否存在同样先计算出这个数据映射的位置。然后返回这一组别跟这个数据的比特然后进行与运算注意不是与等是不能改变原本位图的比特位的。 //判断x是否存在如果存在返回truebool test(size_t x){size_t i x 3;size_t j x % 8;return _bits[i] (1 j);}
完整代码如下
namespace my_BitSet
{templatesize_t Nclass bitset{public://初始化空间初始值为0bitset(){_bits.resize((N 3) 1, 0);}void set(size_t x){size_t i x 3;//位于哪一个char对象上size_t j x % 8;//位于这个char对象上的哪个比特位上_bits[i] | (1 j);//通过或运算将x对应的比特位变为1}void reset(size_t x){size_t i x 3;size_t j x % 8;_bits[i] (~(1 j));//通过与运算让x对应的比特位变为0}//判断x是否存在如果存在返回truebool test(size_t x){size_t i x 3;size_t j x % 8;return _bits[i] (1 j);}private:vectorchar _bits;};
}
布隆过滤器
位图对于判断大量数据中是否存在某一个数据的情况固然是好其优点是节省空间和判断速度块。但其缺点是一般要求范围相对集中如果范围特别分散那么空间消耗就大了而且是只针对整型。因此布隆过滤器降临
布隆过滤器的概念
布隆过滤器是一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询可以用来告诉你 “某样东西一定不存在或者可能存在”它是用多个哈希函数将一个数据映射到位图结构中因为布隆过滤器是哈希位图的结合。此种方式不仅可以提升查询效率也可以节省大量的内存空间。
一般的位图下每一个数据只跟位图产生一个映射点而且只能用于整型。但布隆过滤器是每一个数据可以有N个映射点N个映射点对应于N个哈希函数这个是我们自己定义的。用哈希函数将非整型转化成整型。 布隆过滤器的长度的计算方式
使用公式 K为哈希函数的个数m为布隆过滤器长度n为数据的个数。假设K为3而ln2约等于0.7因此m4.2n。
布隆过滤器的功能支持
布隆过滤器支持set和test方法最好不要有将1变回0的操作。因为这样会导致其它数据的判断的误差。如果真的要支持就用计数的方法但这种方法不推荐。
简单实现代码如下
这里使用3个哈希函数分别为BKDRHash、APHash和DJBHash。使用string为类型。
set方法 void set(const K key){//通过不同的哈希函数让同一个数据可以计算出三个不同的位置size_t hash1 HashFunc1()(key) % (N * X);size_t hash2 HashFunc2()(key) % (N * X);size_t hash3 HashFunc3()(key) % (N * X);//计算出位置后使用位图的set方法将位图上对应的比特位进行0变1_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}
test方法 bool test(cost K key){//先逐个位置判断如果它是0直接返回falsesize_t hash1 HashFunc1()(key) % (N * X);if (!_bs.test(hash1)){return false;}size_t hash2 HashFunc2()(key) % (N * X);if (!_bs.test(hash2)){return false;}size_t hash3 HashFunc3()(key) % (N * X);if (!_bs.test(hash3)){return false;}//直到最后说明该数据是存在的返回truereturn true;}
整体代码如下
namespace my_BloomFilter
{struct BKDRHash{size_t operator()(const string key){size_t hash 0;for (auto ch : key){hash * 131;hash ch;}return hash;}};struct APHash{size_t operator()(const string key){unsigned int hash 0;int i 0;for (auto ch : key){if ((i 1) 0){hash ^ ((hash 7) ^ (ch) ^ (hash 3));}else{hash ^ (~((hash 11) ^ (ch) ^ (hash 5)));}i;}return hash;}};struct DJBHash{size_t operator()(const string key){unsigned int hash 5381;for (auto ch : key){hash (hash 5) ch;}return hash;}};templatesize_t N,size_t X 5,class K string,class HashFunc1 BKDRHash,class HashFunc2 APHash,class HashFunc3 DJBHashclass BloomFilter{public:void set(const K key){//通过不同的哈希函数让同一个数据可以计算出三个不同的位置size_t hash1 HashFunc1()(key) % (N * X);size_t hash2 HashFunc2()(key) % (N * X);size_t hash3 HashFunc3()(key) % (N * X);//计算出位置后使用位图的set方法将位图上对应的比特位进行0变1_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}bool test(cost K key){//先逐个位置判断如果它是0直接返回falsesize_t hash1 HashFunc1()(key) % (N * X);if (!_bs.test(hash1)){return false;}size_t hash2 HashFunc2()(key) % (N * X);if (!_bs.test(hash2)){return false;}size_t hash3 HashFunc3()(key) % (N * X);if (!_bs.test(hash3)){return false;}//直到最后说明该数据是存在的返回truereturn true;}private:std::bitsetN* X _bs;};
}海量数据处理问题
哈希切割 给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址 超过100G大小的文件肯定不能直接放到内存中而是通过将它切割分成很多份。那么如何去切割呢是平均分成100份每一份1G这样吗
如果平均切割那么会导致的问题是如果文件中有好几个相同的值且分布不集中此时平均切割就很可能使一个IP有很多份在很多小文件中。
因此不能平均切割需要的是哈希切割。哈希切割就是通过取模让取模结果相同的数据放到同一份小文件里面。
哈希切割后通过map来对每一个小文件进行统计。 小问题如果超过1G的问题 ①不重复的IP有很多个map就需要很多节点因此map是统计不下来的。 ②重复的IP有很多个map可以统计下来因为节点不多。 解决方法 先不看什么情况直接用map统计如果是第二种情况的话就直接统计下来了。但是第一种情况会在insert的时候失败因此可以在失败的时候捕捉异常接着换哈希函数递归切分再统计即可。 位图的应用 1.给定100亿个整数设计算法找到只出现一次的整数 只出现一次那就说明它在位图中比特位是01。如果找到该位置发现是00或11或者其它的情况那就不是。
但一个一般的位图只会出现单个比特即要么是0要么是1不会出现两个比特。这里的方法使用两个位图的结构。即定义两个位图然后用同一个数据计算出来的同一个位置分别在这个两个位图上进行0和1的操作。 简单的代码实现 templatesize_t Nclass twobitset{public:void set(size_t x){//初次映射两个位图对应的比特位都为0即00if (!_bs1.test(x) !_bs2.test(x)// 00{_bs2.set(x);// 01}else if (!_bs1.test(x) _bs2.test(x) // 01{//第二次遇到这个数字后此时是01的要变成10_bs1.set(x); //11_bs2.reset(x); // 10}//如果第三次遇到也不用管了第二次遇到的时候就已经不是它了//10//11}void PrintOnce(){for (size_t i 0; i N; i){if (!_bs1.test(i) _bs2.test(i)) // 01 出现一次{cout i endl;}}cout endl;}private:bitsetN _bs1;bitsetN _bs2;};
} 2.给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集 这里提供两种思路
思路1先将一个文件的数据映射到位图中然后用另外一个文件的数据去遍历得到交集需要注意去重。
思路2分布将两文件映射到两个位图然后通过两位图的与运算判断是否有交集。 3.位图应用变形1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整数。 这道问题跟第一个问题基本一样就是让“01”和10为需要找到的整数。如果出现11以上那么就不行。
布隆过滤器的应用 1. 给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法和近似算法。 query是一般为一个查询指令可能是一个网络请求的指令也可能是一个数据库sql语句。
精确算法找文件交集的思路是分别给两个文件创建布隆过滤器然后让它们进行哈希切割分成一个个小文件。最后通过编号相同的小文件中查找交集。
近似算法的思路是将一个文件的数据映射到一个布隆过滤器中然后另外一个文件去查找有没有相同的有就是交集。这种算法会造成误判。
