位图与布隆过滤器

embedded/2024/9/23 12:46:26/

引例

给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。
思路1:排序+二分查找
思路2:哈希或红黑树
因为40亿个整数要占用16GB
102410241024Byte 约等于10亿Byte=1GB
40亿*4Byte = 16GB
16G太大放不进内存,就算我们用归并排序对文件排序,也无法对文件使用二分查找,如果一段一段的放进内存里面查找的话,还不如在读取的时候就直接把他那个数挨个查找,放在内存,所以用哈希桶和红黑存储就更加不可能了,毕竟红黑树和哈希桶存储还有导致其他的内存开销。

位图

位图就是用数据中的一个位来标识,然后用哈希的直接定址法存储那一个标识bit位来表示某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的。
逻辑结构图:
在这里插入图片描述问:如何确定我要存储的x值应该存储到哪一个位置?
x/8=x存储在那一个char里面
x%8= x存储在char的那一个位里面
问:如何在第一个char中的第5个字节置为1?
对0x01左移动5位(设为y),然后再对第一个char(设为x),x|=y,因为0|或任何数都是该数本身,而1|任何数都是1
注意,这里的为什么是左移而不是右移,要清楚左右移不是指移动的方向,而是指右移一向低地址移动,左移-向高地址移动
问:如何在第一个char中的第5个字节置为0?
对0x01左移动5位(设为y),在对y取反就会得到 1110 1111, x&=y,因为1&任何数都是该数本身,而0&任何数都是0

位图的作用

  1. 快速查找某个数据是否在一个集合中
  2. 排序 + 去重
  3. 求两个集合的交集、并集等
  4. 操作系统中磁盘块标记

代码实现:

#pragma once
#include <vector>
using namespace std;template<size_t N>
class bitset
{
public:bitset(){_bits.resize(N / 8 + 1, 0);}//置1void set(size_t x){size_t i = x / 8;size_t j = x % 8;_bits[i] |= (0x01 << j);//为什么是左移动}//置零void reset(size_t x){size_t i = x / 8;size_t j = x % 8;_bits[i] &= ~(0x01 << j);}// 查值bool test(size_t x){size_t i = x / 8;size_t j = x % 8;return _bits[i] & (0x01 << j);}private:vector<char> _bits;
};
int main()
{bitset<-1> bitset;return 0;
}

注意这里这个bitset使用了一个非类型的模版参数来传入一个N用来表述,用于在开空间的时候要开多少多大?

非类型模板参数

模板参数分类类型形参与非类型形参。
类型形参即:出现在模板参数列表中,跟在class或者typename之类的参数类型名称。
非类型形参,就是用一个常量作为类(函数)模板的一个参数,在类(函数)模板中可将该参数当成常量来使用。

引例的解决方案

把40亿存到位图中,再用位图的test去查那个无符号整数到底有没有在位图里面

位图的题目:

1. 给定100亿个整数,设计算法找到只出现一次的整数?

解答:用两个位图来标识出现的状态, 00表示一次都没有出现,01表示出现一次,如果在01状态之后再出现的话就是多次出现

2. 1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数

解答:同样用两个位图来标识出现的状态00一次都没有出现 01出现一次 10出现两次 11出现两次以上。

代码实现

#pragma once
#include "bitset.h"template<size_t N>
class TwoBitset
{
public:// 给定100亿个整数,设计算法找到只出现一次的整数?bool Test_OneTime(size_t x) const{if (bit1.test(x) && !bit2.test(x)){return true;}return false;}// 1个文件有100亿个int,1G内存,// 设计算法找到出现次数不超过2次的所有整数bool Test_NoMoreThanTwoTime(size_t x) const{if (bit1.test(x) && bit2.test(x)){return false;}return true;}void set(size_t x){if (!bit1.test(x) && !bit2.test(x)){bit1.set(x);}else if (bit1.test(x) && !bit2.test(x)){bit1.reset(x);bit2.set(x);}else if (!bit1.test(x) && bit2.test(x)){bit1.set(x);}}
private:bitset<N> bit1;bitset<N> bit2;
};

3. 给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?

解答:用两个位图来存储两个文件,然后再对两个位图进行 &预算,得出的第三个位图就是交集

代码实现

//给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?
void intersection()
{int a1[] = { 100,21,21,32,121,123,123,31,32,12,41,213,231,413312,312,213,122 };int a2[] = { -1,-1,100,21,21,21,32,32,121,123,123,31,32,1,12,4321,24,12,412, };bitset<-1> bit1;bitset<-1> bit2;for (auto val : a1){bit1.set(val);}for (auto val : a2){bit2.set(val);}for (size_t i = 0; i < -1; i++){if (bit1.test(i) && bit2.test(i)){cout << i << endl;}}
}

位图的缺点

只能映射整形,其他类型如:浮点数、string等等不能存储映射

布隆过滤器

布隆过滤器是由布隆在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构,特点是高效地插入和查询,可以用来告诉你“某样东西一定不存在或者可能存在”,它是用多个哈希函数,将一个数据映射到位图结构中。此种方式不仅可以提升查询效率,也可以节省大量的内存空间。

布隆过滤器就是用位图+多个哈希函数映射来确定字符串在不在的一个key模型,但是布隆过滤器确定一个字符串不在是准确的,在是不准确的,如下图:
我们存放不同名字的时候,会映射三个位置,如果我搜寻这字符串的时候少于三个位置就是不在的,为什么呢?因为我们是映射是通过三个函数去映射三个位置,如果只有二个位置,那么就证明我并没有存进来,这那个位置只不过是存放其他值的时候刚好冲突到该字符串映射的位置而已,而为什么说在是不准的呢?是因为这三个映射位置也有可能是其他值冲突导致碰巧映射到而已。
在这里插入图片描述
White是没有映射存放的,但是碰巧他的映射位置被其他字符串冲突了

布隆过滤器实现代码

struct BKDRHash
{size_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;hash *= 31;}return hash;}
};struct APHash
{size_t operator()(const string& s){size_t hash = 0;for (long i = 0; i < s.size(); i++){size_t ch = s[i];if ((i & 1) == 0){hash ^= ((hash << 7) ^ ch ^ (hash >> 3));}else{hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));}}return hash;}
};struct DJBHash
{size_t operator()(const string& s){size_t hash = 5381;for (auto ch : s){hash += (hash << 5) + ch;}return hash;}
};// N最多会插入key数据的个数
template<size_t N,
class K = string,
class Hash1 = BKDRHash,
class Hash2 = APHash,
class Hash3 = DJBHash>
class BloomFilter
{
public:void set(const K& key){size_t len = N*_X;size_t hash1 = Hash1()(key) % len;_bs.set(hash1);size_t hash2 = Hash2()(key) % len;_bs.set(hash2);size_t hash3 = Hash3()(key) % len;_bs.set(hash3);//cout << hash1 << " " << hash2 << " " << hash3 << " " << endl << endl;}bool test(const K& key){size_t len = N*_X;size_t hash1 = Hash1()(key) % len;if (!_bs.test(hash1)){return false;}size_t hash2 = Hash2()(key) % len;if (!_bs.test(hash2)){return false;}size_t hash3 = Hash3()(key) % len;if (!_bs.test(hash3)){return false;}// 在      不准确的,存在误判// 不在    准确的return true;}
private:static const size_t _X = 6;bitset<N*_X> _bs;
};

布隆过滤器的场景

能容忍误判的场景。比如:注册时,快速判断昵称是否使用过,假设现在要实现注册表单去判断有没有人用过昵称,就可以用到布隆过滤器,因为布隆过滤器对于不在这个结果是准确的。所以可以把昵称存放在布隆过滤器中快速过滤

哈希切分

题目1:给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法

首先,估算一下文件大小,100亿个query大概需要占用多少空间? 假设单个query,平均50byte,100亿个query是5000亿byte大概估算占用500G
用哈希函数把文件映射成小文件
在这里插入图片描述
为什么哈希切分只需要找A、B中对应i号的文件即可?
因为在哈希切分的时候,query字符串经过哈希函数的切分,会把冲突的字符串放在同一个桶里,只需要桶对桶之间进行交集计算即可

问题:因为不是平均切分,可能会出现冲突多,每个Ai,Bi小文件过大。…假设两个都是4-5G
所以要分类处理,
直接使用一个unordered set/set,依次读取文件query,插入set中
1、如果读取整个小文件query,都可以成功插入set,那么说明单个文件有大量重复的query
2、如果读取整个小文件query,插入过程中抛异常,则是单个文件有大量不同的query,换其他哈希函数,再次分割,再求交集。说明:set插入key,如果已经有了,返回false;如果没有内存,会抛bad alloc异常,剩下的都会成功。


http://www.ppmy.cn/embedded/115592.html

相关文章

注册登录案列

案列需求&#xff1a; 在主测页面中输入用户数据&#xff0c;点击注册按钮完成用户注册 实现步骤&#xff1a; 1.创建数据库表&#xff0c;Mysql代码如下&#xff1a; CREATE TABLE tb_user( id int primary key auto_increment, username VARCHAR(32), password VARCHAR(3…

Linux:vim编辑技巧

命令模式 光标跳转 输入18&#xff0c;再输入G&#xff0c;可以跳转到18行。 复制、粘贴、删除 P是往上一行粘贴 小写u可以撤销 查找/撤销/保存 大写U可能失效&#xff0c;用CTRLr 末行模式 保存/退出/文件操作 字符串替换 开关参数的控制

python绘制弦图-科研作图

一、背景 弦图以其直观、精美的展示方式受到越来越多人的关注&#xff0c;它不仅能够有效展示两个变量之间的联系&#xff0c;还能同时展现多个变量间的复杂互动&#xff0c;本文将通过Python语言中的pycirclize库&#xff0c;带你深入了解如何绘制弦图。 弦图是一种圆…

两台虚拟机之分布式部署

Apache2 和 PHP 安装 在虚拟机1上执行以下步骤: 更新系统包列表: sudo apt update安装 Apache2: sudo apt install apache2 -y安装 PHP 及其扩展: sudo apt install php libapache2-mod-php php-mysql配置Apache和PHP sudo nano /etc/apache2/mods-enabled/dir.conf#…

基于Springboot的医疗健康助手开题报告

文未可获取一份本项目的java源码和数据库参考。 一&#xff0e;选题意义, 研究现状,可行性分析 选题意义&#xff1a;随着科技的高速发展&#xff0c;人们的生活水平也正在稳步提高&#xff0c;解决温饱问题以后&#xff0c;广大人民群众也越来越注重自己的身体健康&#xff0…

后台数据管理系统 - 项目架构设计-Vue3+axios+Element-plus(0920)

十三、文章分类页面 - [element-plus 表格] Git仓库&#xff1a;https://gitee.com/msyycn/vue3-hei-ma.git 基本架子 - PageContainer 功能需求说明&#xff1a; 基本架子-PageContainer封装文章分类渲染 & loading处理文章分类添加编辑[element-plus弹层]文章分类删除…

在mac中如何使python3作为默认版本

在系统中同时安装了Python 2和Python 3&#xff0c;且二者的执行文件分别是python和python3。如果你执行python --version看到的是Python 2的版本&#xff0c;而执行python3 --version看到的是Python 3的版本&#xff0c;这表明系统能够正确区分两个版本。 如果你希望使用Pyth…

力扣(leetcode)每日一题 2374 边积分最高的节点

题干 2374. 边积分最高的节点 - 力扣&#xff08;LeetCode&#xff09; 给你一个有向图&#xff0c;图中有 n 个节点&#xff0c;节点编号从 0 到 n - 1 &#xff0c;其中每个节点都 恰有一条 出边。 图由一个下标从 0 开始、长度为 n 的整数数组 edges 表示&#xff0c;其中…