C++|哈希应用->位图
目录
一、概念
1.1原理分析:
1.2效率分析:
二、模拟实现
2.1位图框架+初始化空间
2.2映射
2.3清零
2.4判断
2.5测试代码
三、位图扩展应用
一、概念
位图,本质上也是一个数组,通过哈希思想构造的一种数据结构,他提现的哈希思想是整数与比特位的映射,通过比特位来代表某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在。
通过一道经典题来引入如何模拟实现位图结构。
给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。【腾讯】
方法1:遍历,时间复杂度O(N)
方法2:排序O(N*logN)+二分查找O(logN),时间复杂度O((N+1)*logN)
这两种方法看似都行,但是有一个问题的是40亿个整数大小,每个整形占4个字节,40亿个整数占160亿个字节,而1GB ≈ 10亿个字节,所以40亿个整数≈16GB,而16GB是大于正常的内存大小,我们也无法在内存中开16GB大小的空间。所以,该40亿个数据是存放在文件当中,但是也无法直接导入到内存当中,那么为了解决该问题,就可以采用映射的方式,将数据映射到位图中,且位图的大小是不超过内存的大小。至于原理是什么,接下来进行解释。
方法3:位图
1.1原理分析:
将每个整数想象成一个比特位,对于位图来说,它是个数组,目的就是要将这些整数存储到数组中去,也就是将比特位存储到数组中去,
那么数组存储的数据类型又是什么,只能是整形,如果是char类型,根本存不下,其他类型又不符合,接着将数组中每个整数当成32个比特位去理解,
所以最终目的是将比特位映射到数组中的对应整数中的32个比特位之中,也就是将整数映射到数组中对应整数的32个比特位之中,并将映射位置设为1,所以就可以通过判断映射到32个比特位的对应位置是1或者0来确定该整数是否存在。示意图;
通过该图,可以更清晰的了解是如何发生映射的,可以发现,数组中存储的仍然是整数,但是要把整数当成32个比特位去理解,虽然映射后,数组中的整数值是改变了,但是所看的根本就不是该整数值,而是整数对应的比特为是1还是0的状态来判断要映射的整数是否存在。
1.2效率分析:
那么这样算下来,40亿个数据映射到数组中的时间复杂度是O(N),但是对于该16GB的大小,对于数组来说就只要开16GB/32 = 0.5G 大小的空间,且内存是完全够开的,这就是位图体现的作用。
位图就是个以空间换时间的做法,但同时位图有自己的缺陷,就是只能针对整型数据,数据量大,整数在不在的问题。而对于其他数据类型不支持,那么对于这一问题,布隆过滤器可以解决,这在下一章节将解决。
现在就来模拟实现一下位图。
二、模拟实现
2.1位图框架+初始化空间
对于位图,需要容纳海量数据,判断数据是否存在,所以采用的是非类型模板参数。
假设整形个数据个数为N,那么对于位图而言需要开多大空间呢?
是 N/32个吗? 并不是,对于刚好是32的倍数的确实满足,但对于不能刚好取整的就要多开一个,即使是刚好取整,多开32个比特位空间也不足挂齿。所以最终开的空间是 N/32 + 1个大小空间。
template<size_t N>class bitset{public:bitset(){_bst.resize(N / 32 + 1);}private:vector<int> _bst;};
2.2映射
对于映射,在概念中,也已经简明扼要,这就不在过多阐述。
void set(size_t x){int i = x/32;//在第几个整形int j = x % 32;//在这个整形的第几个比特位_bst[i] |= (1 << j);//将该位置设置为1}
2.3清零
对于映射完后的数据,如果不想要了,就可以清理调,那么对此该如何操作了。其实只需要更改一下位操作即可,即_bst[i] &= ~(1<<j);示意图:
实现:
void reset(size_t x){int i = (x >> 5);int j = x % 32;_bst[i] &= ~(1 << j);//将对应映射位置清0}
2.4判断
同理只需要更改为操作判断该为是否为1即可
实现:
bool test(size_t x){int i = (x >> 5);int j = x % 32;return _bst[i] & (1 << j);//测试该整数映射位置是否为1,即判断整数在不在}
2.5测试代码
//MyBitSet.h
#include <iostream>
#include <vector>
using namespace std;
namespace bit
{template<size_t N>class bitset{public:bitset(){_bst.resize(N / 32 + 1);}void set(size_t x){int i = x/32;//在第几个整形int j = x % 32;//在这个整形的第几个比特位_bst[i] |= (1 << j);//将该位置设置为1}void reset(size_t x){int i = (x >> 5);int j = x % 32;_bst[i] &= ~(1 << j);//将对应映射位置清0}bool test(size_t x){int i = (x >> 5);int j = x % 32;return _bst[i] & (1 << j);//测试该整数映射位置是否为1,即判断整数在不在}private:vector<int> _bst;};
}
测试:
#include "MyBitSet.h"int main()
{bit::bitset<0xffffffff> bst;int arr[] = { 1,3,7,4,12,16,19,13,22,18 };for (size_t i = 0; i < sizeof(arr)/sizeof(arr[0]); i++){bst.set(arr[i]);}cout << bst.test(7);return 0;
}
输出结果:
三、位图扩展应用
1.给定100亿个整数,设计算法找到只出现一次的整数?
这里直接说解法了,用两个位图来实现,对于这100一个整数可能出现重复的数,那么可以分三种情况,出现0次,1次,2次及以上,那么可以用位图来表示的情况是:
出现0次:0 0
出现1次:0 1
出现2次及以上:1 0,
100亿个整数大约1.25GB,构造两个分别为2GB的位图即可,这样内存开了4GB的空间,也是够的。
代码实现,对于位图的代码,前面已经实现了,这里就直接使用了:
template<size_t N>class two_bitset{public:void set(size_t x){if (_bst1.test(x) == false && _bst2.test(x) == false)//出现1次{_bst2.set(x);}else if (_bst1.test(x) == false && _bst2.test(x) == true)//出现2次{_bst1.set(x);//1_bst2.reset(x);//0}}void PrintOnce(){for (int i = 0; i < N; i++){if (_bst1.test(i) == false && _bst2.test(i) == true){cout << i << endl;;}}}private:bitset<N> _bst1;bitset<N> _bst2;};
测试:
#include "MyBitSet.h"int main()
{bit::two_bitset<100> tbst;int arr[] = { 1,3,3,7,4,12,12,16,16,19,13,13,22,22,18 };for (auto e : arr){tbst.set(e);}tbst.PrintOnce();return 0;
}
输出结果:
2.给两个文件,分别由100亿个整数,我们只有1G内存,如何找到两个文件交集?
方案一:整型的范围是确定的,如果按大小算大约为2GB,映射到位图中,位图只需开2GB/32 =1/16,所以构造一个位图开0.5G是完全够用的,虽然有100亿个数据,但都脱离不开整型的范围,必然会有重复,且位图会进行去重,所以0.5G必然够用。接着,将一个文件的数据映射到这个位图,再判断另一个文件的数据在不在位图中即可。
方案二:构造两个位图,每个位图开0.5G个内存,分别将两个文件中的数据映射到两个位图中,进行按位与比较即可。
3.1个文件有100亿个整数,1G内存,设计算法找到出现次数不超过2次的所有整数
这跟第一个情况是类似的,分析出现0次,1次,2次,3次及以上,这里就不在实现了。
end~
相关文章:
C++|哈希应用->位图
目录 一、概念 1.1原理分析: 1.2效率分析: 二、模拟实现 2.1位图框架初始化空间 2.2映射 2.3清零 2.4判断 2.5测试代码 三、位图扩展应用 一、概念 位图,本质上也是一个数组,通过哈希思想构造的一种数据结构,…...
Rust 实战丨SSE(Server-Sent Events)
📌 SSE(Server-Sent Events)是一种允许服务器向客户端浏览器推送信息的技术。它是 HTML5 的一部分,专门用于建立一个单向的从服务器到客户端的通信连接。SSE的使用场景非常广泛,包括实时消息推送、实时通知更新等。 S…...
Django API开发实战:前后端分离、Restful风格与DRF序列化器详解
系列文章目录 Django入门全攻略:从零搭建你的第一个Web项目Django ORM入门指南:从概念到实践,掌握模型创建、迁移与视图操作Django ORM实战:模型字段与元选项配置,以及链式过滤与QF查询详解Django ORM深度游ÿ…...
React基础教程:TodoList案例
todoList案例——增加 定义状态 // 定义状态state {list: ["kevin", "book", "paul"]}利用ul遍历list数组 <ul>{this.state.list.map(item ><li style{{fontWeight: "bold", fontSize: "20px"}} key{item.i…...
PHP超详细安装及应用
目录 所需安装包如下 一、PHP安装 依赖包安装 安装扩展工具(先将PHP所需的软件包全部拖进centos根目录下) 安装libmcrypt 安装mhash 安装mcrypt 安装PHP 二、设置LAMP组件环境(要保证mysql、http都安装完成了) Php.ini的建…...
【算法篇】大数加法JavaScript版
题目描述 以字符串的形式读入两个数字,编写一个函数计算它们的和,以字符串形式返回。 数据范围:s.length,t.length≤100000,字符串仅由’0’~‘9’构成 要求:时间复杂度 𝑂(𝑛) 示例1 输入&…...
【LeetCode 128】 最长连续子序列
判断前一位数在不在字典中是这道题的关键之处,这样就可以避免重复查找,从而达到O(n) 的时间复杂度。如果没有这个判断,那么时间复杂度最坏也得是O(N^2)级别的。 1. 题目 2. 分析 合理利用数据结构。本题中使用了set来保存数组的元素&#x…...
SpringCloud-面试篇(二十六)
(1)Sentinel核心API-ProcessorslotChain...
使用__try...__except和try...catch捕获异常实例分享(附源码)
在C/C++的代码中,为了防止代码块执行的过程中产生异常导致软件崩溃,我们会给代码块添加__try...__except或try...catch保护,防止软件因为操作内部触发的异常产生崩溃。本文简单地介绍一下这两种异常捕获的使用示例。 1、概述 当软件运行过程中代码抛出异常,如果异常没有处…...
基于51单片机的简易温控水杯恒温杯仿真设计( proteus仿真+程序+设计报告+讲解视频)
基于51单片机的简易温控水杯恒温杯仿真设计( proteus仿真程序设计报告讲解视频) 仿真图proteus7.8及以上 程序编译器:keil 4/keil 5 编程语言:C语言 设计编号:S0099 1. 主要功能: 基于51单片机的简易温控水杯恒温…...
王德峰视频讲座,王德峰视频全部大全集,百度云百度网盘资源下载
王德峰教授的视频讲座其内容丰富、观点独到,深受广大学者和爱好者的喜爱。很多朋友想下载王德峰教授的讲座视频,今天我给大家分享一个下载王德峰教授视频的方法 搜索 “方圆资源网官网” 打开 “方圆资源网官网,找到王德峰教授的讲座 总之&a…...
Visual Studio和BOM历史渊源
今天看文档无意间碰到了微软对编码格式解释,如下链接: Understanding file encoding in VS Code and PowerShell - PowerShell | Microsoft LearnConfigure file encoding in VS Code and PowerShellhttps://learn.microsoft.com/en-us/powershell/scrip…...
虚拟现实(VR)游戏与增强现实(AR)游戏的区别
随着科技的飞速发展,沉浸式游戏体验已经成为现代娱乐的重要组成部分。虚拟现实(VR)游戏和增强现实(AR)游戏是这类体验中的两大主流,但它们在技术实现、用户体验和应用场景上有显著的区别。本文将详细探讨VR…...
git已经设置了自己的账号和密码,提交信息还是别人解决方法
1、运行一下命令缓存输入的用户名和密码: git config --global credential.helper wincred2、重新设置自己的邮箱和用户名 查看配置信息 git config --list修改用户名和邮箱地址: git config --global user.name 你自己的username git config --glo…...
探索面向对象与并发编程的完美融合:Java中的实践与思考
探索面向对象与并发编程的完美融合:Java中的实践与思考 在软件开发的世界里,面向对象编程(OOP)与并发编程(Concurrency)常被视为两个独立的领域。然而,Java语言却将这两个领域无缝地融合在一起,使得面向对象思想能够有效简化并发编程的复杂性。那么,如何才能用面向对…...
探索在线问诊系统的安全性与隐私保护
随着远程医疗的普及,在线问诊系统成为医疗服务的重要组成部分。然而,随着医疗数据的在线传输和存储,患者的隐私保护和数据安全面临巨大挑战。本文将探讨在线问诊系统的安全性与隐私保护,介绍常见的安全措施和技术实现,…...
How To: Localize Bar and Ribbon Skin Items
您可以使用Localizer对象自定义皮肤菜单,而不是迭代每个条形皮肤子菜单项和功能区皮肤库项容器来手动修改这些项。此方法允许您同时自定义所有现有栏子菜单和功能区库中的外观项目。 创建BarLocalizer类的派生类并重写XtraLocalizer.GetLocalizedString方法。 pub…...
通过 urllib 结合代理IP下载文件实现Python爬虫
本教程将向您展示如何使用 Python 的 urllib 库结合代理 IP 来下载文件。这种技术对于避免被目标网站封锁 IP 或简单地从不同的地理位置访问网站特别有用。通过这种方式,您可以更安全地进行网页数据的爬取和分析。 安装必须的库 在开始编写代码之前,您…...
单线服务器与双线服务器的区别?
单线服务器和双线服务器之间有什么区别呢?接下来就让小万来为大家具体分析一下吧! 首先单线服务器和双线服务器之间运营商的性质是不同的,单线服务器主要是一家带宽运营商,而双线服务器则是有两家运营商提供带宽的线路。 单线服务…...
使用Hadoop MapReduce实现各省学生总分降序排序,根据省份分出输出到不同文件
使用Hadoop MapReduce实现各省学生总分降序排序,根据省份分出输出到不同文件 本文将展示如何使用Hadoop MapReduce对一组学生成绩数据进行处理,将各省的学生成绩按总分降序排序并按照省份进行分区将结果分别输出到不同的文件中。 数据样例 我们将使用…...
LeetCode | 66.加一
这道题有多个思路,可以依次取数组的每一位,乘10后加下一位,直到最后一位,就得到我们数组所表示的数字,然后加一,然后把新得到的数字再转化为对应的数组,我的做法是直接取数组的最后一位…...
Oracle最终会扼杀MySQL?(译)
原文网站:https://www.percona.com/blog/is-oracle-finally-killing-mysql/ 作者:Peter Zaitsev 自从Oracle收购了MySQL后,很多人怀疑Oracle对开源MySQL的善意,这篇percona的文章深入分析了Oracle已经和将要对MySQL采取的措施&a…...
分布式物联网平台特点
随着物联网(IoT)技术的飞速发展,我们正步入一个万物互联的新时代。在这个时代,设备、数据和服务的无缝集成是实现智能化的关键。分布式物联网平台作为这一进程的核心,正在成为构建智能世界的基石。 一、分布式物联网平…...
【学习笔记】Linux文件编译调试相关(问题未解决)
//-I意为include 指定头文件搜索路径 -l:告诉编译器链接时需要的库 gcc *.c -I /usr/include/fastdfs/ -I /usr/include/fastcommon/ -l fdfsclient//调试gcc -g -rdynamic main.c如何解决 “ 段错误(吐核) ” ??? 【线上排错】记…...
微信小程序毕业设计-驾校管理系统项目开发实战(附源码+论文)
大家好!我是程序猿老A,感谢您阅读本文,欢迎一键三连哦。 💞当前专栏:微信小程序毕业设计 精彩专栏推荐👇🏻👇🏻👇🏻 🎀 Python毕业设计…...
【多线程】进程与线程
🥰🥰🥰来都来了,不妨点个关注叭! 👉博客主页:欢迎各位大佬!👈 文章目录 1. 操作系统2. 进程2.1 进程是什么2.2 进程管理2.3 进程调度2.3 内存管理2.4 进程间通信 3. 线程3.1 线程是什…...
【文献阅读】一种多波束阵列重构导航抗干扰算法
引言 针对导航信号在近地表的信号十分微弱、抗干扰能力差的问题,文章提出了自适应波束形成技术。 自适应波束形成技术可以分为调零抗干扰算法和多波束抗干扰算法。 调零抗干扰算法主要应用功率倒置技术,充分利用导航信号功率低于环境噪声功率的特点&…...
前端传递bool型后端用int收不到
文章目录 背景模拟错误点解决方法 背景 我前几天遇到一个低级错误,就是我前端发一个请求,把参数送到后端,但是我参数里面无意间传的布尔型(刚开始一直没注意到,因为当时参数有十几个),但是我后…...
巴伦在接收链路中的应用
一、巴伦的定义 "巴伦"(Balun),是一种平衡-不平衡转换器,通常用于将平衡信号(如差分信号)转换为不平衡信号(如单端信号),或者反之。巴伦在无线通信、广播、天…...
React常见面试题(2024最新版)
创建项目 npx create-react-app my-app启动项目 npm start目录结构 目录/文件名描述README.md项目的自述文件node_modules/项目依赖包存放目录package.json包管理配置文件,记录项目信息和依赖package-lock.json锁定依赖版本,确保跨环境一致性public/公共资源目录public/ind…...
南京网站建设招标/如何成为百度广告代理商
引用地址: http://hi.baidu.com/aaxh/blog/item/6d4863590b74a4292834f0db.html1. 定义游标定义游标语句的核心是定义了一个游标标识名,并把游标标识名和一个查询语句关联起来。DECLARE语句用于声明游标,它通过SELECT查询定义游标存储的数据集…...
asp网站应用程序/网络推广的含义
开心的Blue完成了自己的想法,水题dp,两种方法过关! 描述北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n 个地点排列在同一条直线上。我们用一个整数序列m1, m2, ...…...
做网站需要编程?/清远疫情防控措施
spark入门实战http://www.cnblogs.com/shishanyuan/p/4699644.html转载于:https://blog.51cto.com/wilsonking/1747157...
wordpress 书籍发布/seo知识分享
1.数据插入 1、插入完整或部分的行 INSERT INTO table VALUES (001,china,111,NULL);上面这种方式需要数据按照列在表中的顺序添加,没有值要用NULL填充。 但是我们最好不要采用这种方式,因为这高度依赖表中列的次序,即使次序知道也不能保证…...
网站开发答辩会问哪些问题/全网营销渠道
1 IV的用途 IV的全称是Information Value,中文意思是信息价值,或者信息量。 我们在用逻辑回归、决策树等模型方法构建分类模型时,经常需要对自变量进行筛选。比如我们有200个候选自变量,通常情况下,不会直接把200个变量…...
wordpress静态分离/焊工培训
近段时间以来,我们频频听到「机器学习(machine learning)」这个词(通常在预测分析(predictive analysis)和人工智能(artificial intelligence)的上下文中)。几十年来&…...