海量数据处理

题目1

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数
中。【腾讯面试题】

解决方案：1，放入set或者unordered_set里面进行排序，然后查找。效率是O（N）
2，排序，然后二分查找O（N*logN）
这两种方案查找效率是非常高的，但是对内存消耗极大。因为放入set或者放入数组里面排序都要把40亿个数加载到内存中

单位换算 1G = 1024 MB
1G = 1024 * 1024 KB
1G = 1024 * 1024 * 1024byte 差不多1G=10亿个字节，光40亿个数就要占用16G的内存。显然上面两种方案无法解决问题。

位图的引入：
数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。
也就是说，我们只需要用bit位去标识数据在不在就可以。

位图的实现：

#include
#include
using namespace std;

namespace chen
{ 
	//这里应该给无符号数的最大值，因为要所有的无符号数都要映射位置
	template<size_t N> 
	class bitset
	{
	public:
		bitset()
		{
			_bt.resize(N / 8 + 1, 0); // 如果只有9个数据，也是要开两个char类型的，就算是浪费，最多是也是1个字节
		}

		void set(size_t x)  //把x所映射的位置置1，其他的不变就行
		{
			int i = x / 8;  //数组下标
			int j = x % 8;  //第几个bit位

			_bt[i] |= (1 << j); //如果当前位是1，还是1； 是0 则置0
		}

		void reset(size_t x)  // 把 x所映射的位置置0
		{
			int i = x / 8;
			int j = x % 8;

			_bt[i] &= ~(1 << j);
		}

		bool test(size_t x) // 查看x在不在位图里面
		{
			int i = x / 8;
			int j = x % 8;

			return _bt[i] & (1 << j);
		}

	private:
		vector<char> _bt;
	};
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

所以解题思路就是，用位图遍历一遍40亿个数，然后再查找。内存500M，查找效率O（1）

题目二

1， 给定100亿个整数，设计算法找到只出现一次的整数？
题目分析：有可能不出现，出现1次，出现2次及以上

题目三

位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数。
这题和题目二很相似：
只需要找出现1次和出现2次的数
改一下标记方式：
出现 0 次， 标记 00
出现1次， 标记，01，
出现2次，标记 10
出现两次及以上，标记11

template<size_t N>
	class two_bitset
	{
	public:
		void set(size_t x)
		{
			int in1 = _bs1.test(x);
			int in2 = _bs2.test(x);

			if (in1 == 0 && in2 == 0)
			{
				_bs2.set(x);
			}
			else if (in1 == 0 && in2 == 1)
			{
				_bs1.set(x);
				_bs2.reset(x);
			}
			else if(in1 == 1 && in2 == 0)
			{
				_bs1.set(x);
				_bs2.set(x);
			}
		}

		bool is_once(size_t x)
		{
			return _bs1.test(x) == 0 && _bs2.test(x) == 1;
		}

		bool is_once_or_twice(size_t x)
		{
			return is_once(x) || (_bs1.test(x) == 1 && _bs2.test(x) == 0);
		}

	private:
		bitset<N> _bs1;
		bitset<N> _bs2;
	};
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

题目4

给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
方案1：把第一个文件的整数映射到一个位图，然后再读取另一个文件的所以整数，判断在不在位图里面。
方案2：把两个文件分别放在两个位图，然后 & 放在其中一个位图，如果bit位为1就是交集。

题目5

给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出
精确算法和近似算法 （这里的query可以看成是一串字符串。）

怎么解决呢？ 用位图吗？
位图的优点是节省空间，查找效率快O（1） 缺点是只能处理整形。
为什么位图只能处理整形呢？主要原因是冲突：不同的字符串可能会转换成相同整形。

针对以上这样的问题，布隆过滤器应运而生。
布隆过滤器的实质：位图的变形改造。将一个字符串通过不同的哈希函数（一般三个）转换成多个整形，
然后这三个整形再去位图里面映射各自的位置。

为什么存在结果是存在误判的呢？ 因为你算出的3个哈希值都有可能已经被其他字符串用过了。

	struct HashBKDR
	{
		size_t operator()(const std::string& s)
		{
			size_t value = 0;
			for (auto ch : s)
			{
				value += ch;
				value *= 131;
			}

			return value;
		}
	};

	struct HashAP
	{
		size_t operator()(const std::string& s)
		{
			register size_t hash = 0;
			size_t ch;
			for (long i = 0; i < s.size(); i++)
			{
				ch = s[i];
				if ((i & 1) == 0)
				{
					hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
				}
				else
				{
					hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
				}
			}
			return hash;
		}
	};

	struct HashDJB
	{
		size_t operator()(const std::string& s)
		{
			register size_t hash = 5381;
			for (auto ch : s)
			{
				hash += (hash << 5) + ch;
			}

			return hash;
		}
	};

	template<size_t N, class K = string,class Hash1 = HashBKDR,class Hash2 = HashAP,class Hash3 = HashDJB>
	class BloomFilter
	{
	public:
		void Set(const K& key)
		{

			size_t i1 = Hash1()(key) % N;
			size_t i2 = Hash2()(key) % N;
			size_t i3 = Hash3()(key) % N;

			_bitset.Set(i1);
			_bitset.Set(i2);
			_bitset.Set(i3);
		}

		bool Test(const K& key)
		{
			size_t i1 = Hash1()(key) % N;
			if (_bitset.Test(i1) == false)      //如果一个哈希函数算出来的位置是空。那一定不存在
			{
				return false;
			}

			size_t i2 = Hash2()(key) % N;
			if (_bitset.Test(i2) == false)
			{
				return false;
			}

			size_t i3 = Hash3()(key) % N;
			if (_bitset.Test(i3) == false)
			{
				return false;
			}

			return true;
		}

	private:
		bitset<N> _bitset;
	};

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

哈希切分：

假设两个文件是A和B。每个字符串是20个字节。那每个文件的大小是200G.

切分好后，然后从A1和B1，Ai和Bi取找交集

题目6

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