当前位置：首页 > article >正文

C++练级计划-＞《海量数据处理》面试题

article 2024/11/24 13:58:49

一.位图

二.布隆过滤器

三.哈希切割

海量数据：顾名思义：数据量很大，正常的方法例如哈希无法装下这么多数据时，要使用别的结构来解决

下面是三种海量处理思想：有三个问题，深度层层递增

一.位图

题目1：给定100亿个整数，要求找出只出现一次的整数。

100亿个整数如果我们用hash来存一个整数4个字节。总共400亿个字节。换算下来就是40g内存。目前的普通游戏笔记本内存是16g。所以这个内存要求太大了。所以就可以使用位图了

首先数字可能出现的状态有：1.没出现过 2.出现1次（要找的） 3.出现2次以上的

因为是100亿个整数：整数int的范围是4294967295，所以就我们开辟两个4294967295大小的位图就可以了两个4294967295大小的位图的大小只有1G，一瞬间小了40倍。

下面先看代码：

#include <iostream>
#include <vector>
#include <assert.h>
#include <bitset>
using namespace std;

int main()
{
	//此处应该从文件中读取100亿个整数
	vector<int> v{ 12, 33, 4, 2, 7, 3, 32, 3, 3, 12, 21 };
	//在堆上申请空间
	bitset<4294967295>* bs1 = new bitset<4294967295>;
	bitset<4294967295>* bs2 = new bitset<4294967295>;
	for (auto e : v)
	{
		if (!bs1->test(e) && !bs2->test(e)) //00->01
		{
			bs2->set(e);
		}
		else if (!bs1->test(e) && bs2->test(e)) //01->11
		{
			bs1->set(e);
		}
		else if (bs1->test(e) && !bs2->test(e)) //11->11
		{
			//不做处理
		}
		else //11（理论上不会出现该情况）
		{
			assert(false);
		}
	}
	for (size_t i = 0; i < 4294967295; i++)
	{
		if (!bs1->test(i) && bs2->test(i)) //找到01，即只有bs2为1的点
			cout << i << endl;
	}
	return 0;
}

思路是：同时遍历这100亿个整数，当这个数第一次出现时把第二个位图的这个整数的比特位置1.

这个数第二次出现时就把第一张位图的这个整数的比特位也置为1，此时两张位图的这个整数都是1

之后同时遍历两个位图，找出只有第二个位图为1的数输出即可。

题目二：给两个文件，分别有100亿个整数，我们只有1G的内存，怎么找到两个文件的交集

这个题目二有了题目一的铺垫我们也知道要用位图了。这里提供两个方案：

1.方案一：只用一个位图（512M）

思想：遍历第一个文件，将出现的数字映射到位图上，之后再遍历第二个文件，此时如果当前数字的映射只要为1，输出这个数字即可。

2.方案二：使用两个位图（2*512M）

思想：同时遍历两个文件：第一个文件的数字映射到位图1，第二个文件映射到位图2.

C++中位图重载了部分位运算的运算符，这里我们使用与（ & ）操作（二者都为1才为1，其中一个为0则为0），然后把结果给到其中一个位图即可，此时也算是找到了交集。

题目三：一个文件有100亿个整数，1G内存，设计算法找到出现次数不超过2次的所有整数

这里和题目一是类似的：题目一要求的是：只出现过一次的，现在变成了2次以下那现在可能出现的情况就如下：

1.这个数字没出现过

2.这个数字出现过1次（要找的）

3.这个数字出现过2次（要找的）

4.这个数字出现超过2次。

思路：题目一用两个位图：这里我们依然可以用2个位图因为出现两次，所以我们可以一个整数使用两个比特位（一个位图使用一个），00->01->10->11；00代表没出现，01代表出现一次，10代表出现两次，11代表出现超过两次，最后我们在遍历两个位图找到01 10的情况即可。

如果出现要求出现次数更多：那就加比特位或者加位图即可

代码如下：

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

int main()
{
	vector<int> v{ 12, 33, 4, 2, 7, 3, 32, 3, 3, 12, 21 };
	//在堆上申请空间
	bitset<4294967295>* bs1 = new bitset<4294967295>;
	bitset<4294967295>* bs2 = new bitset<4294967295>;
	for (auto e : v)
	{
		if (!bs1->test(e) && !bs2->test(e)) //00->01
		{
			bs2->set(e);
		}
		else if (!bs1->test(e) && bs2->test(e)) //01->10
		{
			bs1->set(e);
			bs2->reset(e);
		}
		else if (bs1->test(e) && !bs2->test(e)) //10->11
		{
			bs2->set(e);
		}
		else //11->11
		{
			//不做处理
		}
	}
	for (size_t i = 0; i < 4294967295; i++)
	{
		if ((!bs1->test(i) && bs2->test(i)) || (bs1->test(i) && !bs2->test(i))) //01或10
			cout << i << endl;
	}
	return 0;
}

二.布隆过滤器

先介绍一下什么是布隆过滤器：通常我们的游戏名字都是字符，我们起名字时会有一个名字重复查询，我们在查询时在数据量少时用hash就可以，但是数据量大了以后hash需要的内存就太多了，因为我们判断一个用户是否存在，我们只要知道存在情况，而具体数据无所谓。

布隆过滤器就是把字符串转换为整数在存到位图里。但是字符串的判重是有难度的，因为一个字符可能重的特别多就像，有油又三个字的拼写都是you。此时就都是重复的，所以布隆过滤器使用了三个hash函数（不同的数据转换为整数的函数算法），计算出三个位置，把三个位置都变为1，只有三个1都存在此时才是重复的。所以布隆过滤器是可能误判的。