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;
}