位图和布隆过滤器:位图

在《unordered_mapunordered_set》 中提到过:

哈希是一种思想,通过哈希函数将数据转化为一个或多个整型 —— 映射关系;通过这种映射关系,可以做到以 O(1) 的时间复杂度查找数据。

本文即将介绍的 位图布隆过滤器 就是两个非常典型的哈希思想的应用成果,可以在应对海量数据问题 且 做到极大程度节省空间的同时,快速判断 一个整型 和 一个字符串 是否在 位图 和 布隆过滤器 中

一、位图

1.1 位图的概念

在直接给出位图的概念之前,我们先温习几个常识:

  • 1 int == 4 byte

  • 1 byte == 8 bit ——> 1 int == 32 bit

也就是说,假设我们有 10 个位于 [0, 32) 的整数,仅需 1 个 int 就可以将这些数据标记(在保证数据范围的情况下,即使数据量更大一些也没问题)。

位图的概念:

各个比特位上的数据默认为 0 —— 不存在,遍历数据的过程中,将数据对应位置的 0 修改为 1 —— 存在;再判断某个整数是否存在时,仅须根据其对应位置上的状态(0 或 1)即可得出。

图中 “53 在 32 右边” 的情形并不绝对,与机器的大小端有关。无论你的设备是大端机还是小端机,“1 << 21” —— 左移 都能保证把 “1” 往数据高位移动

进一步延伸,面对这样一个场景:

给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。

试图通过 排序 + 二分 的办法解决,显然不靠谱 —— 存下 40 亿个整数大约 16 GB 内存

面对海量整型数据,判断某个整数存在与否 的场景下,位图具有无可比拟的优势 —— 占用的空间小且能够快速查找

一个非常重要的问题:位图应该开多大的空间? 具体要开多大,不是由数据的个数决定,而是由数据的范围决定

代码:
	template<size_t N> // 非类型模板参数class bitset {public:bitset(){_bs.resize(N/32 + 1); // 开 (N/32 + 1) 个 int 类型空间}void set(size_t n) // 将 n 对应的位置状态修改为 1{size_t i = n / 32;size_t j = n % 32;_bs[i] |= (1 << j);}void reset(size_t n) // 将 n 对应的位置状态修改为 0{size_t i = n / 32;size_t j = n % 32;_bs[i] &= ~(1 << j);}bool test(size_t n) // 判断 n 是否存在{size_t i = n / 32;size_t j = n % 32;return _bs[i] & (1 << j);}private:vector<int> _bs;};

位图代码逻辑本身很简单,诸位读者要理解各个函数中位运算的经义。

PS: STL 库中 bitset 是在栈区上开空间,我们实现的位图在堆区上开空间。

1.2 切分思想

还是上面那个的场景(40 亿个不重复整数),我们进一步对可使用内存的大小进行限制 —— 只能使用 256 MB 。

这会带来一个结果:我们无法一次性把这么多整数存入位图 —— 40 亿个不重复整数大约 500 MB。

把这 40 亿个整数分成两个区间:[0, 2 ^ 31)[2 ^ 31, 2 ^ 32) 。(2 ^ 31 与 2 ^ 32 均为数学运算,C++ 中 ^ 为 异或)

先对 [0, 2 ^ 31) 范围内的整数进行 set() 和 test() ,处理完后将位图置空,再处理 [2 ^ 31, 2 ^ 32) 部分。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1425116.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

亚马逊Prime Day旺季备货遭遇美国海关查验高峰,应对策略全攻略!

随着全球化贸易的日益繁荣&#xff0c;跨境电商企业在旺季备货时面临着巨大的挑战&#xff0c;尤其是当遇到美国海关查验潮时&#xff0c;如何应对成为众多商家关注的焦点。本文将从分析美国海关查验的原因入手&#xff0c;为商家提供一系列应对策略和建议。 一、美国海关查验潮…

​学者观察 | 从区块链应用创新看长安链发展——CCF区块链专委会荣誉主任斯雪明

导语 2024年1月27日&#xff0c;斯雪明教授在长安链发布三周年庆暨生态年会上发表演讲&#xff0c;认为在区块链发展过程中&#xff0c;不仅需要技术创新&#xff0c;同时需要有价值、有特色、有示范意义的应用创新。斯雪明教授介绍了国内区块链技术与应用发展的现状、趋势与挑…

SVN切换账号

SVN切换账号 有这么一种情况&#xff0c;对于一个新项目&#xff0c;项目紧急的情况下&#xff0c;大家会使用一个svn账号下载代码&#xff0c;开始提前熟悉业务。那么当正式开发的时候&#xff0c;每个人的svn账号也已经下发下来了&#xff0c;这个时候大家就需要切换成自己的…

C# .Net8 switch 的用法

在 .net 8中&#xff0c;switch 不需要再和传统的写法一样了&#xff0c;会更加的方便 创建一个 .net 8 控制台项目 switch 的写法没必要和以前一样 namespace SwitchTest {internal class Program{static void Main(string[] args){int day 3;var week day switch{1 > &…

AIGC文生视频:Sora模型报告总结

作为世界模拟器的视频生成模型 我们探索视频数据生成模型的大规模训练。具体来说&#xff0c;我们在可变持续时间、分辨率和宽高比的视频和图像上联合训练文本条件扩散模型。我们利用对视频和图像潜在代码的时空补丁进行操作的变压器架构。我们最大的模型 Sora 能够生成一分钟…

继承的奥秘:面向对象编程中的血脉传承与智慧抉择

1. 概述 在面向对象编程&#xff08;OOP&#xff09;中&#xff0c;继承是构建复杂软件系统的基石之一。它允许我们定义一个类&#xff08;称为父类或基类&#xff09;作为其他类&#xff08;称为子类或派生类&#xff09;的基础&#xff0c;子类能够自动获得父类的属性和方法…

Stable Diffusion超详细教程!本地部署 Stable Diffusion

前言 目前市面上比较权威&#xff0c;并能用于工作中的AI绘画软件其实就两款&#xff1a; Midjourney&#xff08;MJ&#xff09;Stable-Diffusion&#xff08;SD&#xff09; MJ需要付费使用&#xff0c;而SD开源免费&#xff0c;但是上手难度和学习成本略大&#xff0c;并…

抖店商品详情API接口(店铺|标题|主图|价格|SKU属性等)

抖店商品详情API接口(店铺|标题|主图|价格|SKU属性等) 抖店商品详情API接口是指通过调用抖音开放平台提供的接口&#xff0c;获取抖店上商品的详细信息的方法。 抖店开放平台提供了一系列的接口&#xff0c;可以用于获取商品的基本信息、价格、库存、销量、评价等各种信息。以…

【前段】开发五子棋小游戏全流程

使用前端技术开发五子棋小游戏 在这篇博文中&#xff0c;我们将详细介绍如何使用HTML、CSS和JavaScript开发一个简单的五子棋小游戏。我们将展示如何初始化棋盘、处理用户交互以及实现胜负判定。特别是&#xff0c;我们将着重介绍胜负判定的逻辑实现。 完整代码我放在了这里&a…

AI应用案例:吸烟打电话行为识别推理

使用百度PaddlePaddle&#xff08;现更名为PaddlePaddle-GPU或PaddlePaddle-CPU&#xff09;框架来构建精准的人员抽烟、打电话动作识别模型&#xff0c;并将其应用于加油站监控场景&#xff0c;你可以遵循以下步骤&#xff1a; 数据准备&#xff1a; 收集抽烟和打电话行为的图…

【Linux网络编程】传输层中的TCP和UDP(UDP篇)

【Linux网络编程】传输层中的TCP和UDP&#xff08;UDP篇&#xff09; 目录 【Linux网络编程】传输层中的TCP和UDP&#xff08;UDP篇&#xff09;传输层再谈端口端口号范围划分认识知名端口号netstatiostatpidofxargs UDP协议UDP协议端格式UDP的特点面向数据报UDP的缓冲数据UDP使…

基于springboot实现大学生就业需求分析系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现大学生就业需求分析系统演示 摘要 信息数据从传统到当代&#xff0c;是一直在变革当中&#xff0c;突如其来的互联网让传统的信息管理看到了革命性的曙光&#xff0c;因为传统信息管理从时效性&#xff0c;还是安全性&#xff0c;还是可操作性等各个方面来讲…

linux系统查看服务器硬件信息

1、查看服务器型号、序列号 # dmidecode|grep "System Information" -A9 | egrep "Manufacturer|Product|Serial" 2、查看主板型号 # dmidecode |grep -A16 "System Information$" 或 dmidecode -t1 3、查看BIOS信息 # dmidecode -t bios 4、…

绘唐2跟绘唐3有什么区别

绘唐2跟绘唐3有什么区别 这款产品的最大亮点在于其高度精准的语音克隆能力&#xff0c;利用先进的模型&#xff0c;能够捕捉到用户独特的音调、音高和调制方式&#xff0c;使用户能够以前所未有的方式复制和利用自己的声音。仅需10秒钟的录制时间&#xff0c;即可实现声音的克…

c语言中数字字符串和数字互转

#include <getopt.h> #include <stdio.h> #include <stdlib.h>#define MAX_PATH 256 char filename[MAX_PATH 5]; int main(int argc, char** argv) {//数字字符串转数字const char* kk "689";int zhi atoi(kk) 8;//数字字符串转doubledoub…

zip压缩unzip解压缩、gzip和gunzip解压缩、tar压缩和解压缩

一、tar压缩和解压缩 tar [选项] 打包文件名 源文件或目录 选项含义-c创建新的归档文件-x从归档文件中提取文件-v显示详细信息-f指定归档文件的名称-z通过gzip进行压缩或解压缩-j通过bzip2进行压缩或解压缩-J通过xz进行压缩或解压缩-p保留原始文件的权限和属性–excludePATTE…

VUE H5字体在安卓手机偏上解决

安卓手机展示样式,数字偏上,展示效果如图: 项目内添加新字体,引用新字体 vue 项目需要引入字体的话, 可以移步到这篇文章(无需下载依赖包)Vue3中引入外部自定义字体 项目文件assets内创建font文件夹, 粘贴你想用的字体, 创建对应的css文件; scss代码: font-face {/* 自定义的…

CV每日论文--2024.5.15

1、Can Better Text Semantics in Prompt Tuning Improve VLM Generalization? 中文标题&#xff1a;更好的文本语义在提示微调中能否提高视觉语言模型的泛化能力? 简介&#xff1a;这篇论文介绍了一种新的可学习提示调整方法,该方法超越了仅对视觉语言模型进行微调的传统方…

mysql主从热备+keepalived+ipvsadm 部署 mysql高可用主备+负载均衡模式

1、工作原理 ipvsadm工具工作原理&#xff1a; ipvsadm是一个用于管理IPVS&#xff08;IP Virtual Server&#xff09;的命令行工具。IPVS是linux内核中的一种负载均衡技术&#xff0c;它允许将网络流量分发到多个后端服务器&#xff0c;以提高系统的可用性、性能和扩展性。而…

Android面试题之Kotlin的几种常见的类

本文首发于公众号“AntDream”&#xff0c;欢迎微信搜索“AntDream”或扫描文章底部二维码关注&#xff0c;和我一起每天进步一点点 初始化的顺序 主构造函数里声明的属性 类级别的属性赋值 init初始化块里的属性赋值和函数调用 次构造函数里的属性赋值和函数调用 延迟初始…