当前位置: 首页 > 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…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...