旅游网站制作教程,wordpress简介怎么改,专业建站外包,wordpress版权图片本期我们来学习位图#xff0c;布隆过滤器等相关知识#xff0c;以及模拟实现#xff0c;需求前置知识 C-哈希Hash-CSDN博客 C-封装unordered_KLZUQ的博客-CSDN博客 目录
位图
布隆过滤器
海量数据面试题
全部代码 位图
我们先来看一道面试题 给 40 亿个不重复的无符号…本期我们来学习位图布隆过滤器等相关知识以及模拟实现需求前置知识 C-哈希Hash-CSDN博客 C-封装unordered_KLZUQ的博客-CSDN博客 目录
位图
布隆过滤器
海量数据面试题
全部代码 位图
我们先来看一道面试题 给 40 亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在 这 40 亿个数中。【腾讯】 这是一个查找在不在的问题我们该如何解决呢使用set可以吗排序二分查找可以吗
如果但从效率来看它们都是longN但是都不行40亿整数是160亿字节换算下来大约是16G左右内存是不会给我们开16G的如果用set更恐怖除了存整形还要存各种附带的东西leftrightparent颜色等等红黑树哈希表这些都是有附带消耗的
这是一个在不在的问题所以我们可以用0和1来表示存在所以这里可以用比特位来标记我们开2^32个比特位进行标记这里和哈希的直接定址法一样我们这里是开范围而且2^32比特位是0.5G左右 此时我们来写需要的结构我们用vector来实现但是此时又有一个问题什么类型的大小是一个比特位没有但是我们仔细回忆的话位运算和位段都是可以实现一个比特位的 我们这里要实现两个接口一个set一个reset分别是将x映射的位置标记为1和0 一个int是32个比特位假设此时x80我们首先要计算出x在第几个整形的位置我们用x/32即可在该整形的第几个位上面我们可以用x%32我们带入计算一下80/32是2刚好在第二个整形从第0个开始再用80%32是166416是80所以位置刚好是下标
这里还有一个问题我们的机器其实是小端机 也就是说在内存中其实是这样的 比如我们这里存了一个1在内存中的存储就是这样的 //x映射的位置标记位1void set(size_t x){size_t i x / 32;size_t j x % 32;_a[i] | (1j);}//x映射的位置标记位0void reset(size_t x){size_t i x / 32;size_t j x % 32;_a[i] (~(1 j));}
我们实现这两个函数使用位运算就可以巧妙的解决问题
set我们让它的那个位置 | 上1reset我们让那个位置上~1这里1用来移位所以没有0
接下来我们要判断某个位置是0还是1 bool test(size_t x){size_t i x / 32;size_t j x % 32;return _a[i] (1 j);}
我们1即可如果是0返回则为假是1返回真注意这里是不是 我们再加上构造函数开一下空间这里向上取整 接着我们测试一下没有问题 下面我们要来完成面试题首先我们要开42亿的空间不是40亿题目说的是40亿个不重复有可能比40亿大
我们在这里写INT_MAX可以吗不行INT_MAX是21亿多 我们应该用这个无符号的最大值 或者用更简单的办法写个-1即可因为这里是无符号-1的补码是全1 手动写16进制也可以 另外位图在库里面也是有的 有各种接口我们记住testset和reset即可其他的基本用不到
我们来看一些位图的应用 1. 给定 100 亿个整数设计算法找到只出现一次的整数 2. 给两个文件分别有 100 亿个整数我们只有 1G 内存如何找到两个文件交集 3. 位图应用变形 1 个文件有 100 亿个 int 1G 内存设计算法找到出现次数不超过 2 次的所有整数 我们看第一个100亿个整数只出现一次
我们之前用1个位标记在不在现在我们可以用2个位来表示状态2个位可以表示出4种状态我们用3种即可00表示不在01表示出现一次10出现2次及以上我们把位图改造一下即可解决
还有更省力的方法我们用bitset来完成 开两个位图第一个的第一位和第二个的第一位结合起来就是一个数的状态依次类推 为了方便我们先把之前的myset改名和库里面一样的bitset
templatesize_t Nclass twobitset{public:void set(size_t x){//00 - 01if (!_bs1.test(x) !_bs2.test(x)){_bs2.set(x);}//01 - 10else if(!_bs1.test(x) _bs2.test(x)){_bs1.set(x);_bs2.reset(x);}// 本身是10代表出现2次及以上就不变}bool is_once(size_t x){return !_bs1.test(x) _bs2.test(x);}private:bitsetN _bs1;bitsetN _bs2;};
我们实现一个towbitset实现一个set接口对于出现的数字如果00就变为0101就变为1010不用变然后提供一个isonce判断出现一次的数 我们简单测试一下没有问题
下面再看第二个问题找两个文件的交集 我们把一个文件的所有值映射到位图然后另一个文件来判断在不在可以吗
可以但是会有一些问题比如第一个文件里有一个3第二个文件里有3个3那么这里得到的结果也是3个3是需要进行去重的
我们来看更好的方法 我们把两个文件分别映射到两个位图存在为1不存在为0然后对应的位置一下即可或者对应位置都为1的就是交集 比如这样写
我们再看第三个问题 不超过2次就是1次和2次我们还是用2个位来表示00表示0次01表示1次10表示2次11表示2次以上解决思路类似问题1
布隆过滤器
刚才的问题都是数字如果是string呢比如文件1和文件2找交集里面都是字符串比如“语文“”数学“”英语“这些 我们把这些字符串计算成对应成整形映射到位图里然后按刚才的思路走就行了不过这样写会有一些问题就是冲突比如还有一个字符串”物理“它和语文计算出的整形是一样的映射到了同一个位置是会受到影响的就存在误判了
那有什么办法可以解决这个问题吗
答案是不能冲突是无法避免的但是我们可以减少冲突 布隆过滤器是 由布隆 Burton Howard Bloom 在 1970 年提出的 一种紧凑型的、比较巧妙的 概 率型数据结构 特点是 高效地插入和查询可以用来告诉你 “ 某样东西一定不存在或者可能存 在 ” 它是用多个哈希函数将一个数据映射到位图结构中。此种方式 不仅可以提升查询效率也 可以节省大量的内存空间 。 举个例子你要和一个网友去面基网友告诉你当天他穿的黑色裤子背着白色的书包在见面地点你一定不会认错吗不一定虽然提供了两个信息但是还是会有冲突所以我们只能提供更多的信息来降低冲突但是不管提供多少信息在人足够多的情况下还是可能认错
再回到我们的字符串我们可以给一个字符串映射3个位置虽然还可能会有认错但是几率会低很多 而且它们之间可能会有交叉 我们新添加一个物理甚至可能会有两个位置和前面的元素冲突但是只要不全冲突就行容错率是大大提升的
应用场景
不需要精确的场景比如快速判断昵称是否注册过我们就可以把所有昵称放到数据库里我们可以接受百分之3到5的误判率比如一个昵称没有被使用但是却显示被使用了对于用户来说其实是没什么问题的换一个即可
假设我们需要精确不容忍误判我们可以这样玩输入的不存在就返回不存在如果显示在我们就去数据库再查一遍以数据库的结果返回这样可以减少不在的那些昵称要去查找的损耗这里就是过滤器的作用过滤掉了一些降低数据库的负载压力提高效率为什么不全去数据库找因为太慢了这也是为什么他叫过滤器的原因
下面我们来对字符串实现过滤器我们前面使用了字符串哈希算法这里就需要用到它了但是这里还有一个问题会存在双重冲突的问题
第一个是两个字符串不同的但转出来的整形是相同的第二个是用除留余数法映射后可能回到相同的位置
基于这两个问题布隆就想到了映射多个位置所以就有了布隆过滤器
//BloomFilter.h
struct BKDRHash
{size_t operator()(const string str){register size_t hash 0;for (auto ch : str){hash hash * 131 ch;}return hash;}
};struct APHash
{size_t operator()(const string str){register size_t hash 0;size_t ch;for (size_t i 0; i str.size(); i){size_t ch str[i];if ((i 1) 0){hash ^ ((hash 7) ^ ch ^ (hash 3));}else{hash ^ (~((hash 11) ^ ch ^ (hash 5)));}}return hash;}};struct DJBHash
{size_t operator()(const string str){register size_t hash 5381;for (auto ch : str){hash (hash 5) ch;}return hash;}
};templatesize_t N,class K string,class Hash1 BKDRHash,class Hash2 APHash,class Hash3 DJBHash
class BloomFilter
{
public:void Set(const K key){size_t hash1 Hash1()(key) % N;_bs.set(hash1);size_t hash2 Hash2()(key) % N;_bs.set(hash2);size_t hash3 Hash3()(key) % N;_bs.set(hash3);}bool Test(const K key){size_t hash1 Hash1()(key) % N;if (_bs.test(hash1) false)return false;size_t hash2 Hash2()(key) % N;if (_bs.test(hash2) false)return false;size_t hash3 Hash3()(key) % N;if (_bs.test(hash3) false)return false;return true;//存在误判}
private:bitsetN _bs;
};
布隆过滤器实现起来就很简单了我们借助库里面的bitset和三个字符串哈希算法来实现然后我们将字符串哈希算法改为仿函数我们只需要实现Set和Test即可 我们简单测试一下没有问题 我们还可以把hash123打印出来看一看 这里还是有一个冲突的猪八戒的两个25 如果数据足够多空间小的话冲突的概率就会很大这里沙悟净就出现了误判
另外大家可以发现我们这里是没有实现reset的是不能实现的举个例子如果我们把上面的猪八戒reset了5和6都会受影响进而导致孙悟空和二郎神他们都会受影响就不见了所以一般不支持删除删除一个值可能会影响其他值
如果想要强行支持删除那要付出很大的代价比如可以使用多个位标识一个值使用引用计数
这里提供一篇知乎大佬写的布隆过滤器详解 详解布隆过滤器的原理使用场景和注意事项 - 知乎 (zhihu.com) 建议大家看一看 下面我们来测试一下我们set大量的值然后再给其他大量的值这些值里有一部分在过滤器里一部分不在我们来看看不在过滤器里的值会不会出现误判也就是原本不在过滤器里的值显示出在
void TestBloomFilter2()
{srand(time(0));const size_t N 100000;BloomFilterN * 4 bf;std::vectorstd::string v1;//std::string url https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html;std::string url 猪八戒;for (size_t i 0; i N; i){v1.push_back(url std::to_string(i));}for (auto str : v1){bf.Set(str);}// v2跟v1是相似字符串集前缀一样但是不一样std::vectorstd::string v2;for (size_t i 0; i N; i){std::string urlstr url;urlstr std::to_string(9999999 i);v2.push_back(urlstr);}size_t n2 0;for (auto str : v2){if (bf.Test(str)) // 误判{n2;}}cout 相似字符串误判率: (double)n2 / (double)N endl;// 不相似字符串集std::vectorstd::string v3;for (size_t i 0; i N; i){//string url zhihu.com;string url 孙悟空;url std::to_string(i rand());v3.push_back(url);}size_t n3 0;for (auto str : v3){if (bf.Test(str)){n3;}}cout 不相似字符串误判率: (double)n3 / (double)N endl;
}
我们来看一看 根据上面的测试结果来看只要你舍得开空间误判率是可以降低很多的另外数据样本也是会有影响的我们用了猪八戒这个字符串来测试如果用上面很长的网址又是另一个结果不过差别不会太大而且只要我们把空间变大误判率就会下降一般推荐5到10倍左右
海量数据面试题 哈希切割 给一个超过 100G 大小的 log file, log 中存着 IP 地址 , 设计算法找到出现次数最多的 IP 地址 与上题条件相同如何找到 top K 的 IP 如何直接用 Linux 系统命令实现 位图应用 1. 给定 100 亿个整数设计算法找到只出现一次的整数 2. 给两个文件分别有 100 亿个整数我们只有 1G 内存如何找到两个文件交集 3. 位图应用变形 1 个文件有 100 亿个 int 1G 内存设计算法找到出现次数不超过 2 次的所有整数 布隆过滤器 1. 给两个文件分别有 100 亿个 query 我们只有 1G 内存如何找到两个文件交集分别给出 精确算法和近似算法 2. 如何扩展 BloomFilter 使得它支持删除元素的操作 这些题我们讲过了部分我们来看过滤器的1要求给出精确算法这里就需要用到哈希切分
假设平均一个query查询是30byte100亿是3000亿字节1G大约是10亿字节也就是说一共是300G左右而且还是两个这样的文件现在我们只有1G内存
我们可以把文件切成一个一个的小文件但是切成小文件后交集该怎么找呢一个一个的再去组合测试吗这样太慢了
我们可以用哈希切分比如我们把文件切成1000分但不是平均切分i Hash(query) % 1000
i是多少query就进入第i个小文件两个文件都用这样的方式来处理 画出来大概就是这样此时我们只需要对应编号的找即可比如A0和B0找A1和B1找即可
哈希切分的效果是A和B中相同的query一定会分别进入Ai和Bi编号相同的小文件比如一个query在文件A里经过hash然后%1000得到了500那么如果B里面也有这个query它也会经过一样的步骤所以得到的i是相同的进入小文件的编号也就是一样的这里有点像哈希桶同一个桶里就是冲突的但是也有不冲突的大多数的这种问题都是可以用哈希切分来解决
这里其实还有一个问题没有解决找交集是从Ai中读出来然后放到set里再从Bi中读取query看在不在set如果在就是交集就是可以找到Ai和Bi的交集这里的切分如果是平均切分就是一个文件300M但我们是哈希切分如果冲突太多会导致某个Ai文件过大甚至超过1G别忘了set也要消耗内存那该怎么办
这里会有两个场景比如Ai有5G场景14G都是相同1G是冲突场景2大多数是冲突
这里场景2我们可以换个哈希函数再次切分一直切是可以解决的但是场景1不可以相同的是切不开的并且我们是无法区别到底是场景1还是场景2的
解决方案1.先把Ai的query读到一个set如果set的insert报错抛异常bad_alloc那么就说明大多数query是冲突如果能全部读出来insert到set里面那么说明Ai中有大量相同的queryset自己可以去重
2.如果抛异常说明有大量冲突我们换一个哈希函数进行二次切分
我们再看下一个问题 这道题还可以扩展成出现次数最多的K个ip地址
同样的我们还是使用哈希切分比如我们切成300份i Hash(query) % 300
相同的ip一定会进入同一个小文件之后我们用map分别统计每个小文件中ip出现的次数即可出现次数最多的K个我们建小堆即可
全部代码
#pragma once
#includevector
using namespace std;
//bitset.h
namespace bai
{templatesize_t Nclass bitset{public:bitset(){size_t num N / 32 1;_a.resize(num);}//x映射的位置标记位1void set(size_t x){size_t i x / 32;size_t j x % 32;_a[i] | (1j);}//x映射的位置标记位0void reset(size_t x){size_t i x / 32;size_t j x % 32;_a[i] (~(1 j));}bool test(size_t x){size_t i x / 32;size_t j x % 32;return _a[i] (1 j);}private:vectorint _a;};templatesize_t Nclass twobitset{public:void set(size_t x){//00 - 01if (!_bs1.test(x) !_bs2.test(x)){_bs2.set(x);}//01 - 10else if(!_bs1.test(x) _bs2.test(x)){_bs1.set(x);_bs2.reset(x);}// 本身是10代表出现2次及以上就不变}bool is_once(size_t x){return !_bs1.test(x) _bs2.test(x);}private:bitsetN _bs1;bitsetN _bs2;};
}
#pragma once
#includevector
#includeiostream
#includebitset
#includestring
using namespace std;//BloomFilter.h
struct BKDRHash
{size_t operator()(const string str){register size_t hash 0;for (auto ch : str){hash hash * 131 ch;}return hash;}
};struct APHash
{size_t operator()(const string str){register size_t hash 0;size_t ch;for (size_t i 0; i str.size(); i){size_t ch str[i];if ((i 1) 0){hash ^ ((hash 7) ^ ch ^ (hash 3));}else{hash ^ (~((hash 11) ^ ch ^ (hash 5)));}}return hash;}};struct DJBHash
{size_t operator()(const string str){register size_t hash 5381;for (auto ch : str){hash (hash 5) ch;}return hash;}
};templatesize_t N,class K string,class Hash1 BKDRHash,class Hash2 APHash,class Hash3 DJBHash
class BloomFilter
{
public:void Set(const K key){size_t hash1 Hash1()(key) % N;_bs.set(hash1);size_t hash2 Hash2()(key) % N;_bs.set(hash2);size_t hash3 Hash3()(key) % N;_bs.set(hash3);}bool Test(const K key){size_t hash1 Hash1()(key) % N;if (_bs.test(hash1) false)return false;size_t hash2 Hash2()(key) % N;if (_bs.test(hash2) false)return false;size_t hash3 Hash3()(key) % N;if (_bs.test(hash3) false)return false;return true;//存在误判}
private:bitsetN _bs;
};
以上即为本期全部内容希望大家可以有所收获
如有错误还请指正
