海量数据处理_一个40亿的数据存储,但是你只有1g内存,怎么存

海量数据处理

第一题

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

出现次数最多的

• 那么，我们能想到的方法首先有我们可以通过暴力遍历的方式，取一个ip地址，遍历文件检测该ip地址出现的次数
• 对文件中的ip地址进行排序，遍历一遍文件就可以统计出所有的ip的次数
• 用unordered_map来进行统计的方式
• 但是上面的方式，我们都没有加上文件大小这样的一个限制的条件，如果我们考虑了文件的大小的话，首先就得把暴力遍历的方式不考虑了，操作磁盘的次数太多了，效率不高；那么，现在来看排序的方式，因为我们所涉及的数据量太大了，所以考虑采用外部排序的方式—归并排序，但是归并排序对于数据量很大的情况来说，磁盘的io次数也是太多了，而且操作起来比较复杂；那么再来看一下unordered_map的方式，因为数据量其实还是很大的，所以我们考虑，先用一个unordered_map进行统计，如果空间不够的话，我们可以将该unoedered_map统计的结果保存到文件当中，然后再统计后续的结果，但是这种方式其实也是有缺陷的，比如说相同的ip地址在文件中可能出现的比较离散，不能够一次性统计出相同的ip的总次数
• 所以说，如果考虑数据的大小的话，上面的三种方式其实都是无法使用的
• 那么如何对海量数据的问题进行处理的操作呢？我们所能想到的一个方式其实就是对文件进行分割的操作，把文件分割成100份，那么一份文件数据的大小其实就是1G—那么，我们如何对文件进行分割的操作呢
• 我们首先想到的方式其实就是平均分割，然后对每个小文件中的ip地址采用unordered_map来进行统计的操作
  
• 但是，其实如果按照上面的方式来进行分割的话，和上面所给出的方式三是没有任何区别的，这种方式的缺陷其实就是相同的ip地址很有可能会分散再不同编号的文件的当中，将一个文件统计结束之后，并不能知道每条ip地址总的出现次数
• 那么最好的分割方式其实就是我们能不能想出一种方式能够让相同的ip地址放到同一个文件当中
• 我们可以采用哈希分割的方式，其实就是类似于哈希桶的方式
• 但是，其实我并不会直接给文件里面放入ip地址，因为ip地址的表示方式是点分十进制，占用的空间其实是有一些大的
  
• 当我们完成了上图的操作之后，其实相同的ip地址就已经在同一个文件当中了， 针对每个文件采用unorder_map来进行统计的操作，就可以得到该文件中每个ip地址出现的总次数，就知道该文件中出现次数最多的ip地址，按照类似的方式处理后续的文件，但是，采用这种方式对问题进行求解其实还有一个隐藏的问题其实就是可能会存在大量ip放在同一个文件当中的情况(解决方是也有，我们可以通过扩容，然后增大文件分数重新进行散列的方式来解决上面出现的问题)
  

TOP-K问题

• 按照上面所给出的方式，我们已经统计出每个ip地址出现的次数了，然后我们可以利用优先级队列来找top-k
  

第二题

假设现在有40亿个整形的数据，那么如何快去查找某个数据是否在该集合当中

• 我们能想到的方式有，我们首先是可以直接进行遍历的操作的(但是如果直接进行遍历的话，其实效率是有些低的)；还能想到的方式其实是排序+二分查找；还能想到的方式其实就是借助哈希表了，直接遍历的缺陷是速度是很慢的，而且想多来说io的次数也会稍微多一些；排序+二分查找的缺陷其实也是相对来说较慢的；哈希的方式，将40亿个数据放到哈希表里面的话，其实可以使得复杂度变成为O(1)，但是哈希表也是存在有缺陷的，缺陷其实就是数据不一定能全部放在哈希表中
• 那么，如何去解决上述的问题呢？其实解决上述问题的最佳的方式其实就是使用位图
• 位图—其实就是用一个比特位表示数据存在与否的状态信息，那么我只需要把40亿个数据映射在一张位图表里面其实就是可以的了
• 那么现在又有问题出现了，如果将40亿个整形数据加载在内存中需要多大的空间呢？以及如果对40亿个整形数据使用位图来进行映射，需要多大的空间呢？
• 将40亿数据一次性加载到内存当中大约需要16G，但是一般的计算机只有4G，所以肯定是放不下的
  
  位图的样子大概如下图所示：
  
  
• 位图比较适合用来查找数据到底存在不存在
  
• 那么，40亿个数据如果要放在位图当中的话，大概需要多大的内存空间呢
• 由下图的计算可知，我们大概需要512M的空间去将40亿个数据存放在位图当中
  
  

库中位图的使用以及测验

#pragma once 

#include<bitset>
#include<iostream>

using namespace std;

void TestBitSet()
{
	std::bitset<100> bt;  //说明我现在给出100个比特位

	//调用方法把对应的比特位置为1

	bt.set(12);  //就是把12这个比特位置为1
	bt.set(23);
	bt.set(45);
	bt.set(78);
	bt.set(90);

	cout << bt.size() << endl;
	cout << bt.count() << endl;   //返回为1的比特位的个数

	//test方法用来检测对应的比特位上的值到底是0还是1
	if (bt.test(12))
	{
		cout << "12 bit is 1" << endl;
	}
	else
	{
		cout << "12 bit is 0" << endl;
	}

	//reset的功能是将对应的比特位置0

	bt.reset(12);

	if (bt.test(12))
	{
		cout << "12 bit is 1" << endl;
	}
	else
	{
		cout << "12 bit is 0" << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

模拟实现一个位图

#pragma once 

#include<bitset>
#include<iostream>

using namespace std;
#include<vector>
namespace bite
{
	template<size_t N>
	class bitset
	{
	public:
		//给出位图的构造
		bitset()
		{
			_bst.resize((N >> 3) + 1);   //为什么要进行+1的操作呢，因为现在假如说
			//只有6个比特位的话%8是不够的，所以需要进行+1的操作，使其成为1个字节
		}

		//set将对应的比特位进行置1的操作
		bitset<N>& set(size_t pos)
		{
			size_t index = pos / 8;
			size_t which = pos % 8;

			_bst[index] |= (1 << which);

			++bit1Count;

			return *this;
		}

		//reset将对应的比特位进行置0的操作
		bitset<N>& reset(size_t pos)
		{
			size_t index = pos / 8;
			size_t which = pos % 8;

			_bst[index] &= ~(1 << which);

			--bit1Count;
			return *this;
		}

		//size返回的是总的比特位的个数
		size_t size()const
		{
			return N;
		}
		
		//返回为1的比特位个数
		size_t count()const
		{
			return bit1Count;
		}

		//test方法用来检测比特位到底是0还是1
		bool test(size_t pos)const
		{
			if (pos > N)
				return false;
			size_t index = pos / 8;
			size_t which = pos % 8;

			return _bst[index] & (1 << which);
		}
	private:
		vector<unsigned char> _bst;
		size_t bit1Count;
	};
}

void TestBitSet()
{
	bite::bitset<100> bt;  //说明我现在给出100个比特位

	//调用方法把对应的比特位置为1

	bt.set(12);  //就是把12这个比特位置为1
	bt.set(23);
	bt.set(45);
	bt.set(78);
	bt.set(90);

	cout << bt.size() << endl;
	cout << bt.count() << endl;   //返回为1的比特位的个数

	//test方法用来检测对应的比特位上的值到底是0还是1
	if (bt.test(12))
	{
		cout << "12 bit is 1" << endl;
	}
	else
	{
		cout << "12 bit is 0" << endl;
	}

	//reset的功能是将对应的比特位置0

	bt.reset(12);

	if (bt.test(12))
	{
		cout << "12 bit is 1" << endl;
	}
	else
	{
		cout << "12 bit is 0" << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

• 那么，现在其实还有一个问题就是，当你拿到了一个字节之后，你怎么才能够快速的知道一个字节中有多少个比特位为1？----其实最快的方式就是进行查表的操作
• 表格中保存了字节范围为0~255中每个字节为1的比特位的个数
  

位图的应用

• 快速查找某个数据是否在一个集合中
• 排序(如果要用位图来进行排序的操作的话，那么位图一定是不能处理有重复的数字的情况的)
• 求两个集合的交集、并集等(怎么用位图来求集合的交集，首先将两个集合的数据分别都映射到两个位图当中，讲两个位图对应的字节进行与的操作，如果对应的比特位为1的话，那么就是交集的数据)
• 操作系统中磁盘块标记

位图的变形应用

• 给定100亿个整数，设计算法找到只出现了一次的整数
  
  
  

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

• 这个题目其实是可以直接使用位图的方式来进行处理的，但是在使用位图的方式来进行处理的时候，需要注意一下内存的要求，因为只提供了1G的内存空间
• 思路—首先，我们需要将两个文件中的数据分别映射到两个位图当中，一个文件中的数据映射到位图当中，需要512M的内存空间，如果将两个文件映射到位图中的话，就需要1G的空间；然后将两个位图对应的字节进行&操作，检测&完的结果，为1的比特位对应的数就是两个文件的交集

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