网站未备案做经营被罚款,孝感的网站建设,全网推广平台有哪些,九一人才网赣州前言
之前介绍了 位图#xff0c;位图在判断某一个 数是否存在#xff0c;或者在计算某个数是否出现 一次 或者 两次这些问题之上有着非常高效的实现复杂度#xff0c;它的时间复杂度 可以达到 O#xff08;1#xff09;#xff0c;因为都是逻辑判断和 #xff0c;常数… 前言
之前介绍了 位图位图在判断某一个 数是否存在或者在计算某个数是否出现 一次 或者 两次这些问题之上有着非常高效的实现复杂度它的时间复杂度 可以达到 O1因为都是逻辑判断和 常数次计算。具体请看博客C - 位图 - bitset 容器介绍_chihiro1122的博客-CSDN博客
但是位图的局限性也很高对于 int size_t 这些类型可以直接映射比特位的下标来看这个比特位的值是 1 还是 0 但是 如果是 string 这种自定义类型就会出现问题。
比如string类我们可以按照hash 当中对 string值 计算出的 hash 值来在位图当中进行 映射但是string 在计算哈希值的时候它不想 int 类型是多少就是多少一个 string 类 映射出的 hash 值可能有多个 string 类都会使用这个值具体的实现逻辑可以看看下面博客当中对 闭散列开放式地址法哈希表当中对 仿函数的书写C - 开放地址法的哈希介绍 - 哈希表的仿函数例子_chihiro1122的博客-CSDN博客
当某一个 string计算出的 hash 值和 另一个 string计算出的hash值相同那么我们在利用这个hash 值寻找 某个 string的时候就会出现误判比如我想找第一个 string是否存在原本是不存在的但是第二个 string存在就把 位图当中 对应位置的 比特位 修改为 1 了那么在查找过程当中我就认为第一个 string是存在的但是实际上不存在。这就 造成了 结果的误判。
此时string 不在是准确的但是 在可能是误判的。 string 类计算出 hash 值有多种方式可以解决虽然都可以缓解冲突问题但是没有更本上解决 冲突问题最终还是会发生冲突所以位图是不能解决 string 类的。
这时有一个布隆的人就提出了布隆过滤器。
布隆过滤器
布隆这个人就想能不能降低 误判的概率。 举个例在线下和朋友面基的时候我们要在一个商场当中找到我们的朋友朋友跟你说它穿了白色的T恤黑色的牛仔裤那么商场当中人这么多穿同样衣服的人很有可能不止 朋友一个那么此时就会出现误判可能就会找错人。
那么 布隆就想能不能让朋友在给出关于自己更详细 的信息比如在给出 身高发型身材胖瘦那么我就可以再根据这些信息在筛选出一些人那么我 误判的概率就会有所降低。
这就是 布隆过滤器所实现的效果。
但是不管你提供的信息有多么详细极端情况下可能还是会有人和朋友的特征发生冲突让你找错人但是这种情况在信息详细的情况下很难发生所以给出详细的信息虽然不能彻底解决冲突的问题但是还是可以很大程度上的实现 降低误判的概率。 比如现在我们判断 四个 公司是否参加 某一个 活动那么我们对这四个公司的公司名是否存在在名单上进行判断而且我们不在使用 一个字符串映射一个位置的方式来计算了假设我们现在使用 三个位置来映射三个位置为1 才说明这个公司参加了这次活动其中有任何一个位置为 0 都没有参加 如上述所示除了华为之外其他的都参加了因为只有华为 有一个位置的映射是 0 我们发现虽然华为和腾讯 阿里 的 两个位置冲突了但是我们可以正确的判断华为是否参加了这场活动。
像上述就降低了 误判率但是没有彻底消除误判可能后面还会有公司和 华为的第三个映射位置冲突但是我们发现这种方式可能有效的 降低误判率而且向上述的方式一个 string 映射的位置越多那么误判率降低的也就越多。
此时 string类 不在是准确的在可能是误判的。 而且如果一个 string 占用的 映射位置变多了就会带来一个问题就是空间利用率降低了也就是说使用布隆过滤器的话如果降低误判率就会降低空间利用率反之。
布隆过滤器实现 布隆过滤器的实现直接利用位图作为底层然后在之上实现过滤条件即可。具体 位图的实现可以上篇文章C - 位图 - bitset 容器介绍_chihiro1122的博客-CSDN博客
或者使用库当中的 bitset 实现。 位图实现的代码
#pragma once
#includevectornamespace bit
{templatesize_t Nclass bitset{public:bitset(){_a.resize(N / 32 1);}// x映射的那个标记成1void set(size_t x){size_t i x / 32;size_t j x % 32;_a[i] | (1 j);}// 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;};
按照上述的说法一个 string 需要三个比特位来就映射当三个位置都是 1 才能说明这个string是存在的。
关于string计算hash 值有很多方法具体可以参考这篇文章各种字符串Hash函数 - clq - 博客园 (cnblogs.com) 那么关于一个 string 类型的三个映射位置我们把每一个映射位置都用不同的 hash 计算方式来映射当然三种映射方式都有可能冲突但是要三个位置都冲突的话这种可能性比较小。
当我们要“插入”一个 string时 就 计算三种映射方式计算出三个对应位置把这三个位置 set为1 即可。
判断是否存在的test函数只需要判断这个 string 用三个方法计算出的 三个位置是否都为 1是就存在不是就不存在。 在布隆过滤器当中我们不敢去支持 rset删除函数因为一个 string 是映射了三个位置的如果我们直接把这个三个比特位的值改为 0 的话那么 如果有其他的 string 某个位置映射到 这三个 位置的话也就是说冲突我们就会修改到 其他string 的映射位置那么这个 本来是存在但是在 rset另一个 string 之后这个 string 就不存在了这个问题很大。 而且我们很难确定一个 位置 映射了 那些字符串所以我们一般不支持删除函数。 如果想要支持的话那么上述的三个位置就不仅仅是一个 比特位了每一个位置要存储 这个位置映射了多少个 string当我们要 rset删除某一个 string的时候就把这个 string 映射的三个位置的计数--但是计数就带来一个新的问题如果单独是 2,3 个 比特位能存储的数字太有限了而平常情况下一个位置映射的string个数可能是 很多个 如果我们拿 8 个比特位来存储的话最大就可以存储 0 - 2 ^ 8 范围的数据但是 我们都用 位图来实现了本来就是想利用位图节省空间的优点那么我们在想上述来浪费空间的话就有点本末倒置了。 有人专门对 使用的不同哈希函数的个数误判率的影响可以看下面这个篇文章 详解布隆过滤器的原理使用场景和注意事项 - 知乎 (zhihu.com)
这是文章当中数据测试的折线截图 可以发现当 k 越大 也就是当使用的不同哈希函数越多那么左边的 误判率就越低。
m 是 位图的长度相对于 string 个数的比值也就是相当于是 一个 string 要 映射m个比特位。上图当中是控制了 m 不变按照每个 string 10个 比特位来映射的。
我们之前也分析过了m 越多误判率也就越低但是空间利用率也就越低。
那么我们该如何选择其中的 m 和 k 呢
在文章当中也描述了按照下述公式计算 总结下来大约 m n*4.3 是差不多和上述计算结果类似的。 布隆过滤器简单测试误判率 我们创建大量的字符串这些字符串基本都是不同的但是前缀有一部分是相同的但是后缀不是基本不同的然后我们来计算一下这些例子它的误判率有多少
void TestBloomFilter2()
{srand(time(0));const size_t N 100000;BloomFilterN*8 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;
} 布隆过滤器的应用场景 1.不需要精确判断的场景比如快速判断某一昵称是够被注册过。 像这种场景之下我们允许有很小的误判率比如 3% - 5%只需要用户输入的很大部分的用户名都能被正确的判断是否存在就行了至于出现的那一小部分错误用户也不知道不用太在意。之所以使用 布隆过滤器是因为他的底层实现逻辑还是 和 位图基本一致只不过多加上了过滤的逻辑所以在查找方面布隆过滤器还是和位图一样有着 非常高效的 常数级别的 时间复杂度在用户输出用户名的时候能很快的找出是否存在不用子数据库当中去查找虽然数据库的那种查找也非常的快但是肯定是没有布隆过滤器快的。
而且布隆过滤器在可能会有误判但是不在肯定是正确的所以不可能出现用户注册的用户名和 数据库当中的用户名注册重复情况。 2.在上述的场景下还是判断用户名但是需要精确和效率也就是说不能直接用数据库来进行查找因为数据库有点慢。
所以此时就需要用 布隆过滤器 和 数据库结合的方式来使用了
先用布隆过滤器查找一遍
如果不在因为不在是准确的所以可以直接 打勾√ 如果在因为在可能会误判所以还要在数据库当中查找一遍以数据库当中查找的结果返回给用户在数据库当中查找肯定是精准的 因为 布隆过滤器 查找的 时间复杂度是 O1所以在上述的第二种情况多判断的一次 布隆过滤器可能直接忽略不计。 这种方式就减轻了数据库查找的负载压力提升了效率。
哈希切分 我们先来看一个问题 1. 给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法 和 近似算法 近似算法的话看过前面的文章相信你已经猜到了就是使用布隆过滤器把 两个文件放到两个布隆过滤器当中然后进行取交集的操作取交集在 上一篇当中对位图的介绍当中已经进行说明两者之间是类似如有需要请看一下博客当中对位图应用的板块介绍C - 位图 - bitset 容器介绍_chihiro1122的博客-CSDN博客
我们主要来看 精确算法
query 是查询的意思一句 sql 语句可能就是 30 个 字节这里只是举一个例子那么按照一个 query 是 30 字节的话1G 是 2^30字节 大概是 10亿字节左右那么 100 亿字节就是 大概 300G 左右。为我们只要 1G 的内存所以 300 G 我们肯定是不可能完全存下的所以我们要切分出一个一个的小文件假设是 把 大文件 A 和 大文件 B 各自都切分成1000 个小文件对这些小文件按照 A 和 B 切分出的对应位置来进行一对一对的小文件进行比较得出结果。
当然对于小文件当中的数据 你可以按照哈希表的形式去处理但是哈希表肯定是带来多余的内存消耗的所以我们在这里不使用哈希表的方式来存储。
而且我们按照顺序来切分出 的小文件一个一个对比的话效率也是不高的。以为 A 文件 和B 文件当中 query 的存储顺序不一定是一样的我们可能不能再对应的小文件当中找到这个匹配的 query。假设从 A 当中的第一个文件当中取出一个 query那么假设这 query 在 B 当中是有交集的但是在B 当中的 这个 query 可能在任意位置那么平均切分的话这 query可能在任意位置。那么也就意味我想判断一个 query 在另一个文件当中是否有交集就得把另一个大文件切分出的所有小文件都判断寻找一遍那么这个效率就可想而知了。
所以这里就需要哈希切分了。
还是同样把上述 两个大文件 都各自切成 1000 个小文件从 大文件当中取出的 query他其实本质是一个字符串那么我们可以按照哈希当中对字符串转化成 key 的算法算出字符串的 key 值然后按照 key 值 % 1000因为是1000个小文件算出这个query是在 应该在哪一个 小文件当中存储然后把 这query 放到对应文件当中。
同样两个文件都进行同样的处理如此下来两个文件当中的query都是按照同一个哈希函数进行有规律的排列的那么此时我们就只需要按照顺序小文件匹配顺序来一对一对的小文件进行取交集就行了。 如下图所示 把两个文件按照 哈希函数去把 query 在 小文件当中进行存储。 此时去交集就只需要按照 小文件对应编号来进行取交集就可以了。不需要像之前一样找一个 query 需要遍历另一边的全部小文件。 我们把上述按照哈希函数来切分出来的一个个小文件这样的操作叫做哈希切分。 使用哈希切分的话在A和B 当中相同的 query 一定会进入 Ai 和 Bi 编号相同的小文件当中但是不同的 query 可能会进入Ai 和 Bi 编号相同的小文件当中。不可能出现 相同的 query 进去到不同编号的 小文件当中。 上述描述的过程就和哈希桶一样每一个哈希桶当中的数据都是计算出来的key 值冲突的情况在这个桶当中不止有 冲突的还有相等的那么这个相等的是一定存在的冲突的才是不一定存在的。 而且数据当中是有重复的部分的 也会是说我们要去重那么在找交集的时候Ai 读取出来 放到 set 当中去去重然后再去和 Bi 文件当中进行比较在不在在就是交集然后要删掉Bi当中的query 防止交集重复这是找交集的过程。
但是我们在利用哈希切分切分出来的一个一个小文件因为这种方式不是 平均切分我们上述之所以切分1000 份小文件是因为大文件是 300 G那么平均切分出来每个小文件就是 300M但是哈希切分不是平均的是要计算 query 的 key 值然后再去文件当中找位置。这种方式的话可能会导致某一个文件特别大某一个文件特别少。比如说一个文件当中冲突数据太多会导致 某个 Ai 文件太大甚至超过 1G。 所以这时候就要在对这个大的小文件再进行切分。但是切分之后不一定就会满足要求他可能还是比较大比如在这个文件当中数冲突的数据占大部分那么在切分怎么切都是不能切小的。如下图所示 对于上述情况我们可以大可以换另一种哈希函数来防止冲突。
但是换哈希函数可能还会出现其他冲突而且他不能解决下述这种场景 假设在上述的 Ai 小文件总大小是 5G其中没有正常数据只有冲突数据和 相同的数据其中 query 相同的占 4G冲突的数据占1G。那么就算我们修改 哈希函数那么也最多只能解决 1G 的大小剩下 4G 是相同的query计算出来的 key 值 不管用哪一个哈希函数计算出的结果都是相同的。 解决方案
先把 Ai 当中的query 读到一个 set 当中先不进行切分指的是二次切分先进行读取如果set 当中的 insert报错抛出异常bad_alloc那就说明现在是 query 大多数都冲突的情况不是大多数相等的情况如果 insert 能全部读出来insert 当中 set 里面那么就说明 Ai 当中就有大量的 重复 query。如果抛出异常说明有大量冲突再换一个哈希函数即可在进行二次切分。 2.给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址 同样的还是要进行 哈希切分把大文件按照哈希函数 切分成一个个小文件。
此时相同的文件一定进入了同一个小文件我们再去用 map 来分别统计每一个小文件当中每一个 ip 出现的次数把最大的ip 和这个ip 出现次数保存起来。在去 统计下一个 ip。
至于 判断 一个小文件当中 ip 的最大值有很多方法了可以 用 小堆来实现。
