海量数据处理

前言

        对于内存中无法处理的海量数据，如何处理，这里有一些问题和解觉思路分享给大家。

目录

1.哈希切割的应用

2.位图的应用

3.布隆过滤器的应用

---

1.哈希切割的应用

        问题： 

        给出一个超过100G大小的logfile，log中存储着IP地址，设计算法找到出现次数最多的IP地址？与上面的条件相同，如何找到top K的IP。

        解决思路： 

        分析：100G的logfile，直接在内存中查找是，数据是无法一次性加载到内存中的，所以我们需要创建1000个小文件，并对小文件从0开始按照顺序编号，将大文件中的数据分到小文件中，这样就可以将小文件的数据加载单内存中，然后使用map进行存储，在定义一个pair max来保存IP地址出现最多的情况，每次加载完小文件都要更新max,这样基本就可以解决这个问题了，但是在这里还有其他的问题，如果相同的IP地址出现在不同的小文件中，那么这样统计的结果就是无效的，如何保证相同的IP地址出现在同一个小文件中呢，这里就要使用哈希切分的方法来将IP地址放到小文件中了，取出大文件的IP地址，使用哈希字符串函数，将IP地址分类，保证相同的IP地址出现在同一个小文件中。int i = HashStr("IP")  % 1000;结果要对1000取余数防止超过小文件编号的范围。 

        如果要求topK个出现次数最多的IP地址，可以建一个小堆，每次加载完一个小文件，就在map中找有没有比堆顶出现次数多的IP地址，有的话，替换堆顶的IP地址，然后对堆进行向下调整就行了。

2.位图的应用

        问题1：

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

        解决思路： 

        如果单纯用位图是无法解决这个问题的因为，位图只有两种状态有或者没有，而上述的要求中需要出现三种状态，出现0次，出现1，出现多次，所以我们需要两个位图来存储数据，00表示出现0次，01表示出现一次，10表示出现一次以上。然后对100亿个整数统计它们出现的次数即可。

#include
using namespace std;
namespace qyy
{
 
	class BitSet//位图
	{
	public:
		BitSet(size_t N)
		{
			_array.resize(N / 32 + 1, 0);//开空间并初始化为全0
			int _num = 0;//位图中保存的数据个数
		}
		void set(int x)//将数据x加入位图
		{
			int index = x / 32;//求出x在第几个位置
			int pos = x % 32;//求出是x是第几位
			_array[index] |= (1 << pos);//将数据x加入到位图中
			++_num;
		}
		void reset(int x)//将位图中的x取消
		{
			int index = x / 32;//求出x在第几个位置
			int pos = x % 32;//求出是x是第几位
			_array[index] &= ~(1 << pos);//将数据从位图中取出
			--_num;
		}
		bool test(int x)//判断x是否在位图中
		{
			int index = x / 32;//求出x在位图中第几个位置
			int pos = x % 32; //求出是x是第几位
			return _array[index] & (1 << pos);//判断数据x是否在位图中
		}
		size_t Count()
		{
			return _num;
		}
	private:
		vector<int> _array;
		size_t _num;//保存位图中存储的数据个数
	};
	class DoubleBit//算法
	{
	public:
		void set(size_t  x)
		{
			//00 出现0次的情况
			if ((_bit1.test(x)) == false && (_bit2.test(x) == false))
			{
				//设置为01
				_bit1.reset(x);
				_bit2.set(x);
			}
			//01 出现一次的情况
			else if ((_bit1.test(x) == false) && (_bit2.test(x) == true))
			{
				//设置为出10
				_bit1.set(x);
				_bit2.reset(x);
			}
			//10 不用处理
		}
 
		//查找只出现一次的数:01
		bool test(size_t x)
		{
			if ((_bit1.test(x) == false) && (_bit2.test(x) == true))
			{
				return true;
			}
		}
	private:
		BitSet _bit1;//用两个位图来表示三种状态:00,01,10
		BitSet _bit2;
	};
}

        问题2：

        给两个文件，分别有100亿个整数，我们只有1G内存如何找出两个文件的交集？ 

        解决思路： 

        解法1：将其中一个文件存到位图，这个位图要开辟整形的最大个数个空间，然后将第一个文件中的所有整数都加入到位图中，然后读取第二个文件中的整数判断它在不在位图中，如果在位图中就说明这个数是两个文件所共有的，找出全部的这样的数，就是两个文件的交集 ，消耗空间512M。

        解法2：将文件1中的整数映射到位图1中，将文件2中的整数映射到位图2中，然后将两个位图中的数，按位与结果就是两个文件的交集。

        问题3：

        在一个文件中有100亿个整数，但是只有1G的内存，设计算法出现次数不超过2次的所有整数。

        解决思路：  

        这是问题1的变形，题目要求找出出现次数不超过两次的所有整数，也就是出现一次或者两次的所有整数，这里也需要两个位图，用来表示4种状态，00：出现0次的整数,01：出现1次的整数,10：出现2次的整数,11：出现两次以上的整数。然后对100亿个整数统计它们出现的次数即可。 

//关于位图的代码在上面
class DoubleBit//算法
	{
	public:
		void set(size_t  x)
		{
			//00 出现0次的情况
			if ((_bit1.test(x)) == false && (_bit2.test(x) == false))
			{
				//设置为01
				_bit1.reset(x);
				_bit2.set(x);
			}
			//01 出现一次的情况
			else if ((_bit1.test(x) == false) && (_bit2.test(x) == true))
			{
				//设置为出10
				_bit1.set(x);
				_bit2.reset(x);
			}
			//10 出现两次的情况
			else if ((_bit1.test(x) == true) && (_bit2.test(x) == false))
			{
				//设置为11
				//_bit1.set(x);
				_bit2.set(x);
			}
		}
 
		//查找只出现一次和两次的数:01 和10
		bool test(size_t x)
		{
			if ((_bit1.test(x) == false) && (_bit2.test(x) == true) || (_bit1.test(x) == true) && (_bit2.test(x) == false))
			{
				return true;
			}
		}
	private:
		qyy::BitSet _bit1;//用两个位图来表示四种状态:00,01,10，11
		qyy::BitSet _bit2;
	};

3.布隆过滤器的应用

        问题1：

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

        思路：

        分析：query一般是sql查询语句，或者网络请求的url，100亿个query占多少个空间呢？假设平均一个query占30-60个byte，100亿个 query大约占300-600G的空间。

        方案1：将第一个文件的query映射到一个布隆过滤器中，读取第二个文件中的query，判断在不在布隆过滤器中，所有在布隆过滤器中的query就是两个文件的交集。

        但是方案1有一些缺陷：虽然交集不会遗漏，但是某些不是交集的query可能会被判为是在交集中。

        这两个文件都很大，大概在300-600G之间，也没有合适的数据结构能直接精确的找出交集。文件很大都不能放到内存中，那么我们可以将大文件切分成很多的小文件，将小文件加载到内存中。

         方案2：切分成每个小文件中的数据都可以放到内存中，这里的文件大概300-600G，切分成1000份，每个小文件差不多300-600M，这里有1G 的内存是完全够用的。

        如果是将文件平均切分放到内存中存储在一个set中，那么B0-B999的数据都要和A0比较，依次类推，A1存放到内存中后，也要和B0-B999的数据进行比较A2也是。如图：

        这样的话读取到内存中的每个文件Ax都要和B0到B999进行比较来求交集，虽然这样比起来暴力比较已经快很多了。但是有没有优化的空间呢？

        是有的，我们对文件切割的时候可以使用哈希切割，使用字符串哈希函数，将大文件中的query分别存储到不同的小文件中，int  i  =  Hashstr（query） %1000,i 是 多少，query就进入哪个第Ai/Bi个文件中。对于两个大文件采取相同的处理方法，这样做的目的就是使得相同的query一定编号相同的Ai和Bi的小文件中，所以接下来比较的时候，只需要编号相同的Ai文件和Bi文件进行比较找交集就可以了。 

        问题2：

        如何扩展BloomFilter使得它支持删除元素的操作  

         思路：

        将布隆过滤器中按照 按位存储的数据的方式换成按照计数器的方式存储数据，如果插入数据，就让数据按照哈希映射位置的计数器++，如果删除某个数，就让对应的位置的计数器--， 布隆过滤器是按照位来存储数据的，如果改成按照计数器来存储数据的话，那么它节省空间的优势就会大大降低，因为计数器不可能只给几个位，起码要给1个或者两个字节，这样的话，占相同空间的布隆过滤器就只能存储它原来八分之一的数据了，而且给1个字节的空间来作为计数器还是有风险的可能不够。要是给计数器更大的空间那么布隆过滤器存储数据的能力就会进一步降低。