C++:哈希拓展-位图

目录

一.问题导入

二.什么是位图?

2.1如何确定目标数在哪个比特位?

2.2如何存放高低位

2.3位图模拟代码实现

2.3.1如何标记一个数

2.3.2如何重置标记

2.3.3如何检查一个数是否被标记

整体代码实现

标准库的Bitset

库中的bitset的缺陷

简单应用

---

一.问题导入

这道题直接使用遍历,效率太差,不推荐使用;

第二种方法就是先排序+二分查找:肯呢个有些人会觉得,排序的代价太大了;其实不然,我们只需要排序一次那么接下来的查找就好办了;
对于二分查找,效率是O(logn),根据2^10=1024,那2^30的数量级就是10^9,就已经上升到亿了,2^32大约就是40亿;所以我们使用二分在40亿个数中查找一个数最多只需要查找32次就可以了,效率是相当客观的;

那么问题来了:我们排序的数据是在内存中的,但是我们能在内存中直接开出40亿个整形吗?来计算一下;

答案肯定是不行的;1GB=1024MB=1024*1024KB=1024*1024*1024B(B是字节),10^9量级大约等于10亿多字节;一个整形4字节,40亿个整形就是16*10^9字节,相当于是16亿G;

所以40亿个整数是无法直接放到内存中的,只能放到硬件文件中,而二分查找只能堆内存中的数组中的有序数据进行查找;

针对上述的空间问题,我们可以使用位图思想来实现;

二.什么是位图?

我们都知道一个字节占8个比特位,每个比特位上储存的是二进制数0和1,那我们就可以在每个比特位上根据1或0,来判断是否存在一个数;

2.1如何确定目标数在哪个比特位?

这个问题其实并不难,我们采用无符号整形构造位图,一个整形占4字节,也就是32个比特位,那这样一个整形中我就可以标记32个数;

那如果我要标记35呢?

第一个整形可以标记的数是0-31,第二个整形可以标记的数是31-63......通过观察我们可以得到结论:35在第二个整形中,在第4个比特位也就是下标为3;

结论:N在第N/32个整形中,所在比特位的下标为N%32;

2.2如何存放高低位

我们都知道二进制数排列是从低位向高位的,而按位左移也是从低位向高位的;

同样的在位图中每个整形的存储方式也是如此;那么我们可以推断数值在位图中存储形态;

我们来分析一下:

首先,我要标记一个数1,这个数在第1个整形中,所占比特位下标为1;然后我们在看看2是在哪里标记的;2同样在第一个整形中,比特位下标为2,我们来看比特位高低位分布,2是不是在1的左边;

在一个数的比特位中,高位数的值大于低位数的值; 所以左边存储的是较大的数;右边存储的是较小的数;

2.3位图模拟代码实现

我们先来把整体框架来实现一下:

template <size_t N>//非类型模板参数N:一共有多少个数
class bitset
{
public:bitset():_bs(ceil(N/32.0))//根据模版的N开整形空间{}void set(int n);//标记数void reset(int n);//重置标记bool test(int n);//检查该数是否标记private:vector<int>_bs;  //使用变长数组模拟
};

2.3.1如何标记一个数

现在如果我们要标记一个数,那我们需要先确定这个数在第几个整形中和第几个比特位;i是所在整形的下标,j是所在比特位的下标:

i=N/32;

j=N%32;

我们通常是将1左移j位然后或上_bs[i];

template <size_t N>//非类型模板参数N:一共有多少个数
class bitset
{
public:bitset():_bs(ceil(N/32.0))//根据模版的N开整形空间:(ceil是向上取整){}void set(int n)
{int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位_bs[i] |= 1 << j;
}void reset(int n);bool test(int n);//检查该数是否标记private:vector<int>_bs;  //使用变长数组模拟
};

2.3.2如何重置标记

我们只需要将该比特位&上~(1<<j)即可;

template <size_t N>//非类型模板参数N:一共有多少个数
class bitset
{
public:bitset():_bs(ceil(N/32.0))//根据模版的N开整形空间:(ceil是向上取整){}void set(int n)
{int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位_bs[i] |= 1 << j;
}void reset(int n)
{int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位_bs[i] &= ~(1 << j);  
}bool test(int n);//检查该数是否标记private:vector<int>_bs;  //使用变长数组模拟
};

2.3.3如何检查一个数是否被标记

判断一个比特位是否是1:将该比特位&1,如果是1那就是1,如果是0那就是0;

template <size_t N>//非类型模板参数N:一共有多少个数
class bitset
{
public:bitset():_bs(ceil(N/32.0))//根据模版的N开整形空间:(ceil是向上取整){}void set(int n)
{int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位_bs[i] |= 1 << j;
}void reset(int n)
{int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位_bs[i] &= ~(1 << j);  
}bool test(int n){int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位return _bs[i] & (1 << j); }private:vector<int>_bs;  //使用变长数组模拟
};

整体代码实现

#include<iostream>
#include<vector>
#include<Bitset>   
using namespace std;
namespace bit {template <size_t T>class bitset{public:bitset():_bs(ceil(T/32.0)){}void set(int n){int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位_bs[i] |= 1 << j;}void reset(int n){int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位_bs[i] &= ~(1 << j);  }bool test(int n){int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位return _bs[i] & (1 << j); }private:vector<int>_bs;  };
}

标准库的Bitset

 其中最核心的就是set和reset;其他的了解即可;

库中的bitset的缺陷

我们模拟实现的bitset底层是使用的vector,而vector的空间来自堆上;这就意味着,我们开一个比较大的空间时bitset的大小是不变的;一直都是vector<int>的大小;

我们来验证一下:

结果一直都是32;为什么是32呢;根据我们在前面Vector的模拟实现可以得知,32是多个指针所占的内存空间;

那标准库中的bitset是什么样的呢?

标准库中的bitset底层是使用静态数组实现的;那么这就意味着空间是在堆栈上开辟的;其实堆栈是很小的,所以当我们开出一块很大的空间的时候容易出现问题;

所以当数据量十分巨大的时候我们尽量使用自己构造的bitset;

另外就是当我们使用我们的bitset<-1>bs时,是可以开出很大的空间的;

但是库中的bitset不支持此操作;

简单应用

这道题是有100亿个数,并且要统计次数,有效的次数就是0,1,2,3;正好占2个比特位,可以使用两个比特位来表示出现的次数;

这道题就是要是使用两个位图协同进行标记;

具体思路:封装两个位图->twoset,底层是bitset<1e10>bs1,bitset<1e10>bs2;分别代表n出现次数的两个比特位;

代码实现:

#include<iostream>
#include<vector>
#include<Bitset>   
using namespace std;
namespace bit 
{template <size_t N>    class bitset{public:bitset():_bs(ceil(N/32.0))      {}void set(int n){int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位_bs[i] |= 1 << j;}void reset(int n){int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位_bs[i] &= ~(1 << j);  }bool test(int n){int i = n / 32;//找到所在整形的下标int j = n % 32;//找到所在整形中对应的比特位return _bs[i] & (1 << j); }private:vector<int>_bs;  };template <size_t T>class twoset{public:twoset() = default;void set(size_t n){//00->01if (!bs1.test(n) && !bs2.test(n)){bs2.set(n);}else if (!bs1.test(n) && bs2.test(n))//01->10{bs1.set(n);bs2.reset(n);}else//10->11{bs2.set(n);}}int get_count(int n){return bs1.test(n)*2 + bs2.test(n);}private:bitset<T>bs1;    bitset<T>bs2;     };}

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=3te3qaa7daww8