海量数据查重问题解决方案

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

上一篇:C++的大坑


下一篇:STL 总结