位图、布隆过滤器、海量数据处理

文章目录

  • 位图
  • 布隆过滤器
  • 海量数据处理

正文开始前给大家推荐个网站，前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。

位图

概念：所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。但是位图只能判断正整数的在不在问题。
我们用一个比特位的0/1代表这个数的在不在。
在这里插入图片描述
我们可以看到，我们直接开最大数个比特位+1就可以把所有的数在不在映射到位图中，我们可以用char的数组也可以用int的数组，但是用位图的情况数据一般都比较大，我们综合考虑，用int的数组，一个位置可以表示32个比特位。实现比较简单。
代码有注释。

template <size_t N>
class bitset
{
public:
	bitset()
	{
		//N表示几个比特位，所以开空间需要/32,+1是为了方式向下取整导致空间少开
		_bits.resize(N / 32 + 1);
	}
	void set(const int& x)
	{
		// /32计算在数组中的第几个位置
		int i = x / 32;
		// %32计算在第几个比特位
		int j = x % 32;
		//将数组第i个元素的第j个比特位置为1
		_bits[i] |= (1 << j);
	}

	void reset(const int& x)
	{
		int i = x / 32;
		int j = x % 32;
		//将数组第i个元素的第j个比特位置为0
		_bits[i] &= ~(1 << j);
	}

	bool test(const int& x)
	{
		int i = x / 32;
		int j = x % 32;
		//将数组第i个元素的第j个比特位置为0就返回fasle，非0就返回true
		return _bits[i] & (1 << j);
	}
private:
	vector<int> _bits;
};

位图的应用

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

布隆过滤器

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

在这里插入图片描述
查找
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。
注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，也有可能不存在，因为有些哈希函数存在一定的误判。
比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。

删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。
想要支持删除的话就需要使用引用计数，将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。

缺陷：

  1. 无法确认元素是否真正在布隆过滤器中
  2. 存在计数回绕

布隆过滤器的实现
我们会用到位图这个结构来封装布隆过滤器。

struct BKDRHash
{
	size_t operator()(const string& s)
	{
		// BKDR
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}
};
struct APHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (long i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ s[i] ^ (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;
	}
};
template<size_t N,
	size_t X = 5,
	class K = string,
	class HashFunc1 = BKDRHash,
	class HashFunc2 = APHash,
	class HashFunc3 = DJBHash>
class BloomFilter
{
public:
	void Set(const K& key)
	{
		size_t len = X * N;
		size_t index1 = HashFunc1()(key) % len;
		size_t index2 = HashFunc2()(key) % len;
		size_t index3 = HashFunc3()(key) % len;
		_bs.set(index1);
		_bs.set(index2);
		_bs.set(index3);
	}
	bool Test(const K& key)
	{
		size_t len = X * N;
		size_t index1 = HashFunc1()(key) % len;
		if (_bs.test(index1) == false)
			return false;
		size_t index2 = HashFunc2()(key) % len;
		if (_bs.test(index2) == false)
			return false;
		size_t index3 = HashFunc3()(key) % len;
		if (_bs.test(index3) == false)
			return false;
		return true; // 存在误判的
	}
	// 不支持删除，删除可能会影响其他值。
	void Reset(const K& key);
private:
	bitset<X* N> _bs;
};

优点

  1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
  2. 哈希函数相互之间没有关系，方便硬件并行运算
  3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
  4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
  5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
  6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

缺点

  1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
  2. 不能获取元素本身
  3. 一般情况下不能从布隆过滤器中删除元素
  4. 如果采用计数方式删除，可能会存在计数回绕问题

海量数据处理

海量数据一般数据都比较到，直接放内存肯定是放不下的，所以我们就要使用位图或者布隆过滤器来尝试着解决一下。

位图应用

  1. 给定100亿个整数，设计算法找到只出现一次的整数？
  2. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

这两个题的思路都是一样的，只使用一个位图是没法解决的，我们需要用位图的变形，使用两个位图，即一个数据映射两个位置，在不同的位图中,两个比特位可以标识4中不同的状态，出现0次(00),出现1次(01)出现2次(10)还有其他(11).

template <size_t N>
class two_bitset
{
public:
	void set(const int& x)
	{
		//00->01
		if (_b1.test(x) == false && _b2.test(x) == false)
		{
			_b2.set(x);
		}
		else
		{
			//01->10
			if (_b1.test(x) == false && _b2.test(x) == true)
			{
				_b1.set(x);
				_b2.reset(x);
			}
			else
			{
				//10->11
				if (_b1.test(x) == true && _b2.test(x) == false)
				{
					_b2.set(x);
				}
			}
		}
	}

	void print()
	{
		for (size_t i = 0; i < N; i++)
		{
			if (_b1.test(i) == false && _b2.test(i) == true)
			{
				cout << "1->" << i << endl;
			}

			if (_b1.test(i) == true && _b2.test(i) == false)
			{
				cout << "2->" << i << endl;
			}
		}
	}
private:
	bitset<N> _b1;
	bitset<N> _b2;
};
  1. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

我们同样可以使用2个位图，每个文件映射一个位图，然后两个位图都是1的位就是交集。虽然有100亿个数据，我们还是只开42亿多个就可以了，因为在计算机中能表示的整数只有42亿多个，直接开bitset<-1>就可以，因为-1会被转化为size_t类型的。

布隆过滤器

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

近似算法就是直接使用布隆过滤器映射一个文件，然后读取另一个文件判断是否在布隆过滤器中。
精确算法的话，还是需要先把一个文件映射到布隆过滤器，然后读取另一个文件，判断该值在过滤器中的情况，如果不在，就说明一定不定交集，但是如果判断在的话，我们不能确定到底是在还是不在，所以需要遍历文件，得到准确情况。也可以使用哈希分割的思想，使用同一个哈希函数对文件A和文件B的元素操作，将两个大文件分切切分成相等份的小文件，然后在内存中找交集。

哈希分割
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？

只有一个文件要要求出现次数最多的，光凭位图或者布隆过滤器时无法解决的。
由于文件log file的大小超过100GB，考虑使用相同的Hash函数将文件log file切分成200个小文件。使得每个小文件能够以合适的大小（不影响效率）加载到内存中,因为使用的是相同的Hash函数，所以相同的IP地址一定会被分到同一个文件，依次将每个小文件加载到内存中， 然后用map容器统计出每个小文件中各个 IP 地址出现的次数，然后比对各个小文件中出现次数最多的 IP 地址，最后能得到出现次数最多的IP。

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【Spring】08 BeanNameAware 接口

【Spring】08 BeanNameAware 接口

文章目录 1. 简介2. 作用3. 使用3.1 创建并实现接口3.2 配置 Bean 信息3.3 创建启动类3.4 启动 4. 应用场景总结 Spring 框架为开发者提供了丰富的扩展点&#xff0c;其中之一就是 Bean 生命周期中的回调接口。本文将聚焦于其中的一个接口 BeanNameAware&#xff0c;介绍它的作…
阅读更多...
深度学习中的预测图片中的矩形框、标签、置信度分别是什么意思。

深度学习中的预测图片中的矩形框、标签、置信度分别是什么意思。

问题描述&#xff1a;深度学习中的预测图片中的矩形框、标签、置信度分别是什么意思。 问题解答&#xff1a; 目标框&#xff08;Bounding Box&#xff09;&#xff1a; 描述目标位置的矩形边界框。 类别标签&#xff1a; 表示模型认为目标属于哪个类别&#xff08;例如&#…
阅读更多...
opencv 十六 python下各种连通域处理方法（按面积阈值筛选连通域、按面积排序筛选连通域、连通域分割等方法）

opencv 十六 python下各种连通域处理方法（按面积阈值筛选连通域、按面积排序筛选连通域、连通域分割等方法）

本博文基于python-opencv实现了按照面积阈值筛选连通域、按照面积排序筛选topK连通域、 连通域细化（连通域骨架提取）、连通域分割（基于分水岭算法使连通域在细小处断开）、按照面积排序赛选topK轮廓等常见的连通域处理代码。并将代码封装为shapeUtils类，在自己的python代码…
阅读更多...
[Verilog] 设计方法和设计流程

[Verilog] 设计方法和设计流程

主页&#xff1a; 元存储博客 文章目录 1. 设计方法2. 设计流程 3 Vivado软件设计流程总结 1. 设计方法 Verilog 的设计多采用自上而下的设计方法&#xff08;top-down&#xff09;。设计流程是指从一个项目开始从项目需求分析&#xff0c;架构设计&#xff0c;功能验证&#…
阅读更多...
openEuler商业化进展可观：累计装机量超610万套，市场持续扩容

openEuler商业化进展可观：累计装机量超610万套，市场持续扩容

12月15日至16日&#xff0c;以“崛起数字时代&#xff0c;引领数智未来”为主题的操作系统大会&#xff06;openEuler Summit 2023在北京国家会议中心举办。大会旨在汇聚全球产业界创新力量&#xff0c;构筑坚实的基础软件根基&#xff0c;推动基础软件技术持续创新&#xff0c…
阅读更多...
Redis设计与实现之整数集合

Redis设计与实现之整数集合

目录 一、内存映射数据结构 二、整数集合 1、整数集合的应用 2、数据结构和主要操作 3、intset运行实例 创建新intset 添加新元素到 intset 添加新元素到 intset&#xff08;不需要升级&#xff09; 添加新元素到 intset (需要升级) 4、升级 升级实例 5、关于升级 …
阅读更多...
帆软FCRP模拟题

帆软FCRP模拟题

制作步骤可见此博主&#xff1a;https://blog.csdn.net/Ipkiss_Yongheng/article/details/125594366 完成文件下载&#xff1a;【免费】帆软FCRP官网模拟题代码资源-CSDN文库
阅读更多...
大创项目推荐 垃圾邮件(短信)分类算法实现 机器学习 深度学习

大创项目推荐 垃圾邮件(短信)分类算法实现 机器学习 深度学习

文章目录 0 前言2 垃圾短信/邮件 分类算法 原理2.1 常用的分类器 - 贝叶斯分类器 3 数据集介绍4 数据预处理5 特征提取6 训练分类器7 综合测试结果8 其他模型方法9 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 垃圾邮件(短信)分类算…
阅读更多...
5个创建在线帮助文档的好方法！

5个创建在线帮助文档的好方法！

在线帮助文档是企业为用户提供支持服务的重要工具&#xff0c;它能够帮助用户更好地了解和使用产品&#xff0c;提高用户体验。然而&#xff0c;创建一份优秀的在线帮助文档需要掌握一定的技巧和方法。接下来就介绍一下创建在线帮助文档的5个好方法&#xff0c;帮助企业更好地为…
阅读更多...
day05-报表技术-图形报表

day05-报表技术-图形报表

1、图表报表简介 ​ 在大数据时代&#xff0c;人们需要对大量的数据进行分析&#xff0c;帮助用户或公司领导更直观的察觉差异&#xff0c;做出判断&#xff0c;减少时间成本&#xff0c;而在web项目中除了表格显示数据外&#xff0c;还可以通过图表来表现数据&#xff0c;这种…
阅读更多...
一维数组的定义

一维数组的定义

什么是数组&#xff1f; &#xff08;1&#xff09;数组是具有一定顺序关系的若干变量的集合&#xff0c;组成数组的各个变量统称为数组的元素 &#xff08;2&#xff09;数组中的各元素的数据类型要求相同&#xff0c;用数组名和下标确定&#xff0c;数组可以是一维的&#…
阅读更多...
【java】数组遍历的方式：

【java】数组遍历的方式：

文章目录 1、for循环遍历&#xff1a;2、forEach循环&#xff08;增强for循环&#xff09;&#xff1a;3、while循环 或者 do while循环&#xff1a;4、利用Arrays工具类当中的toString()&#xff1a;5、流式遍历:6、使用Arrays.asList()和forEach()方法进行遍历: 1、for循环遍…
阅读更多...
java-IO流

java-IO流

File类 引入 【1】文件&#xff0c;目录&#xff1a; 文件&#xff1a; 内存中存放的数据在计算机关机后就会消失。要长久保存数据&#xff0c;就要使用硬盘、光盘、U 盘等设备。为了便于数据的管理和检索&#xff0c;引入了“文件”的概念。一篇文章、一段视频、一个可执…
阅读更多...
博途WinCC专业版C/S架构入门指南

博途WinCC专业版C/S架构入门指南

WinCC Professional V16 支持客户机/服务器架构&#xff0c;但目前只支持单个服务器或单对冗余服务器/多个客户机的模式&#xff0c;还不能支持像WinCC V7.5 SP1中的多个服务器/多个客户机的分布式架构。 博途工控人平时在哪里技术交流博途工控人社群 博途工控人平时在哪里技…
阅读更多...
C语言 （指针）输入三个整数，由小到大输出

C语言 （指针）输入三个整数，由小到大输出

目录 1问题&#xff1a; 2代码&#xff1a; 3运行结果&#xff1a; 4总结&#xff1a; 1问题&#xff1a; 输入3个整数a,b,c,要求按由小到大的顺序将他们输出。用函数和指针实现》 2代码&#xff1a; #include<stdio.h> int main() {void exchange(int *q1,int *q2…
阅读更多...
Cython（将Python编译为so）

Cython（将Python编译为so）

环境 先配一下环境&#xff0c;我使用的是python3.8.5 pip install Cython 编译过程 我们准备一个要编译的文件 test.py def xor(input_string): output_string "" for char in input_string: output_string chr(ord(char) ^ 0x66) return output_string …
阅读更多...
eNSP小实验---（简单混合）

eNSP小实验---（简单混合）

实验目的&#xff1a;实现vlan10 vlan20 172网段用户互访 1.拓扑图 2.配置 PC1 其它同理 SW4 <Huawei> <Huawei>u t m Info: Current terminal monitor is off. <Huawei>sys <Huawei>sys Enter system view, return user view with CtrlZ. [Hua…
阅读更多...
Dockerfile：创建镜像，创建自定义的镜像。

Dockerfile：创建镜像，创建自定义的镜像。

Docker的创建镜像的方式&#xff1a; 基于已有镜像进行创建。 根据官方提供的镜像源&#xff0c;创建镜像&#xff0c;然后拉起容器。是一个白板&#xff0c;只能提供基础的功能&#xff0c;扩展性的功能还是需要自己定义&#xff08;进入容器进行操作&#xff09; 基于模板进…
阅读更多...
返回零长度的数组或集合，而不是null

返回零长度的数组或集合，而不是null

返回零长度的数组或集合而不是 null 是一种良好的编程实践&#xff0c;可以提高代码的可靠性和可读性。以下是一个例子&#xff0c;展示了返回零长度的数组或集合的情况&#xff1a; import java.util.ArrayList; import java.util.List;public class StudentManager {private…
阅读更多...
【KMP】【判断是否是重复子字符串】Leetcode 459 重复的子字符串

【KMP】【判断是否是重复子字符串】Leetcode 459 重复的子字符串

【KMP】【判断是否是重复子字符串】Leetcode 459 重复的子字符串 解法1 拼接字符串-掐头去尾后判断是否含有原字符串解法2 KMP——重复子串的最小单位是这个字符串里的最长相等前后缀所不包含的子串解法3 暴力解法KMP ---------------&#x1f388;&#x1f388;题目链接&…
阅读更多...
最新文章

Copyright @ 2022~2023