如何在1亿个数中找出最大的100个数（top K问题）

​ 最容易想到的方法是将数据全部排序，然后在排序后的集合中进行查找，最快的排序算法的时间复杂度一般为O（nlogn），如快速排序。但是在32位的机器上，每个float类型占4个字节，1亿个浮点数就要占用400MB的存储空间，对于一些可用内存小于400M的计算机而言，很显然是不能一次将全部数据读入内存进行排序的。其实即使内存能够满足要求（我机器内存都是8GB），该方法也并不高效，因为题目的目的是寻找出最大的10000个数即可，而排序却是将所有的元素都排序了，做了很多的无用功。

​ 第二种方法为局部淘汰法，该方法与排序方法类似，用一个容器保存前10000个数，然后将剩余的所有数字——与容器内的最小数字相比，如果所有后续的元素都比容器内的10000个数还小，那么容器内这个10000个数就是最大10000个数。如果某一后续元素比容器内最小数字大，则删掉容器内最小元素，并将该元素插入容器，最后遍历完这1亿个数，得到的结果容器中保存的数即为最终结果了。此时的时间复杂度为O（n+m^2），其中m为容器的大小，即10000。

​ 第三种方法是分治法，将1亿个数据分成100份，每份100万个数据，找到每份数据中最大的10000个，最后在剩下的10010000个数据里面找出最大的10000个。如果100万数据选择足够理想，那么可以过滤掉1亿数据里面99%的数据。100万个数据里面查找最大的10000个数据的方法如下：用快速排序的方法，将数据分为2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大堆个数N小于10000个，就在小的那堆里面快速排序一次，找第10000-n大的数字；递归以上过程，就可以找到第1w大的数。参考上面的找出第1w大数字，就可以类似的方法找到前10000大数字了。此种方法需要每次的内存空间为10^64=4MB，一共需要101次这样的比较。*

​ 第四种方法是Hash法。如果这1亿个书里面有很多重复的数，先通过Hash法，把这1亿个数字去重复，这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间，然后通过分治法或最小堆法查找最大的10000个数。

​ 第五种方法采用最小堆。首先读入前10000个数来创建大小为10000的最小堆，建堆的时间复杂度为O（mlogm）（m为数组的大小即为10000），然后遍历后续的数字，并于堆顶（最小）数字进行比较。如果比最小的数小，则继续读取后续数字；如果比堆顶数字大，则替换堆顶元素并重新调整堆为最小堆。整个过程直至1亿个数全部遍历完为止。然后按照中序遍历的方式输出当前堆中的所有10000个数字。该算法的时间复杂度为O（nmlogm），空间复杂度是10000（常数）。

实际运行：

​ 实际上，最优的解决方案应该是最符合实际设计需求的方案，在时间应用中，可能有足够大的内存，那么直接将数据扔到内存中一次性处理即可，也可能机器有多个核，这样可以采用多线程处理整个数据集。

​ 下面针对不容的应用场景，分析了适合相应应用场景的解决方案。

（1）单机+单核+足够大内存
​ 如果需要查找10亿个查询次（每个占8B）中出现频率最高的10个，考虑到每个查询词占8B，则10亿个查询次所需的内存大约是10^9 * 8B=8GB内存。如果有这么大内存，直接在内存中对查询次进行排序，顺序遍历找出10个出现频率最大的即可。这种方法简单快速，使用。然后，也可以先用HashMap求出每个词出现的频率，然后求出频率最大的10个词。

（2）单机+多核+足够大内存
​ 这时可以直接在内存总使用Hash方法将数据划分成n个partition，每个partition交给一个线程处理，线程的处理逻辑同（1）类似，最后一个线程将结果归并。

​ 该方法存在一个瓶颈会明显影响效率，即数据倾斜。每个线程的处理速度可能不同，快的线程需要等待慢的线程，最终的处理速度取决于慢的线程。而针对此问题，解决的方法是，将数据划分成c×n个partition（c>1），每个线程处理完当前partition后主动取下一个partition继续处理，知道所有数据处理完毕，最后由一个线程进行归并。

（3）单机+单核+受限内存
​ 这种情况下，需要将原数据文件切割成一个一个小文件，如次啊用hash(x)%M，将原文件中的数据切割成M小文件，如果小文件仍大于内存大小，继续采用Hash的方法对数据文件进行分割，知道每个小文件小于内存大小，这样每个文件可放到内存中处理。采用（1）的方法依次处理每个小文件。

（4）多机+受限内存
​ 这种情况，为了合理利用多台机器的资源，可将数据分发到多台机器上，每台机器采用（3）中的策略解决本地的数据。可采用hash+socket方法进行数据分发。

​ 从实际应用的角度考虑，（1）（2）（3）（4）方案并不可行，因为在大规模数据处理环境下，作业效率并不是首要考虑的问题，算法的扩展性和容错性才是首要考虑的。算法应该具有良好的扩展性，以便数据量进一步加大（随着业务的发展，数据量加大是必然的）时，在不修改算法框架的前提下，可达到近似的线性比；算法应该具有容错性，即当前某个文件处理失败后，能自动将其交给另外一个线程继续处理，而不是从头开始处理。

​ top K问题很适合采用MapReduce框架解决，用户只需编写一个Map函数和两个Reduce 函数，然后提交到Hadoop（采用Mapchain和Reducechain）上即可解决该问题。具体而言，就是首先根据数据值或者把数据hash(MD5)后的值按照范围划分到不同的机器上，最好可以让数据划分后一次读入内存，这样不同的机器负责处理不同的数值范围，实际上就是Map。得到结果后，各个机器只需拿出各自出现次数最多的前N个数据，然后汇总，选出所有的数据中出现次数最多的前N个数据，这实际上就是Reduce过程。对于Map函数，采用Hash算法，将Hash值相同的数据交给同一个Reduce task；对于第一个Reduce函数，采用HashMap统计出每个词出现的频率，对于第二个Reduce 函数，统计所有Reduce task，输出数据中的top K即可。

​ 直接将数据均分到不同的机器上进行处理是无法得到正确的结果的。因为一个数据可能被均分到不同的机器上，而另一个则可能完全聚集到一个机器上，同时还可能存在具有相同数目的数据。

以下是一些经常被提及的该类问题。

（1）有10000000个记录，这些查询串的重复度比较高，如果除去重复后，不超过3000000个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请统计最热门的10个查询串，要求使用的内存不能超过1GB。

（2）有10个文件，每个文件1GB，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。按照query的频度排序。

（3）有一个1GB大小的文件，里面的每一行是一个词，词的大小不超过16个字节，内存限制大小是1MB。返回频数最高的100个词。

（4）提取某日访问网站次数最多的那个IP。

（5）10亿个整数找出重复次数最多的100个整数。

（6）搜索的输入信息是一个字符串，统计300万条输入信息中最热门的前10条，每次输入的一个字符串为不超过255B，内存使用只有1GB。

（7）有1000万个身份证号以及他们对应的数据，身份证号可能重复，找出出现次数最多的身份证号。

重复问题
​ 在海量数据中查找出重复出现的元素或者去除重复出现的元素也是常考的问题。针对此类问题，一般可以通过位图法实现。例如，已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。

​ 本题最好的解决方法是通过使用位图法来实现。8位整数可以表示的最大十进制数值为99999999。如果每个数字对应于位图中一个bit位，那么存储8位整数大约需要99MB。因为1B=8bit，所以99Mbit折合成内存为99/8=12.375MB的内存，即可以只用12.375MB的内存表示所有的8位数电话号码的内容。

算法一：冒泡排序法

千里之行，始于足下。我们先不说最好，甚至不说好。我们只问，如何“从10000个整数中找出最大的10个”？我最先想到的是用冒泡排序的办法：我们从头到尾走10趟，自然会把最大的10个数找到。方法简单，就不再这里写代码了。这个算法的复杂度是10N（N=10000）。

算法二：

有没有更好一点的算法呢？当然。维持一个长度为10的降序数组，每一个从数组拿到的数字都与这个降序数组的最小值比较。如果小于最小值，就舍弃；如果大于最小值，就把它插入到降序数组中的合适位置，舍弃原来的最小值。这样，遍历一遍就可以找到最大的10个数。因为需要在降序数组中插入一个数，对于遍历的每个数可能都需要这样，所以其复杂为5N。

伪代码如下：

　　A[N]，a[m]（分别为原始数组和降序数组，其中N=10000，m=10）

　　a = A[0 ... 9]（将数组A的前10个数赋给数组a）

　　sort a（将组数a降序排序）

　　for i in A[ 10 ... N]（从10到N遍历数组A）

　　　　if A[i] > a[9] then （如果当前值比降序数组中的最小值大）

　　　　　　删除a[9]

　　　　　　将A[i]插入a的合适位置，使a保持降序

　　　　end if

　　end for

　　输出数组a

其实算法二还有一个优点，就是当数组很大时，可以将数据分段读入内存处理，而这样做并不影响结果。

1、首先一点，对于海量数据处理，思路基本上是确定的，必须分块处理，然后再合并起来。

2、对于每一块必须找出10个最大的数，因为第一块中10个最大数中的最小的，可能比第二块中10最大数中的最大的还要大。

3、分块处理，再合并。也就是Google MapReduce 的基本思想。Google有很多的服务器，每个服务器又有很多的CPU，因此，100亿个数分成100块，每个服务器处理一块，1亿个数分成100块，每个CPU处理一块。然后再从下往上合并。注意：分块的时候，要保证块与块之间独立，没有依赖关系，否则不能完全并行处理，线程之间要互斥。另外一点，分块处理过程中，不要有副作用，也就是不要修改原数据，否则下次计算结果就不一样了。

4、上面讲了，对于海量数据，使用多个服务器，多个CPU可以并行，显著提高效率。对于单个服务器，单个CPU有没有意义呢？

也有很大的意义。如果不分块，相当于对100亿个数字遍历，作比较。这中间存在大量的没有必要的比较。可以举个例子说明，全校高一有100个班，我想找出全校前10名的同学，很傻的办法就是，把高一100个班的同学成绩都取出来，作比较，这个比较数据量太大了。应该很容易想到，班里的第11名，不可能是全校的前10名。也就是说，不是班里的前10名，就不可能是全校的前10名。因此，只需要把每个班里的前10取出来，作比较就行了，这样比较的数据量就大大地减少了。

之前看到一个面试题，1000个乱序正整数中找出10个最小值，要求高效快速，不能使用API。

​ 这学期学了些排序的方法，什么快速排序啊，冒泡啊，归并排序啊之类的。看到这个题的时候，第一反应是快速排序，因为它的名字叫快速嘛，应该够快吧。然后又想到这个题目不是要你完整的排序，只需要求出最小的10个就够了，那么冒泡法呢？冒泡法只冒前面10个数？

​ 发现这样子还是要遍历比较1000*10次。

​ 然后，利用类似于数据结构里的栈的特性？把这1000个数的前10个放到一个数组中，排好序，然后，剩下的990个数字，每个都与这10个数的最大数比较，大于则不考虑，小于就把最大值拿出来，把这个数放进去，这样的话，冒泡排序的比较次数就变成了990次，好像高效很多哦？

思路一：

看到这个题目的第一反应是：循环随机产生1-100的随机数，判断数组中是否已经有该数，若已存在，则重新生成随机数；若不存在，则放入数组中。

实现代码如下所示：

public void setData(int[] array){
		Random rd = new Random();
		boolean isExit;
		int len = array.length;
		for(int i = 0; i < array.length; i++){
			isExit = false;
			//生成一个1-100之间的随机数
			int num = rd.nextInt(len)+1;
			//检验数组中是否已有该数
			for(int j = 0; j < i; j++){
				if(array[j] == num){
					isExit = true;
					i--;
					break;
				}
			}
			if(!isExit){
				array[i] = num;
			}
		}
	}

运行查看结果，发现该方法可行，但是，当我们要随机产生的数变大时，这种方法所体现出的效率就会变得非常低。

我们可以利用System.currentTimeMillis()方法来计算该算法所用的时间。

测试：将产生的随机数改成1-10000，运行该程序：

结果如下图所示（结果的一部分）：

我们可以看到，用这种算法效率很差，所以我们要想办法改进这个算法。我们先来想想这个算法的运行时间主要消耗在哪里？这应该是显而易见的，每生成一个随机数，程序就需要遍历整个数组来判断其中是否存在该数，这是很耗时的。能不能想办法不用每次都去遍历查找呢？有什么办法可以保证每次生成的数不会重复呢？

思路二：

我们不妨来逆向思考，事先将1-100这间的数顺序存入数组sorce中，随机产生一个位置，然后将该索引对应的数组元素依次放入数组array中，每次放入一个数后，都要将该数从source数组中删除，而下一次产生的随机数的范围也将所缩小。由于已生成的数已经被删除，所以每次产生的数就不会再重复。

实现代码如下所示：

	public void setNum(int[] source,int[] array){
		Random rd = new Random();
		int range = array.length;
		int index = 0;
		for(int i = 0; i <array.length; i++){
			//随机产生一个位置
			int pos = rd.nextInt(range);
			//获取该位置的值
			array[i] = source[pos];
			//删除该索引在数组中的位置
			for(int j = pos; j < array.length-1; j++){
				source[j] = source[j+1];
			}
			//缩小随机数产生的范围
			range--;
		}
	}

由上图可以看出，由于省去了生成无效随机数的时间，效率提高了100多倍！

思路三：

不过这个算法也不是效率最高的方法，该算法还是存在弊端的，因为在生成了随机数之后，对整个数组进行了删除操作，其实也就是进行了一系列数据的交换，这也是比较耗时的，所以我们可以考虑的是：在保证不进行删除操作，但也能将产生的数从数组中剔除的方法。

第一反应想到的应该会给这个数覆盖上其他的值，那应该赋什么值呢？0？如果赋0的话，那接下来生成随机数的范围就无法再是递减1的缩小了，那么有没有其他的方法呢？可不可以给它赋一个数组中还需要存在的数呢？我们不妨将数组中最后一个数赋给它，那么下次随机数的产生也还能采用思路二中的方法，主要思路如下所示：

假设数组中的数为：1,2,3,4,5,6

第一次随机产生的索引为3，即对应的是4，将4写入array数组中后，将6赋到array[3]中，则数组更新为：1,2,3,6,5,6（有效的数其实只有1,2,3,6,5）

第二次随机产生的索引为4，即对应的是6，将6写入array数组中后，将5赋给array[4]中，则数组更新为：1,2,3,5,5,6（有效的数其实只有1,2,3,5）

第三次随机产生的索引为1，即对应的是2，将2写入array数组中后，将5赋给array[1]中，则数组更新为：1,5,3,5,5,6（有效的数其实只有1,5,3）

以此类推......

采用这个方法，就不需要再对source数组中数进行删除（多次数据交换），而每一次产生随机数后，只需要执行一次数据交换即可，又在一定程度上提高了程序运行的效率。

实现代码如下所示：

public void setNum(int[] source,int[] array){
		Random rd = new Random();
		int range = array.length;
		int index = 0;
		for(int i = 0; i <array.length; i++){
			//随机产生一个位置
			int pos = rd.nextInt(range);
			//获取该位置的值
			array[i] = source[pos];
			//改良：将最后一个数赋给被删除的索引所对应的值
			source[pos] = source[range-1];
			缩小随机数产生的范围
			range--;
		}
	}

可见，该算法的耗时又比思路二的提高了近100倍！而比思路一快了1000多倍！

所以，我们可以发现算法对一个程序的执行效率有着关键性的作用，我们在解决问题的时候应该逐步思考，在运行正确的情况下也应该多考虑程序的性能问题，找到程序中比较耗时的部分，然后再去思考是否有方法对其进行优化。