大数据处理基本思想——分治法

分治法——“分而治之”

众所周知，计算机计算速度非常快而被人们加以使用，但计算速度再快的计算机，处理数据的能力也有一定限度，所以在处理大数据操作的时候，采用分治法可以有效的处理目前人类社会所遇到的大部分大数据问题。

分治法的主要思想就是将一个复杂的问题分成两个或多个相同的子问题，子问题可以分成更小的子问题，直到子问题可以容易解决的时候，原问题的解就是子问题解的和。

下面我们举一个例子，我们先解决一个简单的问题

例1   取任意一组从0~10的数，找出其中出现次数最多的数。

例如我们取一组数{1,2,3,5,6,8,7,4,5,2,1,5,4,8,9,6,3,2,1,2}；只需输出其中出现次数最多的数即可。

这道问题不难解决，方法也很多，可以先将数据排序，然后找一样的个数，可是就算用快排，我们的时间复杂度也还是很大，在这么我们注意问题给的条件：一组0~10的数，没错，我们数据的选择范围是0~10，所以我们可以通过一个十个格子（0~9）大小的数组，来保存每个数字出现的次数，最后遍历比较一遍，将数组中最大的数的下标（即出现次数最多的数）返回即可。

如上图所示，我们把需要测试的数据保存到第一个数组中，第二个则保存出现的次数，最后遍历比较一遍即可（时间复杂度是O(m+n)）；

代码就不写了，过程比较简单，我们用这个题引入下一个题：

例2   还是取一组0~10的数，区别是，我们这次规定重新创建的数组只能用五个格子（4*5=20个字节）的数组，那么这个问题该如何解决呢？

其实仔细想想就能想到，只让用五个格子大小的数组，那我们用两次不就好了，一次保存前五位（0~4），一次保存后五位（5~9）的个数，最后分别遍历，取出最大数的下标，结果和时间复杂度是一样的。

有个小细节，我们可以将前五位保存和后五位保存换成奇数保存和偶数保存，这样保存遍历小数据看不出差异，做大数据处理的时候就能发现其好处了。

下面是代码：

#include <stdio.h>
#include <string.h>

typedef struct Pair
{
	int num;
	int times;
}Pair;


Pair MaxTimes2(int *arr,int len)
{
	int brr[5] = {0};
	int i;
	for(i = 0;i < len ;i++)
	{
		if(arr[i] % 2 == 0)
		{
			brr[arr[i]/2]++;
		}

	}
	Pair tmp={0,0};
	for(i = 0;i < 5;i++)
	{
		if(tmp.times  < brr[i])
		{
			tmp.times = brr[i];
			tmp.num =i*2;
		}
	}

	memset(brr,0,sizeof(brr));
	for(i = 0;i < len;i++)
	{
		if(arr[i]%2 == 1)//1,3,5,7,9->0,1,2,3,4
		{
			brr[arr[i]/2]++;
		}
		
	}
	Pair temp = {0,0};
	for( i = 0; i < 10;i+=5)
	{
		if(temp.times <brr[i])
		{
			temp.times = brr[i];
			temp.num =i*2+1;
		}
	}

	if(tmp.times > temp.times)
	{
		return tmp;
	}
	else
	{
		return temp;
	}
}

int main()
{
	int arr[] = {1,3,5,5,8,9,8,5,8,6,3,3,1,2,3,6,4,8,1,2};
	printf("出现次数最多的数是：%d,出现次数%d\n",MaxTimes2(arr,sizeof(arr)/sizeof(arr[0])).num,MaxTimes2(arr,sizeof(arr)/sizeof(arr[0])).times);

	return 0;
}

 其实小数据的处理就是这样，以小见大，就是大数据的处理，例如我们做如下的题目

 

 是不是思想和上面的例2很像呢？没错，这就是分治法处理大数据的主要思想，如果有兴趣的话，可以试着处理一下这个大数据的题目~我们一起交流结果。