php网站整合dz论坛,怎么修改网站排版,网站未被百度中收录的原因,网站建设与维护课程总结#x1f307;个人主页#xff1a;平凡的小苏 #x1f4da;学习格言#xff1a;命运给你一个低的起点#xff0c;是想看你精彩的翻盘#xff0c;而不是让你自甘堕落#xff0c;脚下的路虽然难走#xff0c;但我还能走#xff0c;比起向阳而生#xff0c;我更想尝试逆风… 个人主页平凡的小苏 学习格言命运给你一个低的起点是想看你精彩的翻盘而不是让你自甘堕落脚下的路虽然难走但我还能走比起向阳而生我更想尝试逆风翻盘。 C专栏C内功修炼基地 家人们更新不易你们的点赞和⭐关注⭐真的对我真重要各位路 过的友友麻烦多多点赞关注。 欢迎你们的私信提问感谢你们的转发 关注我关注我关注我你们将会看到更多的优质内容 一、位图的概念
所谓位图就是用每一位来存放某种状态适用于海量数据数据无重复的场景。通常是用来判断某个数据存不存在的。
1、位图的面试题
给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中。
数据是否在给定的整形数据中结果是在或者不在刚好是两种状态那么可以使用一个二进制比特位来代表数据是否存在的信息如果二进制比特位为1代表存在为0代表不存在。 2、位图模拟实现
#include iostream
#include vector
using std::cout;
using std::endl;
namespace sqy
{templatesize_t Nclass bitset{public:bitset(){_bits.resize(N / 8 1);}void set(size_t n){size_t i n / 8;//算出n属于_bits的哪一个下标size_t j n % 8;//算出属于_bits下标的哪一个比特位_bits[i] | 1 j;} void reset(size_t n){size_t i n / 8;//算出n属于_bits的哪一个下标size_t j n % 8;//算出属于_bits下标的哪一个比特位_bits[i] (~(1 j));}bool test(size_t n){size_t i n / 8;//算出n属于_bits的哪一个下标size_t j n % 8;//算出属于_bits下标的哪一个比特位return _bits[i] (1 j);}private:std::vectorchar _bits;};3、位图的应用
给定100亿个整数设计算法找到只出现一次的整数 我们可以使用两个位图如果是00则表示没有出现一次01表示出现一次10往后的就可以不用实现了。 给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集 使用两个位图将两个文件的数据分别映射到对应的位图中在进行遍历按位与如果为1则为交集否则反之。 位图应用变形1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整数 我们可以使用两个位图如果是00则表示没有出现一次01表示出现一次10表示出现两次11往后的就可以不用实现了。 代码示例
templatesize_t Nclass twobitset{public:void set(size_t n){if (b1.test(n) false b2.test(n) false) //00 - 01{b1.set(n);}else if (b1.test(n) true b2.test(n) false) //01 - 10{b1.reset(n);b2.set(n);}}void printOnce(){for (size_t i 0; i N; i){if (!b2.test(i) b1.test(i)){cout i ;}}cout endl;}private:bitsetN b1;bitsetN b2;};4、位图的优缺点
优点节省空间查找速度快
缺点要求范围相对集中范围特别分散的空间消耗大
位图只对整型使用浮点数、string等等其他类型无法使用。
如果要判断其他类型该类型如果可以使用哈希函数转换为整型的可以考虑布隆过滤器
二、布隆过滤器
1、布隆过滤器的概念
布隆过滤器是由布隆Burton Howard Bloom在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询可以用来告诉你 “某样东西一定不存在或者可能存在”它是用多个哈希函数将一个数据映射到位图结构中。此种方式不仅可以提升查询效率也可以节省大量的内存空间。 我们为了降低误判的概率解决方法就是对同一个元素使用多组哈希函数进行映射它能降低误判率但增加了空间消耗使用时需要把控号布隆过滤器的哈希函数的个数和布隆过滤器的长度 2、布隆过滤器的使用场景
1、不需要一定准确的场景例如个人网站注册的时候昵称判重使用布隆过滤器可以判断某个昵称一定没有被使用过但会误判某些造成冲突但没有被使用的昵称
2、提高效率。例如客户端查找信息时先用布隆过滤器筛选一下如果不在则直接将未查到的信息反馈给客户端如果布隆过滤器发现查找信息与位图匹配则将需要查找的信息推送给服务器中的数据库进行精确查找
3、布隆过滤器的删除
单纯的布隆过滤器时不支持删除的因为一个比特位可能被多个元素所映射。如果非要在布隆过滤器中实现删除那就只能将位图结构修改未计数器结构。数据set时每被映射一次计数器加1reset时该位计数器-1直到该位计数器为0.但是这种操作所需的空间消耗急剧增加。
4、布隆过滤器的优缺点
优点 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无关 哈希函数相互之间没有关系方便硬件并行运算 布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势 在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势 数据量很大时布隆过滤器可以表示全集其他数据结构不能 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
缺点 有误判率即存在假阳性(False Position)即不能准确判断元素是否在集合中 (补救方法再建立一个白名单存储可能会误判的数据) 不能获取元素本身 一般情况下不能从布隆过滤器中删除元素 如果采用计数方式删除可能会存在计数回绕问题
5、布隆过滤器面试题
1、给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址 我们可以将它分成100个小文件使用哈希算法将ip转换成整型将它取模 iHashFunc(ip)%100,i是多少ip就进入几号小文件。 如果冲突的桶超过1G怎么办
1、这个桶冲突的IP很多大多都是不重复的map统计不下
2、这个桶冲突的IP很多大多都是重复的map可以统计 直接使用map中的insert将每一个冲突桶的元素插入到map中。情况一 如果insert失败说明空间不足new节点失败抛出异常。解决方法是 换个哈希函数递归再次对这个桶进行切分。情况二map可以正常统计 2、给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法和近似算法
精确算法使用哈希切分将两个大文件分别切成一个个小文件A0-A99B0-B99蛋哥小文件超过1G换一个哈希函数因为使用的是同一个哈希函数所以交集必定存在于A0和B0A1和B1这种相同下标的小文件中。可以先将A0存放至哈希表中B0去重后与哈希表比对就能够得到精确交集
6、布隆过滤器的实现
#include iostream
#include vector
#include bitset
#include string
using namespace std;struct BKDRHash
{size_t operator()(const string s){// BKDRsize_t value 0;for (auto ch : s){value * 31;value ch;}return value;}
};
struct APHash
{size_t operator()(const string s){size_t hash 0;for (long 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;}
};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 len X * N;size_t index1 HashFunc1()(key) % len;size_t index2 HashFunc2()(key) % len;size_t index3 HashFunc3()(key) % len;/* cout index1 endl;cout index2 endl;cout index3 endlendl;*/_bs.set(index1);_bs.set(index2);_bs.set(index3);}bool test(const K key){size_t len X * N;size_t index1 HashFunc1()(key) % len;if (_bs.test(index1) false)return false;size_t index2 HashFunc2()(key) % len;if (_bs.test(index2) false)return false;size_t index3 HashFunc3()(key) % len;if (_bs.test(index3) false)return false;return true;//存在误判的}// 不支持删除删除可能会影响其他值。void reset(const K key);
private:bitsetX* N _bs;
};void test_bloomfilter1()
{srand((unsigned int)time(0));const size_t N 100000;BloomFilterN bf;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(i));}for (auto str : v1){bf.set(str);}// v2跟v1是相似字符串集但是不一样std::vectorstd::string v2;for (size_t i 0; i N; i){std::string url https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html;url std::to_string(999999 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(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;}
