【C++ 学习 ㉖】- 位图详解(哈希扩展)
目录
一、位图的概念
二、位图的实现
2.1 - bitset.h
2.2 - test.cpp
三、位图的应用
3.1 - 例题一
3.2 - 例题二
一、位图的概念
假设有这样一个需求:在 100 亿个整型数字中快速查询某个数是否存在其中,并假设是 32 位操作系统,4 GB 内存。
由于数字的数量如此之多,如果使用一个 int 型的数组进行存储,需要占用的内存空间为 ,那么如何用更小的空间来 "存储" 这些数字呢?
我们可以用比特位(bit)来标记数字,每个比特位中存放的值则表示其标记的数字是否存在,0 表示不存在,1 表示存在,这就是位图的基本思想。
例如,标记数字 1、2、4、6:

由于 int 总共有 种取值,所以标记所有这些数字需要占用的内存空间为
。
二、位图的实现
2.1 - bitset.h
#pragma once
#include <vector>
namespace yzz
{template<size_t N> // 总共有 N + 1 个比特位class bitset{public:bitset() : _v(N / 32 + 1) { }
void set(size_t x){size_t i = x / 32;size_t j = x % 32;_v[i] |= (1 << j);}
void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_v[i] &= ~(1 << j);}
bool test(size_t x) const{size_t i = x / 32;size_t j = x % 32;return _v[i] & (1 << j);}private:std::vector<int> _v;};
}
2.2 - test.cpp
#include "bitset.h"
#include <iostream>
using namespace std;
int main()
{int arr[] = { -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5 };yzz::bitset<0xffffffff> bs;for (const int& e : arr){bs.set(e);}bs.reset(-3);bs.reset(3);for (const int& e : arr){if (bs.test(e))cout << e << " ";}// -5 -4 -2 -1 0 1 2 4 5cout << endl;return 0;
}
三、位图的应用
位图的应用是大量数据的快速排序、查找和去重。
3.1 - 例题一
给定 100 亿个整数,找到只出现一次的所有整数。
doublebitset.h:
#pragma once
#include "bitset.h"
namespace yzz
{template<size_t N>class doublebitset{public:void set(size_t x){if (_bs1.test(x) == 0 && _bs2.test(x) == 0) // 00 -> 01{_bs2.set(x);}else if (_bs1.test(x) == 0 && _bs2.test(x) == 1) // 01 -> 10{_bs1.set(x);_bs2.reset(x);}// 10 则不变}
bool isSingleNum(size_t x) const{return _bs1.test(x) == 0 && _bs2.test(x) == 1;}private:bitset<N> _bs1;bitset<N> _bs2;};
}
思路:用 2 个比特位来表示一个数字的状态,00 表示不存在,01 表示只出现一次,10 表示出现一次以上。
具体实现则是使用两个位图。
思考:给定 100 亿个整数,找到出现次数不超过 2 次的所有整数。
思路是类似的,用 2 个比特位来表示一个数字的状态,00 表示不存在,01 表示只出现一次,10 表示出现两次,11 表示出现两次以上。
test.cpp:
#include "doublebitset.h"
#include <iostream>
using namespace std;
int main()
{int arr[] = { -3, -3, -2, -1, -2, 0, 1, 1, 2, 2, 3 };yzz::doublebitset<0xffffffff> dbs;for (const int& e : arr){dbs.set(e);}for (const int& e : arr){if (dbs.isSingleNum(e))cout << e << " ";}// -1 0 3cout << endl;return 0;
}
3.2 - 例题二
给两个文件,分别有 100 亿个整数,求两个文件的交集。
法一:
#include "bitset.h"
#include <iostream>
using namespace std;
int main()
{int arr1[] = { -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5 };int arr2[] = { -3, -3, -2, -1, -2, 0, 1, 1, 2, 2, 3 };yzz::bitset<0xffffffff> bs1;yzz::bitset<0xffffffff> bs2;// 去重for (const int& e : arr1){bs1.set(e);}for (const int& e : arr2){bs2.set(e);}// 求交集for (int i = -10; i <= 10; ++i){if (bs1.test(i) && bs2.test(i))cout << i << " ";}// -3 -2 -1 0 1 2 3cout << endl;return 0;
}
法二:
#include "bitset.h"
#include <iostream>
using namespace std;
int main()
{int arr1[] = { -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5 };int arr2[] = { -3, -3, -2, -1, -2, 0, 1, 1, 2, 2, 3 };yzz::bitset<0xffffffff> bs;for (const int& e : arr1){bs.set(e);}for (const int& e : arr2){if (bs.test(e)){cout << e << " ";bs.reset(e); // 避免出现重复的数字}}// -3 -2 -1 0 1 2 3cout << endl;return 0;
}相关文章:
【C++ 学习 ㉖】- 位图详解(哈希扩展)
目录 一、位图的概念 二、位图的实现 2.1 - bitset.h 2.2 - test.cpp 三、位图的应用 3.1 - 例题一 3.2 - 例题二 一、位图的概念 假设有这样一个需求:在 100 亿个整型数字中快速查询某个数是否存在其中,并假设是 32 位操作系统,4 GB…...
天启科技联创郭志强:趟遍教育行业信数化沟坎,创业智能赛道重塑行业生态
郭志强 天启科技联合创始人 近20年互联网、企业信息化、数字化实施、管理及培训经验。对于集团型企业及初创企业、传统企业及互联网企业的信息化、数字化转型有自己独到的见解和实操经验。具备跨区域、集团化信息规划、解决方案、系统架构及企业流程搭建、优化和技术团队管理能…...
Cuckoo沙箱各Ubuntu版本安装及使用
1.沙箱简介 1.1 沙箱 沙箱是一个虚拟系统程序,允许你在沙箱环境中运行浏览器或其他程序,因此运行所产生的变化可以随后删除。它创造了一个类似沙盒的独立作业环境,在其内部运行的程序并不能对硬盘产生永久性的影响。 在网络安全中ÿ…...
什么是mvvm模式,优点是什么
MVVM(Model-View-ViewModel)模式是一种设计模式。它是一种开发模式,旨在分离用户界面的开发和业务逻辑的开发。MVVM模式将应用程序分为三个部分: Model:它代表应用程序的数据模型和业务逻辑。 View:它代表…...
C/C++ 中的函数返回局部变量以及局部变量的地址?
C/C中,函数内部的一切变量(函数内部局部变量,形参)都是在其被调用时才被分配内存单元。形参和函数内部的局部变量的生命期和作用域都是在函数内部(static变量的生命期除外)。子函数运行结束时,所有局部变量的内存单元会被系统释放。在C中&…...
springboot和vue:七、mybatis/mybatisplus多表查询+分页查询
mybatisplus实际上只对单表查询做了增强(速度会更快),从传统的手写sql语句,自己做映射,变为封装好的QueryWrapper。 本篇文章的内容是有两张表,分别是用户表和订单表,在不直接在数据库做表连接的…...
【Leetcode】 51. N 皇后
按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上,并且使皇后彼此之间不能相互攻击。 给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。 每一种…...
Java数据库连接:JDBC介绍与简单示例
Java数据库连接:JDBC介绍与简单示例 在Java程序中,操作数据库是必不可少的。JDBC(Java Database Connectivity)是Java中用于连接和操作数据库的一种技术。通过JDBC,Java程序可以与各种关系型数据库进行交互࿰…...
智慧茶园:茶厂茶园监管可视化视频管理系统解决方案
一、方案背景 我国是茶叶生产大国,茶叶销量全世界第一。随着经济社会的发展和人民生活水平的提高,对健康、天然的茶叶产品的消费需求量也在逐步提高。茶叶的种植、生产和制作过程工序复杂,伴随着人力成本的上升,传统茶厂的运营及…...
springboot整合pi支付开发
pi支付流程图: 使用Pi SDK功能发起支付由 Pi SDK 自动调用的回调函数(让您的应用服务器知道它需要发出批准 API 请求)从您的应用程序服务器到 Pi 服务器的 API 请求以批准付款(让 Pi 服务器知道您知道此付款)Pi浏览器向…...
类 ChatGPT 模型存在的局限性
尽管类ChatGPT模型经过数月的迭代和完善,已经初步融入了部分领域以及人们的日常生活,但目前市面上的产品和相关技术仍然存在一些问题,以下列出一些局限性进行详细说明与成因分析: 1)互联网上高质量、大规模、经过清洗…...
Nginx的安全控制
安全控制 关于web服务器的安全是比较大的一个话题,里面所涉及的内容很多,Nginx反向代理是安全隔离来提升web服务器的安全,通过代理分开了客户端到应用程序服务器端的连接,实现了安全措施。在反向代理之前设置防火墙,…...
字符串与字符编码 - GO语言从入门到实战
字符串与字符编码 - GO语言从入门到实战 字符串 与其他主要编程语⾔的差异 基本数据类型:string 是基础数据类型,而不是引用类型或指针类型。string 在内存中占用的空间大小是固定的,且只读、不可改变。字节切片:string 是只读…...
12P4375X042-233C KJ2005X1-BA1 CE3007 EMERSON servo controller
12P4375X042-233C KJ2005X1-BA1 CE3007 EMERSON servo controller 我们提供三种不同类别的EDGEBoost I/O模块供选择,以实现最大程度的I/O定制: 数字和模拟输入/输出网络和连接边缘人工智能和存储 利用EDGEBoost I/O实现变革性技术 EBIO-2M2BK EBIO-2M2BK载板支持…...
WPF向Avalonia迁移(四、其他事项)
开发必备 1. Avalonia项目源代码!!!!!!!!!!没有源代码,你连控件的背景色怎么改都找不着!! 2.下载你所使用的版本&#x…...
Python 代码调试
from pdb import set_trace as stx 是一个Python代码中常用的调试技巧之一,它用于在代码中插入断点以进行调试。这行代码的作用是将Python标准库中的 pdb(Python Debugger)模块中的 set_trace 函数导入,并将其重命名为 stx&#x…...
DM宣传单制作,利用在线模板,快速替换文字
如果你需要制作一批宣传单,但是时间很紧,而且没有专业的设计人员协助,那么你可以选择使用在线模板来快速制作宣传单。本文将介绍如何使用乔拓云平台,快速制作宣传单的方法。 步骤一:选择适合的在线制作工具 首先&…...
【力扣】42. 接雨水
这道题我卡了差不多1个小时,不是不会做,是不知道怎么能用栈来实现,后面看了一个博主的视频,豁然开朗,我主要的纠结点在于当指针指到7的时候,我计算出4到7的水块是2,但实际上是0,因为…...
IPETRONIK数据采集设备携手Softing Q-Vision软件致力于ADAS测试方案
一 背景 汽车ADAS技术是当下国内外的重点研究方向,且ADAS的发展水平和市场竞争力紧密相关,因此一套完善的ADAS测试方案对各整车厂而言非常重要。然而,国内ADAS测试却面临着很多阻碍,主要原因在于:相关测试设备昂贵&am…...
Go语言中的指针介绍
Go语言中的指针 文章目录 Go语言中的指针一、Go语言中的指针介绍1.1 指针介绍1.2 基本语法1.3 声明和初始化1.4 Go 指针的3个重要概念1.4.1 指针地址(Pointer Address)1.4.2 指针类型(Pointer Type)1.4.3 指针取值(Poi…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
Unity UGUI Button事件流程
场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...
手机平板能效生态设计指令EU 2023/1670标准解读
手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读,综合法规核心要求、最新修正及企业合规要点: 一、法规背景与目标 生效与强制时间 发布于2023年8月31日(OJ公报&…...
