1. 处理海量数据问题的四种方式

• 分治

  • 基本上处理海量数据的问题，分治思想都是能够解决的，只不过一般情况下不会是最优方案，但可以作为一个baseline，可以逐渐优化子问题来达到一个较优解。传统的归并排序就是分治思想，涉及到大量无法加载到内存的文件、排序等问题都可以用这个方法解决。

  • 适用场景:数据量大无法加载到内存

有一个文件，有大量的整数，50亿个整数，内存限制400M，找到文件中重复的元素，重复的次数。
1G=1024x1024x1024=10 7374 1824 大约10亿
50亿整数占用的内存大约= 50/10 G *4 (一个整数四字节) = 20G
分治法的思想：大文件划分成小文件，使得每个小文件能够加载到内存中，求出对应的重复的元素，把结果写入到一个存储重复元素的文件中。
那么小文件的个数 = 20G/400M 大约  52个小文件：
data0.txt
.....
data51.txt

便利大文件的元素，把每个元素根据哈希映射函数，放到对应序号的小文件中 :data %52 = file_index

• 哈希(Hash)

  • 个人感觉Hash是最为粗暴的一种方式，但粗暴却高效，唯一的缺点是耗内存，需要将数据全部载入内存。

  • 适用场景:快速查找，需要总数据量可以放入内存

int main()
{
	/* 
	假设这个vector中，放了原始的待查重的数据
	为了让程序更快的运行出结果，此处缩小了数据量
	*/
	vector<int> vec;
	for (int i = 0; i < 100000; ++i)
	{
		vec.push_back(rand());
	}

	// 用哈希表解决查重，因为只查重，所以用无序集合解决该问题
	unordered_set<int> hashSet;
	for (int val : vec)
	{
		// 在哈希表中查找val
		auto it = hashSet.find(val);
		if (it != hashSet.end())
		{
			cout << *it << "是第一个重复的数据" << endl;
			break; // 如果要找所有重复的数字，这里就不用break了
		}
		else
		{
			// 没找到
			hashSet.insert(val);
		}
	}

	return 0;
}

• bit(位集或BitMap)

  • 位图法，就是用一个比特位（0或者1）来存储数据的状态，比较适合状态简单，数据量比较大，要求内存使用率低的问题场景。位图法解决问题，首先需要知道待处理数据中的最大值，然后按照size = （maxNumber / 8）(byte)+1的大小来开辟一个char类型的数组，当需要在位图中查找某个元素是否存在的时候，首先需要计算该数字对应的数组中的比特位，然后读取值，0表示不存在，1表示已存在。在下面的问题中看具体应用。

    位图法有一个很大的缺点，就是数据没有多少，但是最大值却很大，比如有10个整数，最大值是10亿，那么就得按10亿这个数字计算开辟位图数组的大小，太浪费内存空间

  • 适用场景：可进行数据的快速查找，判重

  • 技能链接:布隆过滤器使用的性能误区

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
int main()
{
	/* 
	假设这个vector中，放了原始的待查重的数据
	为了让程序更快的运行出结果，此处缩小了数据量
	*/
	vector<int> vec;
	for (int i = 0; i < 100000; ++i)
	{
		vec.push_back(rand());
	}

	// 用位图法解决问题
	typedef unsigned int uint;
	uint maxNumber = 1000000000;
	int size = maxNumber / 8 + 1;
	char *p = new char[size]();

	for (uint i = 0; i < vec.size(); ++i)
	{
		// 计算整数应该放置的数组下标
		int index = vec[i] / 8; 
		// 计算对应字节的比特位
		int offset = vec[i] % 8;
		// 获取相应比特位的数值
		int v = p[index] & (1 << offset);
		if (0 != v)
		{
			cout << vec[i] << "是第一个重复的数据" << endl;
			break; // 如果要找所有重复的数字，这里就不用break了
		}
		else
		{
			// 表示该数据不存在，把相应位置置1，表示记录该数据
			p[index] = p[index] | (1 << offset);
		}
	}
	delete[]p;
	return 0;
}

• 堆(Heap)

  • 堆排序是一种比较通用的TopN问题解决方案，能够满足绝大部分的求最值的问题，读者需要掌握堆的基本操作和思想。

  • 适用场景:处理海量数据中TopN的问题(最大或最小)，要求N不大，使得堆可以放入内存

  • 技能链接:排序算法-Heap排序

关于堆：堆排序算法_LIJIWEI0611的博客-CSDN博客

求top k问题
top k问题大致分为两类：
1.在一组数据中，找出值最大的前k个，或者找出值最小的前k个
2.在一组数据中，找出第k大的数字，或者找出第k小的数字。

小根堆和大根堆
        找前top k大的数据用小根堆，找前top k小的数据用大根堆，那么此类问题用堆结构可以很好的解决。在一组数据中以求最大的前10个数据为例，思路就是：先创建一个小根堆结构(每次都要当前堆中最小的元素的比较，如果比最小的大，则删除最小值，将该值加入到队列，这样最后剩下的10个便是最大的10个)，然后读取10个值到堆中，然后遍历剩下的元素依次和堆顶元素进行比较，如果比堆顶元素大，那么删除堆顶元素，把当前元素添加到小根堆中，元素遍历完成，堆中剩下的10个元素，就是值最大的10个元素。

在C++STL中，容器适配器priority_queue默认就是一个大根堆，可以通过改变模板类型，得到一个小根堆，经常会使用到。示例代码如下：
 

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
int main()
{
  /*
  求vector容器中元素值最大的前10个数字
  */
  vector<int> vec;
  for (int i = 0; i < 100000; ++i)
  {
    vec.push_back(rand() + i);
  }

  // 定义小根堆
  priority_queue<int, vector<int>, greater<int>> minHeap;
  // 先往小根堆放入10个元素
  int k = 0;
  for (; k < 10; ++k)
  {
    minHeap.push(vec[k]);
  }

  /*
  遍历剩下的元素依次和堆顶元素进行比较，如果比堆顶元素大，
  那么删除堆顶元素，把当前元素添加到小根堆中，元素遍历完成，
  堆中剩下的10个元素，就是值最大的10个元素
  */
  for (; k < vec.size(); ++k)
  {
    if (vec[k] > minHeap.top())
    {
      minHeap.pop();
      minHeap.push(vec[k]);
    }
  }

  // 打印结果
  while (!minHeap.empty())
  {
    cout << minHeap.top() << " ";
    minHeap.pop();
  }
  cout << endl;

  return 0;
}

那么求前top k小的数据和上面的原理一样，不同的就是使用一个大根堆，并且元素和堆顶元素比较的时候，要判断小于再更换（因为要找小的元素，所以要淘汰大值元素）。

如果找的是第k大的元素或者是第k小的元素，处理方式和上面的代码一样，只不过最后只读取堆顶元素就可以，因为这样的问题只找满足条件的一个元素而已

快排分割函数

来自于算法导论算法导论：期望为线性时间的选择算法_LIJIWEI0611的博客-CSDN博客
快排的分割函数，会选择一个基数，把小于基数的数字都调整到左边，把大于基数的数字都调整到右边，最后基数所在的位置就是第m小的数字，如果我们找的是第k小的数字，那么情况如下：

• 1.当k == m时，说明我们要找的第k小的数字已经找到了
• 2.当k > m时，我们需要把基数右边的数字序列再递归进行上面的操作，直到第1步条件成立
• 3.当k < m时，我们需要把基数左边的数字序列再递归进行上面的操作，直到第1步条件成立

所以当求解第k大的数字，或者第k小的数字时，还可以用快排分割函数递归求解，代码示例如下

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

/*
快排分割函数，选择arr[i]号元素作为基数，把小于arr[i]的元素
调整到左边，把大于arr[i]的元素调整到右边并返回基数位置的下标
*/
int partation(vector<int> &arr, int i, int j)
{
	int k = arr[i];
	while (i < j)
	{
		while (i < j && arr[j] >= k)
			j--;
		if (i < j)
			arr[i++] = arr[j];

		while (i < j && arr[i] < k)
			i++;
		if (i < j)
			arr[j--] = arr[i];
	}
	arr[i] = k;
	return i;
}
/*
params:
1.vector<int> &arr: 存储元素的容器
2.int i:数据范围的起始下标
3.int j:数据范围的末尾下标
4.int k:第k个元素
功能描述：通过快排分割函数递归求解第k小的数字，并返回它的值
*/
int selectNoK(vector<int> &arr, int i, int j, int k)
{
	int pos = partation(arr, i, j);
	if (pos == k-1)
		return arr[pos];
	else if (pos < k-1)
		return selectNoK(arr, pos + 1, j, k);
	else
		return selectNoK(arr, i, pos-1, k);
}
int main()
{
	/*
	求vector容器中元素第10小的元素值
	*/
	vector<int> vec;
	for (int i = 0; i < 100000; ++i)
	{
		vec.push_back(rand() + i);
	}
	
	// selectNoK返回的就是第10小的元素的值
	cout << selectNoK(vec, 0, vec.size()-1, 10) << endl;
	return 0;
}

查重和top k问题的综合应用

如果问题是在一组数字中 ，找出重复次数最多的前10个，那么该问题就是先进行哈希统计（查重操作），然后根据哈希统计结果再求top k问题，如下代码示例，演示了在一组数据中，快速找出数字重复次数最大的前10个，代码如下

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <functional>
using namespace std;
// 在一组数字中 ，找出重复次数最多的前10个
int main()
{
	// 用vec存储要处理的数字
	vector<int> vec;
	for (int i = 0; i < 200000; ++i)
	{
		vec.push_back(rand());
	}

	// 统计所有数字的重复次数,key:数字的值,value:数字重复的次数
	unordered_map<int, int> numMap;
	for (int val : vec)
	{
		/* 拿val数字在map中查找，如果val不存在，numMap[val]会插入一个[val, 0]
		这么一个返回值，然后++，得到一个[val, 1]这么一组新数据
		如果val存在，numMap[val]刚好返回的是val数字对应的second重复的次数，直接++*/
		numMap[val]++;
	}

	// 先定义一个小根堆
	using P = pair<int, int>;
	using FUNC = function<bool(P&, P&)>;
	using MinHeap = priority_queue<P, vector<P>, FUNC>;
	MinHeap minheap([](auto &a, auto &b)->bool {
		return a.second > b.second; // 自定义小根堆元素的大小比较方式
	});

	// 先往堆放k个数据
	int k = 0;
	auto it = numMap.begin();

	// 先从map表中读10个数据到小根堆中，建立top 10的小根堆，最小的元素在堆顶
	for (; it != numMap.end() && k < 10; ++it, ++k)
	{
		minheap.push(*it);
	}

	// 把K+1到末尾的元素进行遍历，和堆顶元素比较
	for (; it != numMap.end(); ++it)
	{
		// 如果map表中当前元素重复次数大于，堆顶元素的重复次数，则替换
		if (it->second > minheap.top().second)
		{
			minheap.pop();
			minheap.push(*it);
		}
	}
	// 堆中剩下的就是重复次数最大的前k个
	while (!minheap.empty())
	{
		auto &pair = minheap.top();
		cout << pair.first << " : " << pair.second << endl;
		minheap.pop();
	}
	return 0;
}

如果问题中对内存的使用大小做了限制，比如说有20亿个整数，内存限制400M，请求解重复次数最高的前10个数字，那么分析一下，20亿个整数，大约是8G大小，肯定无法一次性加载到内存当中，那么此时可以利用分治法的思想，把文件中20亿个整数通过哈希映射划分到50个小文件当中，那么每个文件大约4千万个整数，大小约是150M，此时小文件的数字完全可以一次行加载到内存中，然后分段求解合并最终的结果，得到重复次数最高的前10个数字，代码演示如下：

在内存有所限制的情况下，通过哈希映射+哈希统计+小根堆计算出来的top 10大的整数

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <functional>
using namespace std;
// 大文件划分小文件（哈希映射）+ 哈希统计 + 小根堆(快排也可以达到同样的时间复杂度)
int main()
{
  /*为了快速查看结果，这里缩小了数据量*/
  FILE *pf1 = fopen("data.dat", "wb");
  for (int i = 0; i < 20000; ++i)
  {
    int data = rand();
    if (data < 0)
      cout << data << endl;
    fwrite(&data, 4, 1, pf1);
  }
  fclose(pf1);


  // 打开存储数据的原始文件
  FILE *pf = fopen("data.dat", "rb");
  if (pf == nullptr)
    return 0;

  // 这里由于原始数据量缩小，所以这里文件划分的个数也变小了，11个小文件
  const int FILE_NO = 11;
  FILE *pfile[FILE_NO] = { nullptr };
  for (int i = 0; i < FILE_NO; ++i)
  {
    char filename[20];
    sprintf(filename, "data%d.dat", i + 1);
    pfile[i] = fopen(filename, "wb+");
  }

  // 哈希映射，把大文件中的数据，映射到各个小文件当中
  int data;
  while (fread(&data, 4, 1, pf) > 0)
  {
    int findex = data % FILE_NO;
    fwrite(&data, 4, 1, pfile[findex]);
    cout << "data:" << data << " file:" << findex << endl;
  }

  // 定义一个链式哈希表
  unordered_map<int, int> numMap;
  // 先定义一个小根堆
  using P = pair<int, int>;
  using FUNC = function<bool(P&, P&)>;
  using MinHeap = priority_queue<P, vector<P>, FUNC>;
  MinHeap minheap([](auto &a, auto &b)->bool {
    return a.second > b.second; // 自定义小根堆元素大小比较方式
    });

  // 分段求解小文件的top 10大的数字，并求出最终结果
  for (int i = 0; i < FILE_NO; ++i)
  {
    // 恢复小文件的文件指针到起始位置
    fseek(pfile[i], 0, SEEK_SET);

    while (fread(&data, 4, 1, pfile[i]) > 0)
    {
      numMap[data]++;
    }

    int k = 0;
    auto it = numMap.begin();

    // 如果堆是空的，先往堆方10个数据
    if (minheap.empty())
    {
      // 先从map表中读10个数据到小根堆中，建立top 10的小根堆，最小的元素在堆顶
      for (; it != numMap.end() && k < 10; ++it, ++k)
      {
        minheap.push(*it);
      }
    }

    // 把K+1到末尾的元素进行遍历，和堆顶元素比较
    for (; it != numMap.end(); ++it)
    {
      // 如果map表中当前元素重复次数大于，堆顶元素的重复次数，则替换
      if (it->second > minheap.top().second)
      {
        minheap.pop();
        minheap.push(*it);
      }
    }

    // 清空哈希表，进行下一个小文件的数据统计
    numMap.clear();
  }

  // 堆中剩下的就是重复次数最大的前k个
  while (!minheap.empty())
  {
    auto &pair = minheap.top();
    cout << pair.first << " : " << pair.second << endl;
    minheap.pop();
  }

  return 0;
}