企业网站的建设与管理论文,学生作业做网站需要,足球比赛直播英超,桃子网站目录 一、位图1.1 经典题目1.2 位图概念1.3 位图的应用1.4 关于位图的三个经典问题 二、布隆过滤器2.1 布隆过滤器的提出2.2 布隆过滤器的概念2.3 布隆过滤器的插入2.4 布隆过滤器的查找2.5 布隆过滤器删除2.6 代码实现2.7 布隆过滤器的优点2.8 布隆过滤器的缺陷2.9 布隆过滤器… 目录 一、位图1.1 经典题目1.2 位图概念1.3 位图的应用1.4 关于位图的三个经典问题 二、布隆过滤器2.1 布隆过滤器的提出2.2 布隆过滤器的概念2.3 布隆过滤器的插入2.4 布隆过滤器的查找2.5 布隆过滤器删除2.6 代码实现2.7 布隆过滤器的优点2.8 布隆过滤器的缺陷2.9 布隆过滤器的应用场景 三、海量数据处理3.1 布隆过滤器3.2 位图应用3.3 哈希切割 一、位图
1.1 经典题目
假设有这么一道题目 给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中。 1、先把数据用set存起来再查找一个无符号整数可以吗 不可以为什么因为40亿个整数大概要占16G内存但是一般配置的计算机都是开不出16G的内存的除非有些超级计算机所以这个方法并不适用于所有计算机。 2、排序二分查找可以吗 也不适合因为数据量太大而不能一次性全部加载到内存中所以需要在磁盘中进行归并排序要进行大量的IO效率低并且二分查找的时候也是要在磁盘中进行的所以这个方法也不适合解决这个问题 这也不行那也不行那该如何解决这个问题呢 上面两种方法之所以不适用是因为数据量太大了并且又是整形所占的内存空间太多所以我们不能开辟那么大的内存出来那如果我们能够用一个很小的空间标志出这些数据是否存在那不就可以了吗在这道题中我们的目标是知道一个数在不在这堆数里面是在不在的问题所以我们完全没有必要把这40亿个整数存起来只需要标志一下这些数是否存在就可以了标志一个数在不在我们其实只需要一个比特位就可以了某个数在就把对应的比特位设置成1不在就把对应的比特位设置成0这样一来本来需要4个字节即32个比特位的空间存放一个整形现在变成了只需要一个比特位标志所以40亿个整数占用的空间就从16G变成了500M500M的内存我们是可以开辟出来的我们把开辟出来标志数据在不在的这段空间叫做位图这样我们就能把这40亿个整数都标志到这个位图的对应位置再查找某一个数在不在的时候就只需要查看位图中对应位置的是否为1是1就表示这个数在是0就表示这个数不在。 如此一来就能把这道题给解决了。
1.2 位图概念
所谓位图就是用每一位来存放某种状态适用于海量数据数据无重复的场景。通常是用来判断某个数据存不存在的。 因为500M内存我们的计算机是能够开辟出来的所以我们用的是直接定址法即每一个整数直接映射到位图上的对应的位置。 位图代码实现
namespace BitSetC
{//N是非类型模板参数template size_t Nclass bitset{public://构造函数N表示该位图能映射的数据的最大值每一个映射的值是一个比特位所以应该根据//N的值求出我们需要开辟多少个char的空间因为/的特点是把余数舍去了所以为了映射数据//时不越界所以应该多开辟一个char的空间所以是开辟N/81个空间bitset(){_bs.resize(N / 8 1);}void set(size_t x){//计算x应该映射到第几个char中size_t i x / 8;//计算x在第i个char中的第几个位置size_t j x % 8;//通过位运算把第i个char的第j个位置设置为1//就把这个x设置进位图了_bs[i] | (1 j);}bool test(size_t x){//计算x应该映射到第几个char中size_t i x / 8;//计算x在第i个char中的第几个位置size_t j x % 8;//利用位运算检查第i个char的第j个位置是否被设置成1了//如果设置了就证明这个x在位图中否则x不在位图中if (((_bs[i] j) 1) 1){return true;}else{return false;}}void reset(size_t x){//计算x应该映射到第几个char中size_t i x / 8;//计算x在第i个char中的第几个位置size_t j x % 8;//通过位运算把第i个char中的第j位设置为0即可_bs[i] (~(1 j));}private://这里的vector的元素可以是char也可以是其他类型vectorchar _bs;};
}1.3 位图的应用
快速查找某个数据是否在一个集合中排序 去重求两个集合的交集、并集等操作系统中磁盘块标记
1.4 关于位图的三个经典问题
1、 给定100亿个整数设计算法找到只出现一次的整数 虽然是100亿个整数但是整数最多也就40多亿个所以一个位图占用的空间还是500M因为要找出只出现一次的整数如果只用一个位图只能标志一个数在不在并不能很好的统计该数出现的次数所以我们可以用两个位图来表示一个数字出现的次数因为两个比特位可以表示出四种情况00表示出现了0次01表示出现了1次10表示出现了2次11表示出现了3次如果一个数字出现了2次以上的就标志为11就行了因为我们要找的是出现一次的数字2次及以上的都是不符合要求的。
所以解决这个问题的大概思路是创建两个位图bs1和bs2然后遍历这100亿个整数判断bs1和bs2对应位置的情况如果在这个数对应位置中bs10bs20说明这个数还没有出现过此时bs2设置为1如果bs10bs21说明这个数字已经出现过一次此时把bs1设置为1bs2设置为0如果bs11bs20说明这个数字已经出现了2次这时把bs2设置为1或者说设不设置都可以因为这个数一定是不符合要求的。这样就能把所有数字出现的次数存放在了这两个位图中再遍历一遍这批数同时通过位图查看哪一些数映射到位图上对应位置的结果是bs10bs21的数就是出现一次的数。
2、位图应用变形1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整数。 同理找出不超过2次的整数也是先按照第1题那样把这100亿个整形设置到两个位图bs1和bs2中然后再遍历这100亿个数找到在位图中对应位置的bs10bs21或者bs11bs20的数就是出现次数不超过2的数统计即可。
下面是用我们自己实现的位图解决1、2问题的参考代码
namespace BitSetC
{//N是非类型模板参数template size_t Nclass bitset{public://构造函数N表示该位图能映射的数据的最大值每一个映射的值是一个比特位所以应该根据//N的值求出我们需要开辟多少个char的空间因为/的特点是把余数舍去了所以为了映射数据//时不越界所以应该多开辟一个char的空间所以是开辟N/81个空间bitset(){_bs.resize(N / 8 1);}void set(size_t x){//计算x应该映射到第几个char中size_t i x / 8;//计算x在第i个char中的第几个位置size_t j x % 8;//通过位运算把第i个char的第j个位置设置为1//就把这个x设置进位图了_bs[i] | (1 j);}bool test(size_t x){//计算x应该映射到第几个char中size_t i x / 8;//计算x在第i个char中的第几个位置size_t j x % 8;//利用位运算检查第i个char的第j个位置是否被设置成1了//如果设置了就证明这个x在位图中否则x不在位图中if (((_bs[i] j) 1) 1){return true;}else{return false;}}void reset(size_t x){//计算x应该映射到第几个char中size_t i x / 8;//计算x在第i个char中的第几个位置size_t j x % 8;//通过位运算把第i个char中的第j位设置为0即可_bs[i] (~(1 j));}private://这里的vector的元素可以是char也可以是其他类型vectorchar _bs;};
}//给定100亿个整数设计算法找到只出现一次的整数
//1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整数
template size_t N
class TwoBitSet
{
public:void set(size_t x){//x出现0次则原来的位图组合是00则把_bs1的x位置和_bs2的x位置设置为01if (!_bs1.test(x) !_bs2.test(x)){_bs2.set(x);}//x出现1次则原来的位图组合是01则把_bs1的x位置和_bs2的x位置设置为10else if (!_bs1.test(x) _bs2.test(x)){_bs1.set(x);_bs2.reset(x);}//x出现2次及以上则原来的位图组合是10则把_bs1的x位置和_bs2的x位置设置为11else if (_bs1.test(x) !_bs2.test(x)){_bs2.set(x);}}//查找只出现一次的数bool is_once(size_t x){if (!_bs1.test(x) _bs2.test(x)){return true;}return false;}//1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整数bool FindLowerTwo(size_t x){//出现1次if (!_bs1.test(x) _bs2.test(x)){return true;}//出现2次else if (_bs1.test(x) !_bs2.test(x)){return true;}//出现0次或者2次以上return false;}
private:BitSetC::bitsetN _bs1;BitSetC::bitsetN _bs2;
};3、给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集 这里也肯定是用位图来解决的因为有100亿个整数整形的范围是固定的42亿9千万个所以一个位图还是500M的空间。 所以先创建两个位图bs1和bs2然后分别把这两个文件的整数设置到bs1和bs2位图中。此时我们如何找到这两个位图中的交集呢我们知道111100011而位图中的每一个位置要么是0要么是1如果两个文件都有同一个数即交集那么它们在各自位图中的映射的位置一定是一样的所以把两个位图进行按位与操作得到的结果就是它们的交集了并且通过位图来查找交集还自带了去重的操作因为交集是一个无重复元素的集合。那这两个位图怎么做按位与操作呢其实这里不用真的把两个位图做按位与操作的只需要在遍历这些数的时候判断该数是否同时在bs1和bs2中就可以了。
int main()
{//给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集//假设nums1和nums2就是100亿个整数的文件int nums1[] { 1,2,3,6,8,2,3,6 ,6 };int nums2[] { 1,7,9,6 };BitSetC::bitset10 bs1;BitSetC::bitset10 bs2;for (const auto e : nums1){bs1.set(e);}for (const auto e : nums2){bs2.set(e);}for (size_t i 0; i 10; i){//同一个元素两个位图都设置了说明这个元素是交集if (bs1.test(i) bs2.test(i)){cout i ;}}cout endl;return 0;
}二、布隆过滤器
2.1 布隆过滤器的提出
我们在刷抖音时它会给我们不停地推荐新的内容它每次推荐时要去重去掉那些已经看过的内容。那么问题来了抖音客户端推荐系统如何实现推送去重的 用服务器记录了用户看过的所有历史记录当推荐系统推荐视频时会从每个用户的历史记录里进行筛选过滤掉那些已经存在的记录。 如何快速查找呢
用哈希表存储用户记录。缺点浪费空间用位图存储用户记录。缺点位图一般只能处理整形如果内容编号是字符串就无法处理了。将哈希与位图结合就叫做布隆过滤器。
2.2 布隆过滤器的概念
布隆过滤器是由布隆Burton Howard Bloom在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询可以用来告诉你 “某样东西一定不存在或者可能存在”它是用多个哈希函数将一个数据映射到位图结构中的多个位置。此种方式不仅可以提升查询效率也可以节省大量的内存空间。
2.3 布隆过滤器的插入 2.4 布隆过滤器的查找
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中的多个位置上因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找分别计算每个哈希值对应的比特位置存储的是否为零只要有一个为零代表该元素一定不在哈希表中否则可能在哈希表中。 注意布隆过滤器如果说某个元素不存在时该元素一定不存在如果该元素存在时该元素可能存在因为有些哈希函数存在一定的误判。 比如在布隆过滤器中查找zhaoyun时假设3个哈希函数计算的哈希值为2、4、6刚好和其他元素的比特位重叠即其他元素的刚好把246比特位都设置了此时布隆过滤器告诉你该元素存在但是该元素是不存在的。
2.5 布隆过滤器删除
布隆过滤器不能直接支持删除工作因为在删除一个元素时可能会影响其他元素。比如你要删除的元素的映射位置是135那么你想删除这个元素就要把135位置都设置为0但是可能其他元素通过哈希函数计算出来的映射位置也是1或者3或者5所以如果把135的位置改成0的话其它本来存在的元素也会变成不存在这显然是不对的。基于这样的原因有人提出既然直接置成0有可能会影响到其它元素那么就用一个引用计数记录这个位置被映射了多少次每一次删除的时候就减减这个引用计数直到引用计数减为0的时候才把这个位置设置为0这样删除就可以不影响其它元素了。 这个方法听起来确实可行但是它真的可行吗 其实不是的因为某个元素存在是会有误判的所以你怎么确定你这个元素是存在布隆过滤器里的呢你都无法确定你这个元素是否存在你怎么敢删除呢就好比“zhaoyun”这个元素假设它通过哈希函数算出来的映射位置是246而246三个位置刚好又被其他元素都映射了也就是说这个“zhaoyun”的存在是误判的它压根就不存在此时你删除“zhaoyun”即把246三个位置的引用计数都减1这符合逻辑吗这显然不符合你压根就不存在布隆过滤器中你如何删除。所以用引用计数的方法实现布隆过滤器的删除也是不可行的也是会影响到其他元素的所以无论如何布隆过滤器都是不支持删除操作的。
2.6 代码实现
//针对字符串的哈希函数
struct BKDRHash
{size_t operator()(const string str){size_t hash 0;for (auto ch : str){hash hash * 131 ch;}return hash;}
};struct APHash
{size_t operator()(const string str){size_t hash 0;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){size_t hash 5381;for (auto ch : str){hash (hash 5) ch;}return hash;}
};template size_t N,class K string,class Func1 BKDRHash, class Func2 APHash, class Func3 DJBHash
class BloomFilter
{
public://为了减少误判率所以一个字符串可以通过多个哈希函数//映射到多个位置只有当全部的映射位置都被设置为1了才算// 是这个字符串存在只要有任意一个位置没有被映射就说//明这个字符串是不存在的void set(const K key){//创建仿函数的匿名对象直接调用哈希函数计算映射位置//因为我们只有N个映射位置所以需要%N才能映射到合// 法的对应的映射位置上size_t hash1 Func1()(key) % N;size_t hash2 Func2()(key) % N;size_t hash3 Func3()(key) % N;//把通过哈希函数计算出来的这三个映射位置都设置为1//代表这个字符串是存在的_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}bool test(const K key){//分别检查key通过不同哈希函数计算出来的映射位置//是否都被设置成了1只要其中任意一个位置不被设//置就说明这个字符串是不存在的size_t hash1 Func1()(key) % N;if (!_bs.test(hash1)){return false;}size_t hash2 Func2()(key) % N;if (!_bs.test(hash2)){return false;}size_t hash3 Func3()(key) % N;if (!_bs.test(hash3)){return false;}//来到这里说明该字符串在这三个映射的位置都被设置成1了//此时可以认为该字符串是存在的但是也是会存在误判的//想要降低误判率可以增加每一个字符串映射位置的个数//或者增加N但是凡是都是有两面性的增加了哈希函数就//会在映射时增加计算映射位置的时间增大N就需要开辟更// 多的空间return true;}
private:bitsetN _bs;
};2.7 布隆过滤器的优点
增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无关。哈希函数相互之间没有关系方便硬件并行运算。布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势。在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势。数据量很大时布隆过滤器可以表示全集其他数据结构不能使用同一组散列函数的布隆过滤器可以进行交、并、差运算。
2.8 布隆过滤器的缺陷
有误判率即存在假阳性(False Position)即不能准确判断元素是否在集合中(补救方法再建立一个白名单存储可能会误判的数据)不能获取元素本身只能判断元素存不存在。不能从布隆过滤器中删除元素。如果采用计数方式删除还是会影响到其他元素因为可能要删除的元素本身就不存在。
2.9 布隆过滤器的应用场景 三、海量数据处理
3.1 布隆过滤器
给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法和近似算法。
3.2 位图应用
给定100亿个整数设计算法找到只出现一次的整数给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集位图应用变形1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整数 这3个问题在上面位图的地方已经解答过了。
3.3 哈希切割
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址 与上题条件相同如何找到top K的IP如何直接用Linux系统命令实现 按每一条log file出现的次数建立一个k个元素的小堆最后这个堆的k个数就是topk的IP用linux系统指令实现是
cat log.txt | cut -f1 -d | sort | uniq -c | sort -nr | head -n 1上述命令按以下步骤执行使用cat命令读取日志文件。
使用cut命令提取每行中的第一个字段即IP地址。
使用sort命令对IP地址进行排序。
使用uniq -c命令统计每个唯一的IP地址出现的次数。
使用sort -nr命令按照计数的逆序从高到低对IP地址进行排序。
使用head -n 1命令选择排序后的第一行即出现次数最多的IP地址。
要找到top K的IP地址您可以将最后一步的命令更改为head -n K其中K是您想找到的IP地址的数量。以上就是今天想要跟大家分享的内容啦你学会了吗如果感觉到有所帮助那就点亮一下小心心点点关注呗后期还会持续更新C相关的知识哦我们下期见
