C++:哈希拓展-位图

news/2024/11/19 6:22:39/

目录

一.问题导入

二.什么是位图?

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 


http://www.ppmy.cn/news/1548167.html

相关文章

【算法】【优选算法】前缀和（下）

【算法】【优选算法】前缀和（下）

目录 一、560.和为K的⼦数组1.1 前缀和1.2 暴力枚举 二、974.和可被K整除的⼦数组2.1 前缀和2.2 暴力枚举 三、525.连续数组3.1 前缀和3.2 暴力枚举 四、1314.矩阵区域和4.1 前缀和4.2 暴力枚举 一、560.和为K的⼦数组 题目链接&#xff1a;560.和为K的⼦数组 题目描述&#x…
阅读更多...
手机发展史介绍

手机发展史介绍

手机&#xff0c;这个曾经在电影和科幻小说中出现的高科技产品&#xff0c;如今已经渗透进了我们生活的每个角落。从单纯的通讯工具到如今集成了通讯、娱乐、工作、社交等多种功能的智能终端&#xff0c;手机的发展史也是人类科技进步的缩影。本文将从手机的发展历程、技术革新…
阅读更多...
如何通过低代码逻辑编排实现业务流程自动化？

如何通过低代码逻辑编排实现业务流程自动化？

随着数字化转型的加速&#xff0c;企业对高效、灵活的业务流程自动化需求日益增加。传统开发模式下的定制化解决方案往往周期长、成本高且难以适应快速变化的需求。低代码平台以其直观、简便的操作界面和强大的功能逐渐成为企业实现业务流程自动化的理想选择。本文将探讨低代码…
阅读更多...
MySQL的编程语言

MySQL的编程语言

一、MySQL基础 使用系统的全局变量@@VERSION查看当前使用的MySQL的版本信息，SQL语句如下： select @@version; 将局部变量varl声明为char的类型，长度值为10，并为其赋值为“程菲” begin declare var1 char(10); set @var1="程菲"; end 通过局部变量查看d_eams数…
阅读更多...
视频智能分析软件LiteAIServer视频智能分析平台玩手机打电话检测算法

视频智能分析软件LiteAIServer视频智能分析平台玩手机打电话检测算法

在当今这个数字化时代&#xff0c;智能手机已成为我们日常生活中不可或缺的一部分&#xff0c;它极大地便利了我们的沟通与学习。然而&#xff0c;当这份便利被不恰当地带入到如工厂生产线、仓库以及学校课堂等特定的工作和学习环境中时&#xff0c;其潜在的危害便逐渐显露出来…
阅读更多...
无人机在森林中的应用！

无人机在森林中的应用！

一、森林资源调查 无人机可以利用遥感技术快速获取所需区域高精度的空间遥感信息&#xff0c;对森林图斑进行精确区划。相较于传统手段&#xff0c;无人机调查具有低成本、高效率、高时效的特点&#xff0c;尤其在地理环境条件不好的区域&#xff0c;调查人员无法或难以到达的…
阅读更多...
UEFI学习笔记（十八）：ARM电源管理之PSCI和SCMI概述

UEFI学习笔记（十八）：ARM电源管理之PSCI和SCMI概述

一、PSCI PSCI&#xff08;Power State Coordination Interface&#xff09;是一种用于支持不同监督系统之间协作的标准接口&#xff0c;目的是在多个操作系统或虚拟化层&#xff08;如超管理器&#xff09;之间协调处理器的电源状态管理。操作系统会动态调整核心的电源状态&a…
阅读更多...
GraphPad Prism与鹰谷电子实验记录本强强联合，数据兼容互通

GraphPad Prism与鹰谷电子实验记录本强强联合，数据兼容互通

在科研探索的征途上&#xff0c;每一次数据的记录与分析都至关重要。鹰谷很高兴地宣布&#xff0c;鹰谷电子实验记录本InELN&#xff0c;与国际知名生物数据统计分析GraphPad Prism软件&#xff0c;实现数据快速兼容互通&#xff01;使用鹰谷电子实验记录本的用户&#xff0c;将…
阅读更多...
最新文章

Copyright @ 2022~2023