当前位置: 首页 > news >正文

【C++ 学习 ㉖】- 位图详解(哈希扩展)

目录

一、位图的概念

二、位图的实现

2.1 - bitset.h

2.2 - test.cpp

三、位图的应用

3.1 - 例题一

3.2 - 例题二


 


一、位图的概念

假设有这样一个需求:在 100 亿个整型数字中快速查询某个数是否存在其中,并假设是 32 位操作系统,4 GB 内存。

由于数字的数量如此之多,如果使用一个 int 型的数组进行存储,需要占用的内存空间为 \dfrac{4 \times 10^{10}}{1024 \times 1024 \times 1024} \approx 37.25 GB,那么如何用更小的空间来 "存储" 这些数字呢?

我们可以用比特位(bit)来标记数字,每个比特位中存放的值则表示其标记的数字是否存在,0 表示不存在,1 表示存在,这就是位图的基本思想

例如,标记数字 1、2、4、6:

由于 int 总共有 2^{32} 种取值,所以标记所有这些数字需要占用的内存空间为 \dfrac{2^{32}}{8 \times 1024 \times 1024 \times 1024} = 0.5GB


二、位图的实现

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;};
}
  1. 思路:用 2 个比特位来表示一个数字的状态,00 表示不存在,01 表示只出现一次,10 表示出现一次以上。

    具体实现则是使用两个位图

  2. 思考:给定 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 - 例题二 一、位图的概念 假设有这样一个需求&#xff1a;在 100 亿个整型数字中快速查询某个数是否存在其中&#xff0c;并假设是 32 位操作系统&#xff0c;4 GB…...

天启科技联创郭志强:趟遍教育行业信数化沟坎,创业智能赛道重塑行业生态

郭志强 天启科技联合创始人 近20年互联网、企业信息化、数字化实施、管理及培训经验。对于集团型企业及初创企业、传统企业及互联网企业的信息化、数字化转型有自己独到的见解和实操经验。具备跨区域、集团化信息规划、解决方案、系统架构及企业流程搭建、优化和技术团队管理能…...

Cuckoo沙箱各Ubuntu版本安装及使用

1.沙箱简介 1.1 沙箱 沙箱是一个虚拟系统程序&#xff0c;允许你在沙箱环境中运行浏览器或其他程序&#xff0c;因此运行所产生的变化可以随后删除。它创造了一个类似沙盒的独立作业环境&#xff0c;在其内部运行的程序并不能对硬盘产生永久性的影响。 在网络安全中&#xff…...

什么是mvvm模式,优点是什么

MVVM&#xff08;Model-View-ViewModel&#xff09;模式是一种设计模式。它是一种开发模式&#xff0c;旨在分离用户界面的开发和业务逻辑的开发。MVVM模式将应用程序分为三个部分&#xff1a; Model&#xff1a;它代表应用程序的数据模型和业务逻辑。 View&#xff1a;它代表…...

C/C++ 中的函数返回局部变量以及局部变量的地址?

C/C中&#xff0c;函数内部的一切变量(函数内部局部变量&#xff0c;形参)都是在其被调用时才被分配内存单元。形参和函数内部的局部变量的生命期和作用域都是在函数内部(static变量的生命期除外)。子函数运行结束时&#xff0c;所有局部变量的内存单元会被系统释放。在C中&…...

springboot和vue:七、mybatis/mybatisplus多表查询+分页查询

mybatisplus实际上只对单表查询做了增强&#xff08;速度会更快&#xff09;&#xff0c;从传统的手写sql语句&#xff0c;自己做映射&#xff0c;变为封装好的QueryWrapper。 本篇文章的内容是有两张表&#xff0c;分别是用户表和订单表&#xff0c;在不直接在数据库做表连接的…...

【Leetcode】 51. N 皇后

按照国际象棋的规则&#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上&#xff0c;并且使皇后彼此之间不能相互攻击。 给你一个整数 n &#xff0c;返回所有不同的 n 皇后问题 的解决方案。 每一种…...

Java数据库连接:JDBC介绍与简单示例

Java数据库连接&#xff1a;JDBC介绍与简单示例 在Java程序中&#xff0c;操作数据库是必不可少的。JDBC&#xff08;Java Database Connectivity&#xff09;是Java中用于连接和操作数据库的一种技术。通过JDBC&#xff0c;Java程序可以与各种关系型数据库进行交互&#xff0…...

智慧茶园:茶厂茶园监管可视化视频管理系统解决方案

一、方案背景 我国是茶叶生产大国&#xff0c;茶叶销量全世界第一。随着经济社会的发展和人民生活水平的提高&#xff0c;对健康、天然的茶叶产品的消费需求量也在逐步提高。茶叶的种植、生产和制作过程工序复杂&#xff0c;伴随着人力成本的上升&#xff0c;传统茶厂的运营及…...

springboot整合pi支付开发

pi支付流程图&#xff1a; 使用Pi SDK功能发起支付由 Pi SDK 自动调用的回调函数&#xff08;让您的应用服务器知道它需要发出批准 API 请求&#xff09;从您的应用程序服务器到 Pi 服务器的 API 请求以批准付款&#xff08;让 Pi 服务器知道您知道此付款&#xff09;Pi浏览器向…...

类 ChatGPT 模型存在的局限性

尽管类ChatGPT模型经过数月的迭代和完善&#xff0c;已经初步融入了部分领域以及人们的日常生活&#xff0c;但目前市面上的产品和相关技术仍然存在一些问题&#xff0c;以下列出一些局限性进行详细说明与成因分析&#xff1a; 1&#xff09;互联网上高质量、大规模、经过清洗…...

Nginx的安全控制

安全控制 关于web服务器的安全是比较大的一个话题&#xff0c;里面所涉及的内容很多&#xff0c;Nginx反向代理是安全隔离来提升web服务器的安全&#xff0c;通过代理分开了客户端到应用程序服务器端的连接&#xff0c;实现了安全措施。在反向代理之前设置防火墙&#xff0c;…...

字符串与字符编码 - GO语言从入门到实战

字符串与字符编码 - GO语言从入门到实战 字符串 与其他主要编程语⾔的差异 基本数据类型&#xff1a;string 是基础数据类型&#xff0c;而不是引用类型或指针类型。string 在内存中占用的空间大小是固定的&#xff0c;且只读、不可改变。字节切片&#xff1a;string 是只读…...

12P4375X042-233C KJ2005X1-BA1 CE3007 EMERSON servo controller

12P4375X042-233C KJ2005X1-BA1 CE3007 EMERSON servo controller 我们提供三种不同类别的EDGEBoost I/O模块供选择&#xff0c;以实现最大程度的I/O定制: 数字和模拟输入/输出网络和连接边缘人工智能和存储 利用EDGEBoost I/O实现变革性技术 EBIO-2M2BK EBIO-2M2BK载板支持…...

WPF向Avalonia迁移(四、其他事项)

开发必备 1. Avalonia项目源代码&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;没有源代码&#xff0c;你连控件的背景色怎么改都找不着&#xff01;&#xff01; 2.下载你所使用的版本&#x…...

Python 代码调试

from pdb import set_trace as stx 是一个Python代码中常用的调试技巧之一&#xff0c;它用于在代码中插入断点以进行调试。这行代码的作用是将Python标准库中的 pdb&#xff08;Python Debugger&#xff09;模块中的 set_trace 函数导入&#xff0c;并将其重命名为 stx&#x…...

DM宣传单制作,利用在线模板,快速替换文字

如果你需要制作一批宣传单&#xff0c;但是时间很紧&#xff0c;而且没有专业的设计人员协助&#xff0c;那么你可以选择使用在线模板来快速制作宣传单。本文将介绍如何使用乔拓云平台&#xff0c;快速制作宣传单的方法。 步骤一&#xff1a;选择适合的在线制作工具 首先&…...

【力扣】42. 接雨水

这道题我卡了差不多1个小时&#xff0c;不是不会做&#xff0c;是不知道怎么能用栈来实现&#xff0c;后面看了一个博主的视频&#xff0c;豁然开朗&#xff0c;我主要的纠结点在于当指针指到7的时候&#xff0c;我计算出4到7的水块是2&#xff0c;但实际上是0&#xff0c;因为…...

IPETRONIK数据采集设备携手Softing Q-Vision软件致力于ADAS测试方案

一 背景 汽车ADAS技术是当下国内外的重点研究方向&#xff0c;且ADAS的发展水平和市场竞争力紧密相关&#xff0c;因此一套完善的ADAS测试方案对各整车厂而言非常重要。然而&#xff0c;国内ADAS测试却面临着很多阻碍&#xff0c;主要原因在于&#xff1a;相关测试设备昂贵&am…...

Go语言中的指针介绍

Go语言中的指针 文章目录 Go语言中的指针一、Go语言中的指针介绍1.1 指针介绍1.2 基本语法1.3 声明和初始化1.4 Go 指针的3个重要概念1.4.1 指针地址&#xff08;Pointer Address&#xff09;1.4.2 指针类型&#xff08;Pointer Type&#xff09;1.4.3 指针取值&#xff08;Poi…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...