【C++】位图
Ⅰ、bitset的介绍
位图:
- 就是用 比特位 来标识某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的。
位图的接口:
成员函数 功能
set 设置指定位或所有位
reset 清空指定位或所有位
flip 反转指定位或所有位
test 获取指定位的状态
count 获取被设置位的个数
size 获取可以容纳的位的个数
any 如果有任何一个位被设置则返回true
none 如果没有位被设置则返回true
all 如果所有位都被设置则返回true
- 注意:库里面的函数可以是指定位,也可以是所有位。
栗子:
给 40 亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这 40 亿个数中。
一般思路:
- 排序+二分
- 哈希(unordered_map)
在这里,我们可以用位图解决,空间复杂度会变低。
- 数据是否在给定的整形数据中。结果是在或者不在,刚好是两种状态。
- 那么可以使用一个二进制比特位来代表数据是否存在的信息。
- 如果二进制比特位为1,代表存在,为0代表不存在。
位图的应用:
- 快速查找某个数据是否在一个集合中。
- 排序+去重。
- 求两个集合的交集、并集等。
- 内核中信号标志位(信号屏蔽字和未决信号集)。
Ⅱ、位图的实现
1 .整体框架
- 我们选择用一个vector来存放数据。具体开多大的空间,可以用模板来表示。
- 在构造函数中,用户模板传入的多大字节。其中我们把用户传的大小除以32再加1。
- 判断多少个整形可以有这么多字节的空间,但是会浪费几个比特位,这些空间都是可以忽略的。
class BitSet
{
public:BitSet(){_bs.resize(N / 32 + 1);}private:vector<int> _bs;
};
2 .把某一位设置为1
这里有两步:
- 找到x所处在的那一位: 先确定这个数应该处在第几个整数(类似哈希表找存储位置),也就是index=x/32;然后通过把x对32取模,得到x在第index个整形的第pos个位置
- 把改为设置为1: 把1左移pos位,用这个数和第index整数进行按位或的操作
void set(size_t x)
{int i = x / 32;int y = x % 32;_bs[i] |= (1 << y);
}
3 . 把某一位设置为0
两步:
- 找到那一位: 同上
- 把这位设置为0: 把1左移pos位,把这个数取反,然后和第index个整数进行按位与的操作
void reset(size_t x)
{int i = x / 32;int y = x % 32;_bs[i] &= (~(1 << y));
}
4 . 判断某一位是否为1
两步:
- 找到那一位: 同上
- 把这位设置为0: 把1左移pos位,然后返回这个数和第index个整数进行按位与的的结果
bool test(size_t x)
{int i = x / 32;int y = x % 32;return _bs[i] & (1 << y);
}
- 测试:判断一个数组的元素在另一个数组是否存在。
void Test_BitSet()
{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 };BitSet<100> bs;for (auto e : a1)bs.set(e);for (auto e : a2)cout << bs.test(e) << " ";cout << endl;
}
- 测试结果:可以看见,33和66不存在,打印出来就是0。
5 .例题
问题:用位图实现一个数在数组中出现了几次?(一定是3次及一下)
- 这个题我们可以封装双位图来实现,一个位图代表个数的第一个比特位,一个位图代表个数的第二个比特
template<size_t N>
class Two_BitSet
{
public:void set(size_t x){bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);
//根据对应位置是否存在,来判断是否进位if (!bit1 && !bit2){_bs2.set(x);}else if (!bit1 && bit2){_bs1.set(x);_bs2.reset(x);}else{_bs2.set(x);}}int GetCount(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;}elsereturn 3;}
private:BitSet<N> _bs1;BitSet<N> _bs2;
};
测试:
void Test_TwoBitSet()
{int a[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6,6,6,6,7,9 };int sum = 0;Two_BitSet<100> bs;for (auto x : a)bs.set(x);for (int i = 0; i < 100; i++){cout << bs.GetCount(i) << " ";}cout << endl;}
在测试用例中,我使某些数,多出现了几次,所以结果就不准确了。
Ⅲ、总结
- 位图实现起来十分的简单,应用也是很广的,可以达到节省空间的效果。
- 但是它有一个致命的缺点就是只能处理整形数据。
整体代码:
#pragma once
#include<vector>
using namespace std;
template<size_t N>
class BitSet
{
public:BitSet(){_bs.resize(N / 32 + 1);}void set(size_t x){int i = x / 32;int y = x % 32;_bs[i] |= (1 << y);}void reset(size_t x){int i = x / 32;int y = x % 32;_bs[i] &= (~(1 << y));}bool test(size_t x){int i = x / 32;int y = x % 32;return _bs[i] & (1 << y);}
private:vector<int> _bs;
};
template<size_t N>
class Two_BitSet
{
public:void set(size_t x){bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);if (!bit1 && !bit2){_bs2.set(x);}else if (!bit1 && bit2){_bs1.set(x);_bs2.reset(x);}else{_bs2.set(x);}}int GetCount(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;}elsereturn 3;}
private:BitSet<N> _bs1;BitSet<N> _bs2;
};
相关文章:
【C++】位图
Ⅰ、bitset的介绍 位图: 就是用 比特位 来标识某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的。 位图的接口: 成员函数 功能 set 设置指定位或所有位 reset 清空指定位或所有位 flip …...
性能测试需求分析(超详细总结)
🍅 点击文末小卡片 ,免费获取软件测试全套资料,资料在手,涨薪更快 1、客户方提出 客户方能提出明确的性能需求,说明对方很重视性能测试,这样的企业一般是金融、电信、银行、医疗器械等;他们…...
React开发 - 技术总结系列二
HOC 初体验 高阶组件(HOC)是 React 中用于复用组件逻辑的一种高级技巧。HOC 自身不是 React API 的一部分,它是一种基于 React 的组合特性而形成的设计模式。 简单点说,就是组件作为参数,返回值也是组件的函数&#x…...
Spring事务实现原理
我们一般将Spring事务使用在数据库操作上面,用来保证数据的一致性和完整性 实现原理: 通过AOP和事务管理器实现的 1.AOP拦截: 拦截Transactional注解的方法调用 2.事务管理器: 负责事务的开启,提交和回滚 3.事务…...
云服务器部署upload-labs-docker(文件上传靶场)环境 以及相关报错问题
环境的搭建 准备:云服务器(本地的linux服务器(版本最好不要是老的不然不兼容docker)) f8x配置docker环境: https://github.com/ffffffff0x/f8x 一键配置 docker拉取file-labs靶场 https://github.com…...
Python进阶编程总结
🧑 博主简介:CSDN博客专家,历代文学网(PC端可以访问:https://literature.sinhy.com/#/literature?__c1000,移动端可微信小程序搜索“历代文学”)总架构师,15年工作经验,…...
【第 1 章 初识 C 语言】1.8 使用 C 语言的 7 个步骤
目录 1.8 使用 C 语言的 7 个步骤 1.8.1 第 1 步:定义程序的目标 1.8.2 第 2 步:设计程序 1.8.3 第 3 步:编写代码 1.8.4 第 4 步:编译 1.8.5 第 5 步:运行程序 1.8.6 第 6 步:测试和调试程序 1.8.…...
vue3 实现音频转文字组件
使用recorder-core第三方插件实现音频转纯文本的功能。 工具类文件 recoder.ts import Recorder from recorder-core import recorder-core/src/engine/wav import recorder-core/src/extensions/lib.fft.js import recorder-core/src/extensions/frequency.histogram.view i…...
MySQL各种锁详解
什么是锁? 1.1 锁的解释 计算机协调多个进程或线程并发访问某一资源的机制。 1.2 锁的重要性 在数据库中,除传统计算资源(CPU、RAM、I/O等)的争抢,数据也是一种供多用户共享的资源。 如何保证数据并发访问的一致性&…...
前端工程 Node 版本如何选择
1. Node 与 Npm 版本对应 这是一个必知必会的问题,尤其是对于维护那些老掉牙、一坨坨、非常大的有着长期历史的老破大工程。 1.1. package-lock.json 版本 首先你要会看项目的 package-lock.json 文件中的 lockfileVersion 版本号,这对于 NPM 安装来说…...
新增白名单赋予应用安装权限
目录 相关问题 具体实现 相关问题 安装app到/data/分区时,如何在安装阶段就赋予权限,无需请求权限 具体实现 frameworks/base/core/res/res/values/config.xml <!-- For whitelis apk --><string-array translatable"false" nam…...
学习Python的笔记14--迭代器和生成器
1.迭代器(Iterator) 概念: 迭代意味着重复多次,就像循环一样。 迭代器是一个可以记住遍历的位置的对象。 迭代器对象从集合的第一个元素开始访问,直到所有的元素被访问完结束。 迭代器只能往前不会后退。 1.iter…...
【Golang】Golang基础语法之面向对象:结构体和方法
面向对象——结构 Go 仅支持封装,不支持继承和多态;继承和多态要做的事情交给接口来完成,即——面向接口编程。Go 只有 struct,没有 class。 定义一个最简单的树节点(treeNode)结构,方法如下&…...
重磅升级:OpenAI o1模型上手实测,从芯片架构分析到象棋残局判断的全能表现
引言 昨日,在圣诞节系列发布会的第一天,OpenAI终于给我们带来了令人振奋的更新,这些更新有望塑造AI互动的未来。备受期待的OpenAI o1正式版的推出,标志着ChatGPT体验的重大进化,宣告了AI驱动应用新时代的开始。o1现已可…...
Pandas处理和分析嵌套JSON数据:从字符串到结构化DataFrame
在数据分析领域,我们经常遇到需要从非结构化数据中提取有用信息的场景。特别是当数据以JSON字符串的形式出现时,如何有效地将其转换为结构化的表格形式,以便进行进一步的分析和处理,成为了一个常见的挑战。本文将通过一个具体的例…...
《ODIN: A Single Model for 2D and 3D Segmentation》CVPR2024
斯坦福和微软: 代码链接:ODIN: A Single Model For 2D and 3D Perception 论文链接:2401.02416 摘要 这篇论文介绍了ODIN(Omni-Dimensional INstance segmentation),一个能够同时处理2D RGB图像和3D点云…...
第40节 在ArkTS中实现socket功能
1. 基本概念 在 ArkTS 中实现 Socket 功能主要涉及到网络通信中的套接字(Socket)编程。Socket 是一种用于在不同设备(如客户端和服务器)之间进行双向通信的接口,它允许应用程序发送和接收数据。在网络编程中…...
Ruby On Rails 笔记1——Rails 入门
突然想跟着官方文档把Ruby On Rails过一遍,把一些有用的记下来就可以一直看了,do它! https://guides.rubyonrails.org/v7.2/ 注:官网是英文文档,我自己翻译了一下,不确保完全准确,只供自己学习开发使用。 …...
npm, yarn, pnpm之间的区别
前言 在现代化的开发中,一个人可能同时开发多个项目,安装的项目越来越多,所随之安装的依赖包也越来越臃肿,而且有时候所安装的速度也很慢,甚至会安装失败。 因此我们就需要去了解一下,我们的包管理器&#…...
Uniapp的App环境下使用Map获取缩放比例
概述 目前我试过的就是你用vue后缀是拿不到比例的你可以用nvue当然uniapp的uvue应该是更加可以的我使用的是高德所以你得在高德的后台声请原生的Android的key才可以如果是vue3的开发模式的话不用使用this来获取当前对象使用scale对象来接受和改变缩放比例会比较友好然后直接走…...
[免费]基于Python的Django在线(生鲜)商城(电子商城)管理系统【论文+源码+SQL脚本】
大家好,我是java1234_小锋老师,看到一个不错的基于Python的Django在线(生鲜)商城(电子商城)管理系统,分享下哈。 项目视频演示 【免费】基于Python的Django在线(生鲜)商城(电子商城)管理系统 Python毕业设计_哔哩哔哩_bilibili 项目介绍 随…...
Go 1.19.4 HTTP编程-Day 20
1. HTTP协议 1.1 基本介绍 HTTP协议又称超文本传输协议,属于应用层协议,在传输层使用TCP协议。HTTP协议属是无状态的,对事务处理没有记忆能力,如果需要保存状态需要引用其他技术,如Cookie。HTTP协议属是无连接的&…...
基于微软云第一个大模型程序Java和python实现
1 注册一个微软云账号 按照提示一步一步注册,注册过程中,注册微软云账号需要visa卡。可以在某宝花钱30元买下。 2 部署模型 搜索openAI 创建资源组 部署一个模型 这个后面代码会使用 3 Java 实现 pom 依赖 <dependency><groupId>com…...
【5G】5G目标和标准化 5G targets and standardization
5G标准是在第三代合作伙伴关系项目(3GPP,3rd Generation Partnership Project)中定义的,实际的标准制定工作由参与3GPP活动的区域标准机构成员共同推进。目前,超过600家公司通过各自的地区标准组织成为3GPP的成员。然而…...
KernelShark在ubuntu24.04.01的编译
KernelShark在ubuntu24.04.01的编译 写在前面具体过程装ubuntu24.04.01安装depends下载代码如何编译cmake 输出make 输出 如何安装 初步启动Add the User to the perf Group 简单的使用trace-cmd抓包 来看我的文章,必有所得。 平凡中,总有我帮您踩过的坑…...
【Flutter】WillPopScope组件-监听物理返回键事件自定义返回事件
WillPopScope(onWillPop: () async {if ( flutterWebViewPlugin ! null && await flutterWebViewPlugin.canGoBack() true) {flutterWebViewPlugin!.goBack();return false; // 阻止默认的返回行为} else {return true; // 允许默认的返回行为}},child: Scaffold(),);…...
深度学习每周学习总结J8(Inception V1 算法实战与解析 - 猴痘识别)
🍨 本文为🔗365天深度学习训练营 中的学习记录博客🍖 原作者:K同学啊 | 接辅导、项目定制 目录 0. 总结Inception V1 简介1. 设置GPU2. 导入数据及处理部分3. 划分数据集4. 模型构建部分5. 设置超参数:定义损失函数&am…...
Django模板系统
1.常用语法 Django模板中只需要记两种特殊符号: {{ }}和 {% %} {{ }}表示变量,在模板渲染的时候替换成值,{% %}表示逻辑相关的操作。 2.变量 {{ 变量名 }} 变量名由字母数字和下划线组成。 点(.)在模板语言中有…...
【JavaWeb后端学习笔记】MySQL的数据操作语言(Data Manipulation Language,DML)
MySQL DML 0、准备表结构1、添加数据1.1 指定字段添加数据(单条)1.2 全部字段添加数据(单条)1.3 指定字段添加数据(批量)1.4 全部字段添加数据(批量) 2、修改数据3、删除数据 MySQL的…...
【SpringBoot】Day10-09 动态SQL-XML文件
动态SQL-XML文件的三点规范 1.XML映射文件的名称与Mapper接口名称保持一致,并且将XML映射文件和Mapper接口放置在相同包下(同包同名)- 在项目开发当中,一般都是一个接口对应一份儿映射配置文件; 2.XML映射文件的namesp…...
Linux絮絮叨(三) Ubuntu桌面版添加中文拼音输入法
步骤很详细,直接上教程 一. 配置安装简体拼音输入法 #安装相应的平台支持包 sudo apt install ibus-gtk ibus-gtk3# 安装简体拼音输入法 sudo apt install ibus-pinyin安装完成如果下面的步骤找不到对应输入法可以重启一下,一般不需要 二. 添加简体拼音…...
rockit 学习、开发笔记(六)(VENC)
前言 上节我们讲到了VDEC解码模块,那当然少不了VENC编码模块了,一般有编解码的需求都是为了压缩视频的大小,方便减少传输所占用的带宽。 概述 VENC 模块,即视频编码模块。本模块支持多路实时编码,且每路编码独立&am…...
Python+Django框架山东济南景点数据可视化系统网站作品截图和开题报告参考
博主介绍:黄菊华老师《Vue.js入门与商城开发实战》《微信小程序商城开发》图书作者,CSDN博客专家,在线教育专家,CSDN钻石讲师;专注大学生毕业设计教育、辅导。 所有项目都配有从入门到精通的基础知识视频课程ÿ…...
【C#】键值对的一种常见数据结构Dictionary<TKey, TValue>
在 C# 中,Dictionary<TKey, TValue> 是一个 键值对(key-value)集合,是一种非常常见的数据结构。它允许通过 键(key)来快速查找与之相关的 值(value)。你可以将其类比为一个映射…...
SQL Server:调用的目标发生了异常。(mscorlib)
我之前安装的SQL Server是2014版本,SSMS运行也很流畅,有一次有个同事让我链接云服务器SQL地址,直接报上图的错误,把我弄的一愣一愣的。 后面才发现,这是版本太低导致的,但是你如果使用Navicat是没有问题的…...
windows 上ffmpeg编译好的版本选择
1. Gyan.dev Gyan.dev 是一个广受信赖的 FFmpeg 预编译库提供者,提供多种版本的 FFmpeg,包括静态和动态链接版本。 下载链接: https://www.gyan.dev/ffmpeg/builds/ 特点: 提供最新稳定版和开发版。 支持静态和共享(动态&…...
前端工程化面试题(一)
如何使用 Docker 部署前端项目? 使用 Docker 部署前端项目通常涉及以下几个步骤: 创建项目:首先,需要在本地创建并配置好前端项目。 准备 Docker 文件: .dockerignore:这个文件用于排除不需要上传到 Dock…...
Java设计模式笔记(二)
十四、模版方法模式 1、介绍 1)模板方法模式(Template Method Pattern),又叫模板模式(Template Patern),在一个抽象类公开定义了执行它的方法的模板。它的子类可以按需重写方法实现,但调用将以抽象类中定义的方式进行。 2&…...
vscode(一)安装(ubuntu20.04)
1、更新软件包列表 sudo apt update2、安装依赖包 sudo apt install software-properties-common apt-transport-https wget3、导入Microsoft GPG密钥 wget -q https://packages.microsoft.com/keys/microsoft.asc -O- | sudo apt-key add -4、向系统添加VSCode存储库 sudo…...
C# 命名空间(Namespace)
文章目录 前言一、命名空间的定义与使用基础(一)定义语法与规则(二)调用命名空间内元素 二、using 关键字三、嵌套命名空间 前言 命名空间(Namespace)在于提供一种清晰、高效的方式,将一组名称与…...
云计算介绍_3(计算虚拟化——cpu虚拟化、内存虚拟化、io虚拟化、常见集群策略、华为FC)
计算虚拟化 1.计算虚拟化介绍1.1 计算虚拟化 分类(cpu虚拟化、内存虚拟化、IO虚拟化)1.2 cpu虚拟化1.3 内存虚拟化1.4 IO虚拟化1.5 常见的集群的策略1.6 华为FC 1.计算虚拟化介绍 1.1 计算虚拟化 分类(cpu虚拟化、内存虚拟化、IO虚拟化&#…...
Flutter开发App,编译条件下UI没问题,打包后UI出现问题
刚入门Flutter3个月,终于进入项目打包阶段,发现之前编译环境下都正常的UI,忽然有小部分出现异常,不显示UI部分了。查了2个小时都没发现原因。因为编译环境下,Android、iOS端都正常显示。但是进入打包安装后,…...
Python+OpenCV系列:Python和OpenCV的结合和发展
PythonOpenCV系列:Python和OpenCV的结合和发展 **引言****Python语言的发展****1.1 Python的诞生与发展****1.2 Python的核心特性与优势****1.3 Python的应用领域** **OpenCV的发展****2.1 OpenCV的起源与发展****2.2 OpenCV的功能特性****2.3 OpenCV的应用场景** *…...
报错 JSON.parse: expected property name or ‘}‘,JSON数据中对象的key值不为字符串
报错 JSON.parse: expected property name or ‘}’ 原因 多是因为数据转换时出错,可能是存在单引号或者对象key值不为string导致 这里记录下我遇见的问题(后端给的JSON数据里,对象key值不为string) 现在后端转换JSON数据大多…...
Flutter:商品多规格内容总结,响应式数据,高亮切换显示。
如图所示: 代码为练习时写的项目,写的一般,功能实现了,等以后再来优化。 自己模拟的数据结构 var data {id:1,name:精品小米等多种五谷杂粮精品小等多种五谷杂粮,logo:https://cdn.uviewui.com/uview/swiper/1.jpg,price:100.5…...
WPF+LibVLC开发播放器-LibVLC播放控制
接上一篇: LibVLC在C#中的使用 实现LibVLC播放器播放控制 界面 界面上添加一个Button按钮用于控制播放 <ButtonGrid.Row"1"Width"88"Height"24"Margin"10,0,0,0"HorizontalAlignment"Left"VerticalAlignme…...
Mac环境下brew安装LNMP
安装不同版本PHP 在Mac环境下同时运行多个版本的PHP,同Linux环境一样,都是将后台运行的php-fpm设置为不同的端口号,下面将已php7.2 和 php7.4为例 添加 tap 目的:homebrew仅保留最近的php版本,可能没有你需要的版本…...
nodejs后端项目使用pm2部署
nodejs后端项目使用pm2部署 安装pm2 npm install pm2 -g查看版本号 pm2 --version启动项目 pm2 start app.js# 设置别名 pm2 start app.js --name demo停止项目 pm2 stop [AppName] pm2 stop [ID]# 停止所有项目 pm2 stop all重启项目 pm2 restart [AppName] pm2 re…...
【C++】深入理解字符变量取地址的特殊性与内存管理机制详解
博客主页: [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 💯前言💯栈内存中的变量分配:谁先谁后?cout 的输出行为:按顺序执行,按地址递增读取代码执行顺序与内存布局的关系编译器优化的影响 &…...
【银河麒麟操作系统真实案例分享】内存黑洞导致服务器卡死分析全过程
了解更多银河麒麟操作系统全新产品,请点击访问 麒麟软件产品专区:https://product.kylinos.cn 开发者专区:https://developer.kylinos.cn 文档中心:https://documentkylinos.cn 现象描述 机房显示器连接服务器后黑屏ÿ…...