如何实现WordPress网站导航中图片的动态切换效果？

wordpress网站导航,网站图片切换代码,软件商城哪个好,建设网站公司浩森宇特目录 #x1f680;#x1f680;前言一#xff0c;位图1. 位图的概念2. STL库中的位图3. 位图的设计4. 位图的模拟实现5. 位图的优缺点6. 位图相关考察题⽬ 二#xff0c;布隆过滤器1. 布隆过滤器的概念2. 布隆过滤器的实现3. 布隆过滤器删除问题4. 布隆过滤器的优缺点 点击… 目录 前言一位图1. 位图的概念2. STL库中的位图3. 位图的设计4. 位图的模拟实现5. 位图的优缺点6. 位图相关考察题⽬ 二布隆过滤器1. 布隆过滤器的概念2. 布隆过滤器的实现3. 布隆过滤器删除问题4. 布隆过滤器的优缺点 点击跳转至文章 【C/STL】哈希 – 线性探测哈希桶 前言 在前面的文章里我们已经学习了什么是哈希和以哈希表为底层的unordered系列容器的使用。本篇文章的位图布隆过滤器也是哈希思想下的产物经常使用它们来解决有关海量数据的问题。 一位图 1. 位图的概念 在引出位图的概念之前先来看一个经典面试题 深入分析 解题思路2是否可行我们先算算40亿个数据⼤概需要多少内存。 1G 1024MB 1024 * 1024KB 1024*1024 * 1024byte约等于10亿多byte那么40亿个整数约等于16G说明40亿个数是无法直接放到内存中的只能放到硬盘文件中。而二分查找只能对内存数组中的有序数据进行查找。 解题思路3数据是否在给定的整形数据中结果是在或者不在刚好是两种状态那么可以使⽤⼀个⼆进制⽐特位来代表数据是否存在的信息如果⼆进制⽐特位为1代表存在为0代表不存在。 那么我们设计⼀个⽤二进制比特位表⽰数据是否存在的数据结构这个数据结构就叫位图。 2. STL库中的位图 根据文档可知位图bitset 是非类型模板N是指需要多少比特位。使用时需要包含头文件 #include bitset位图常用的核心接口主要有三个 (1) x 映射位标记成1(插入 x有这个数据了) (2) x 映射位标记成0(删除 x没有这个数据了) (3) 检查是否存在这个数据 x映射的位是1返回真 x映射的位是0返回假 3. 位图的设计 位图本质是⼀个直接定址法的哈希表每个整型值映射⼀个bit位位图提供控制这个bit的相关接口。 实现中需要注意的是C/C没有对应位的类型只能看int/char这样整形类型我们再通过位运算去控制对应的⽐特位。⽐如我们数据存到vector int 中相当于每个int值映射对应的32个值⽐如第⼀个整形映射0-31对应的位第⼆个整形映射32-63对应的位后⾯的以此类推那么来了⼀个整形值xi x / 32j x % 32计算出x映射的值在vector的第 i 个整形数据的第 j 位。 4. 位图的模拟实现 #includevector//非类型模板参数。需要多少比特位 template size_t N class bitset { public:bitset(){_bs.resize(N / 32 1);}//x映射位标记成1void set(size_t x){//映射的位置第i个整型数据的第j位size_t i x / 32;size_t j x % 32;_bs[i] | (1 j);}//x映射位标记成0void reset(size_t x){size_t i x / 32;size_t j x % 32;_bs[i] (~(1 j));}//x映射的位是1返回真//x映射的位是0返回假bool test(size_t x){size_t i x / 32;size_t j x % 32;return _bs[i] (1 j);} private:vectorsize_t _bs; }; 5. 位图的优缺点 优点增删查改快节省空间 缺点只适⽤于整形 6. 位图相关考察题⽬ 深入分析 第一题和第三题是同一类型的题我们先来分析这两题。首先我们知道把数据放入位图中只能标记在或不在两种状态而题目要求的是找出出现几次的数据可能是出现0次1次……显然单用一个位图的一个比特位是无法满足的。 用两个位图的标记就可以解决。我们规定00表示数据出现0次01表示数据出现1次10表示数据出现2次11表示数据出现3次及以上 代码实现如下 注意这里用的bitset是上文我们自己实现的bitset。 我们针对第一题和第三题设计一个结构 templatesize_t N class twobitset { public:void set(size_t x){bool bit1 _bs1.test(x);bool bit2 _bs2.test(x);if (!bit1 !bit2) // 00-01{_bs2.set(x);}else if (!bit1 bit2) // 01-10{_bs1.set(x);_bs2.reset(x);}else if (bit1 !bit2) // 10-11{_bs1.set(x);_bs2.set(x);}}// 返回0 出现0次数// 返回1 出现1次数// 返回2 出现2次数// 返回3 出现2次及以上int get_count(size_t x){bool bit1 _bs1.test(x);bool bit2 _bs2.test(x);if (!bit1 !bit2){return 0;}else if (!bit1 bit2){return 1;}else if (bit1 !bit2){return 2;}else{return 3;}}private:bitsetN _bs1;bitsetN _bs2; };//测试代码可以统计出100以内哪个数据出现了几次 void test_twobitset() {twobitset100 tbs; //开100个bit位int a[] { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6,6,6,6,7,9 };for (auto e : a){tbs.set(e);}for (size_t i 0; i 100; i){cout i - tbs.get_count(i) endl;//if (tbs.get_count(i) 1 || tbs.get_count(i) 2)//cout i endl;} }第二题的代码实现 把数据分别放入两个位图中如果两个位图的标记均为1说明都存在就是二者的交集。 void test_bitset1() {int a1[] { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 };int a2[] { 5,3,5,99,6,99,33,66 };bit::bitset100 bs1;bit::bitset100 bs2;for (auto e : a1)bs1.set(e);for (auto e : a2)bs2.set(e);for (size_t i 0; i 100; i){if (bs1.test(i) bs2.test(i))cout i endl;} }二布隆过滤器 有⼀些场景下⾯有⼤量数据需要判断是否存在⽽这些数据不是整形那么位图就不能使⽤了使⽤红⿊树/哈希表等内存空间可能不够。这些场景就需要布隆过滤器来解决。 1. 布隆过滤器的概念 布隆过滤器是⼀种可以⽤来告诉你某样东西⼀定不存在或者可能存在的数据结构它是⽤多个哈希函数将⼀个数据映射到位图结构中。 布隆过滤器的思路就是把key先映射转成哈希整型值再映射⼀个位如果只映射⼀个位的话冲突率会⽐较多所以可以通过多个哈希函数映射多个位降低冲突率。 布隆过滤器这⾥跟哈希表不⼀样它⽆法解决哈希冲突的因为他压根就不存储这个值只标记映射的位。它的思路是尽可能降低哈希冲突。判断⼀个值key在是不准确的判断⼀个值key不在是准确的。 2. 布隆过滤器的实现 说明我们这里用的bitset是我们上文自己实现的bitset不是库里的。 #include BitSet.h #include stringstruct HashFuncBKDR {size_t operator()(const std::string s){size_t hash 0;for (auto ch : s){hash * 31;hash ch;}return hash;} };struct HashFuncAP { size_t operator()(const std::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 HashFuncDJB {size_t operator()(const std::string s){size_t hash 5381;for (auto ch : s)hash hash * 33 ^ ch;return hash;} };//要用多个哈希函数多映射几个位以便降低哈希冲突 template size_t N,size_t X 5,class K string,class Hash1 HashFuncBKDR,class Hash2 HashFuncAP,class Hash3 HashFuncDJB class BloomFilter { public:void Set(const K key){size_t hash1 Hash1()(key) % M;size_t hash2 Hash2()(key) % M;size_t hash3 Hash3()(key) % M;_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}//如果其中一个位为0就确定不在如果都为1那就在(存在误判)bool Test(const K key){size_t hash1 Hash1()(key) % M;if (!_bs.test(hash1))return false;size_t hash2 Hash2()(key) % M;if (!_bs.test(hash2))return false;size_t hash3 Hash3()(key) % M;if (!_bs.test(hash3))return false;return true;} private:static const size_t M N * X; //布隆过滤器的bit长度bit::bitsetM _bs; };//测试代码 void TestBloomFilter1() {BloomFilter10 bf;bf.Set(猪八戒);bf.Set(孙悟空);bf.Set(唐僧);cout bf.Test(猪八戒) endl;cout bf.Test(孙悟空) endl;cout bf.Test(唐僧) endl;cout bf.Test(沙僧) endl;cout bf.Test(猪八戒1) endl;cout bf.Test(猪戒八) endl; }3. 布隆过滤器删除问题 布隆过滤器默认是不⽀持删除的因为⽐如猪⼋戒“和”孙悟空“都映射在布隆过滤器中他们映射的位有⼀个位是共同映射的(冲突的)如果我们把孙悟空删掉那么再去查找“猪⼋戒”会查找不到因为那么“猪⼋戒”间接被删掉了。 4. 布隆过滤器的优缺点 优点增删查改快节省空间 缺点只适⽤于整形