html网页的基本结构,优化seo公司哪家好,wordpress 七牛云,上海黄金网站设计一、位图
1.1 位图概念 面试题 给40亿个不重复的无符号整数#xff0c;没排过序。给一个无符号整数#xff0c;如何快速判断一个数是否在这40亿个数中。【腾讯】 遍历查找#xff1a;内存中无法存放40亿个整数#xff08;约占内存15-16G#xff09;#xff1b;时间复杂…一、位图
1.1 位图概念 面试题 给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中。【腾讯】 遍历查找内存中无法存放40亿个整数约占内存15-16G时间复杂度O(N) 先排序O(NlogN)再利用二分查找O(logN)数据太大只能存放在磁盘文件中数据读取速度慢。 位图 数据是否在给定的集合中结果是在或者不在刚好是两种状态那么可以使用一个二进制比特位来代表数据是否存在的信息如果二进制比特位为1代表存在为0代表不存在。利用位图解决该问题无符号整数的取值范围是0~2^32一个位代表一个整数只需要2^32bit 512MB内存空间即可。 位图概念 所谓位图就是用每一位来存放某种状态适用于海量数据数据无重复的场景。通常是用来判断某个数据存不存在的。数据的键值通过直接定址法与位图中的位建立联系。 提示位图在STL中的实现为bitset在头文件bitse中声明 1.2 位图的实现
关于位运算的相关知识请阅读
【C语言进阶】位运算 {位运算符位运算符的优先级位运算的应用 关闭位判断位打开位转置位位域}
#include vector
#include math.h
using namespace std; namespace zty{ template size_t N class bitset{ vectorchar _bt; size_t _count; public: bitset() :_bt(ceil((double)N/8)), //ceil向上取整 _count(0) {} //打开位 void set(size_t x){ if(xN) return; size_t i x/8; //计算在第几个char类型 size_t j x%8; //计算在char类型的第几位 _bt[i] | (1j); _count; } //关闭位void reset(size_t x){if(xN) return;size_t i x/8;size_t j x%8;_bt[i] ~(1j);--_count;}//判断位 bool test(size_t x){if(xN) return false;size_t i x/8;size_t j x%8;return _bt[i] (1j);}//返回bitset中被置为1的比特位数size_t count(){return _count;}//返回bitset中的比特位总数size_t size(){return N;}};
}1.3 位图应用
快速查找某个数据是否在一个集合中排序 去重求两个集合的交集、并集等操作系统中磁盘块标记
相关面试题
给定100亿个整数设计算法找到只出现一次的整数
思路
每个整数有3种状态出现0次出现1次出现2次及以上需要两个位图解决 template size_t Nclass twobitset1{bitsetN bs1;bitsetN bs2;public:void set(size_t x){if(!bs1.test(x) !bs2.test(x)) //出现0次(00)--出现1次(01){bs2.set(x);}else if(!bs1.test(x) bs2.test(x)) //出现1次(01)--出现2次(10){bs1.set(x);bs2.reset(x);}}void print_once_num(){for(size_t i 0; iN; i){//找到只出现一次的整数(01)if(!bs1.test(i) bs2.test(i)){cout i ;}}cout endl;}};void test1(){int arr[] {6,99,1,1,2,4,3,5,6,7,1,3,2,4,7,9,8,5,4,3,21,8,9,4,2,3,1,4,3,57};zty::twobitset1100 tbs;for(int e : arr){tbs.set(e);}tbs.print_once_num();
}给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集 思路每个文件对应一个位图两位图的对应位都为1就是交集。 template size_t Nclass twobitset2{bitsetN bs1; //文件1对应的位图bitsetN bs2; //文件2对应的位图public:void setbs1(size_t x){bs1.set(x);} void setbs2(size_t x){bs2.set(x);} void print_intersection_set(){for(size_t i 0; iN; i){//找出两个文件中数据的交集(11)if(bs1.test(i) bs2.test(i)){cout i ;}}cout endl;}};void test2(){int file1[] {6,99,1,1,2,4,3,5,6,7,1,3,2,4,7,9,8,5,4,3,21,8,9,4,2,3,1,4,3,57};int file2[] {5,3,1,5,12,23,45,6,78,9,12,13,15,57,3,4,9};zty::twobitset2100 tbs;for(int e : file1){tbs.setbs1(e);}for(int e : file2){tbs.setbs2(e);}tbs.print_intersection_set();
}位图应用变形1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整数
思路
每个整数有4种状态出现0次出现1次出现2次出现3次及以上需要两个位图解决 template size_t Nclass twobitset3{bitsetN bs1;bitsetN bs2;public:void set(size_t x){if(!bs1.test(x) !bs2.test(x)) //出现0次(00)--出现1次(01){bs2.set(x);}else if(!bs1.test(x) bs2.test(x)) //出现1次(01)--出现2次(10){bs1.set(x);bs2.reset(x);}else if(bs1.test(x) !bs2.test(x)) //出现2次(10)--出现3次(11){bs2.set(x);}}void print_atmost_twice(){//找到出现次数不超过2次的所有整数for(size_t i 0; iN; i){if(!bs1.test(i) bs2.test(i)) //出现1次(01){cout i ;}else if(bs1.test(i) !bs2.test(i)) //出现2次(10){cout i ;}}cout endl;}};void test3(){int arr[] {1,1,1,2,2,2,3,4,4,4,4,4,5,5,6};zty::twobitset3100 tbs;for(int e : arr){tbs.set(e);}tbs.print_atmost_twice();
}二、布隆过滤器
2.1 布隆过滤器概念 位图一般只能解决整形数据在或不在的问题如果数据是字符串或者其他类型可以先将其转换为无符号整型再插入位图。但这样的处理方式存在哈希冲突的概率比较大。 哈希表需要将数据全部加载到内存中还要开辟额外的指针(链表指针)和数组空间(负载因子)面对海量数据会占用大量的内存甚至可能出现内存空间不够用的情况。 于是诞生了新的容器——布隆过滤器。布隆过滤器是由布隆Burton Howard Bloom在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询可以用来告诉你 “某样东西一定不存在或者可能存在”它是用多个哈希函数将一个数据映射到位图结构中的多个位上以此来降低哈希冲突的概率。此种方式不仅可以提升查询效率也可以节省大量的内存空间。 布隆过滤器虽然可以降低哈希冲突的概率但不可完全避免。因此布隆过滤器可能发生误判**不存在一定是准确的但存在则可能发生误判。**误判率可以通过增加哈希函数(映射位数)来进一步降低。理论而言一个值映射的位越多误判率越低但同时空间消耗也就越多 提示STL没有实现布隆过滤器如有需要请自行实现。 2.2 布隆过滤器的结构
布隆过滤器的结构实际就是一个位图 2.2.1 插入
如果我们要映射一个值到布隆过滤器中我们需要使用多个不同的哈希函数生成**多个哈希值**并对每个生成的哈希值指向的 bit 位置 1例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7则上图转变为 2.2.2 查找 布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找分别计算每个哈希值对应的比特位置存储的是否为零只要有一个为零代表该元素一定不在哈希表中否则可能在哈希表中。 比如在布隆过滤器中查找“tencent” 假设3个哈希函数计算的哈希值为3、4、8虽然baidu和tencent两者通过Hash2计算的哈希值(4)相同造成哈希冲突。但Hash1和Hash3的计算结果不同只要三个哈希值中有一个位为0就能确定该字符串不存在。 再比如在布隆过滤器中查找“alibaba” 假设3个哈希函数计算的哈希值为1、4、7刚好和baidu的比特位全部重叠。此时布隆过滤器返回该元素存在但实际该元素是不存在的发生误判。
综上所述布隆过滤器如果说某个元素不存在时该元素一定不存在如果该元素存在时该元素可能存在因为有些哈希函数存在一定的误判。
2.2.3 删除
布隆过滤器不能直接支持删除工作原因有二 在删除一个元素时如果直接将该元素所对应的二进制比特位置0而该元素恰好与其他元素有重叠的位就会导致这些重叠元素也被删除。 不能确定待删除元素本身是存在于布隆过滤器的可能会导致误删。 2.3 如何选择哈希函数个数和布隆过滤器长度
很显然过小的布隆过滤器很快所有的 bit 位均为 1那么查询任何值都会返回“可能存在”起不到过滤的目的了。布隆过滤器的长度会直接影响误报率布隆过滤器越长其误报率越小。
另外哈希函数的个数也需要权衡个数越多则布隆过滤器 bit 位置位 1 的速度越快且布隆过滤器的效率越低但是如果太少的话那我们的误报率会变高。 如何选择适合业务的 k 和 m 值呢这里直接贴一个公式 例如当k为3时m≈4.2n我们向上取整为5。即布隆过滤器的长度是插入元素个数的5倍。 2.4 布隆过滤器的实现 //三种字符串哈希算法struct BKDRHash{size_t operator()(const string s){// BKDRsize_t value 0;for (auto ch : s){value ch;value * 31;}return value;}};struct APHash{size_t operator()(const string s){size_t hash 0;for (size_t i 0; i s.size(); i){if ((i 1) 0){hash ^ ((hash 7) ^ s[i] ^ (hash 3));}else{hash ^ (~((hash 11) ^ s[i] ^ (hash 5)));}}return hash;}};struct DJBHash{size_t operator()(const string s){size_t hash 5381;for (auto ch : s){hash (hash 5) ch;}return hash;}};//布隆过滤器//N是要插入的元素个数//布隆过滤器默认处理字符串template size_t N, class K string,class Hash1 BKDRHash,class Hash2 APHash,class Hash3 DJBHashclass BloomFilter{std::bitsetN*5 _bs; //当哈希函数的个数为3时布隆过滤器的长度是插入元素个数的5倍public:void set(const K key){//将三个哈希函数计算得到映射位置置1size_t hashi1 Hash1()(key) % _bs.size(); //_bs.size()--N*5_bs.set(hashi1);size_t hashi2 Hash2()(key) % _bs.size();_bs.set(hashi2);size_t hashi3 Hash3()(key) % _bs.size();_bs.set(hashi3);}bool test(const K key){//只要三个哈希函数计算得到映射位置中有一个位为0就返回falsesize_t hashi1 Hash1()(key) % _bs.size();if(!_bs.test(hashi1)) return false; //准确的size_t hashi2 Hash2()(key) % _bs.size();if(!_bs.test(hashi2)) return false; //准确的size_t hashi3 Hash3()(key) % _bs.size();if(!_bs.test(hashi3)) return false; //准确的return true; //可能存在误判}};测试代码
//简单测试
void TestBloomFilter1()
{zty::BloomFilter11 bf;string arr1[] { 苹果, 西瓜, 阿里, 美团, 苹果, 字节, 西瓜, 苹果, 香蕉, 苹果, 腾讯 };for (auto str : arr1){bf.set(str);}for (auto str : arr1){cout bf.test(str) endl;}cout endl endl;string arr2[] { 苹果111, 西瓜, 阿里2222, 美团, 苹果dadcaddxadx, 字节, 西瓜sSSSX, 苹果, 香蕉, 苹果$, 腾讯 };for (auto str : arr2){cout str:bf.test(str) endl;}
}//误判率测试
void TestBloomFilter2()
{srand(time(0));const size_t N 100000;zty::BloomFilterN bf;cout sizeof BloomFilter: sizeof(bf) endl; std::vectorstd::string v1;std::string url https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html;for (size_t i 0; i N; i){v1.push_back(url std::to_string(1234 i));}for (auto str : v1){bf.set(str);}//测试相似字符串误判率std::vectorstd::string v2;for (size_t i 0; i N; i){std::string url http://www.cnblogs.com/-clq/archive/2021/05/31/2528153.html;url std::to_string(rand() i);v2.push_back(url);}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;url std::to_string(rand()i);v3.push_back(url);}size_t n3 0;for (auto str : v3){if (bf.test(str)){n3;}}cout 不相似字符串误判率: (double)n3 / (double)N endl;
}2.5 布隆过滤器的应用
提高查找效率利用布隆过滤器减少磁盘 IO 或者网络请求因为一旦一个值必定不存在的话我们可以不用进行后续昂贵的查询请求。 海量数据处理
给两个文件分别有100亿个query(字符串)我们只有1G内存如何找到两个文件交集分别给出精确算法和近似算法 近似算法将其中一个文件中的query插入到布隆过滤器中再在布隆过滤器中遍历查找另一个文件的query。如果找到就是交集。近似算法的问题有1.可能存在误判 2.没有进行去重 精确算法哈希切分
哈希切分
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址如何找到top K的IP 拓展一致性哈希 2.6 布隆过滤器的优缺点 优点 插入和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无关 哈希函数相互之间没有关系方便硬件并行运算 布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势 在能够承受一定的误判时布隆过滤器相比其他数据结构有很大的空间优势 数据量很大时布隆过滤器可以表示全集其他数据结构不能 使用同一组散列函数的布隆过滤器可以进行交、并、差运算 缺点 有误判率即存在假阳性(False Position)即不能准确判断元素在集合中(补救方法再建立一个白名单存储可能会误判的数据)不能获取元素本身一般情况下不能从布隆过滤器中删除元素
