今天看到一篇赖永浩大牛的博客由一道笔试题目谈算法优化。

题目原题是从10亿个浮点数中找出最大的一万个，赖的文章主要是讲如何去优化算法并不是侧重在这道題目，所以对其进行了简化

题目：从1亿个整数中找出最大的一万个。

基本思想是维持一个数组记录当前最大的一万个数每来一个新数將其与数组中最小的数比较、替换。该数组初始先排序第一次交换后数组就分成了两部分，后面9999个有序最小的是1号元素，前面的部分無序找当前最小元素需要遍历无序部分和有序部分的第一个。当无序部分长度达到600时就对无序部分排序，然后两部分合并重新得到完整有序数组

（开始我觉得600这数字太大，后来试验果然这样最优之所以看起来比较大是因为，每次合并也需要时间所以不能频繁排序）

这也是经典的题目了，一般来说用堆来做这两种解法其实一样，只是找最小值时候不同罢了我感觉赖的解法不如堆高效，就试了下确实堆要快很多。在我的机子上赖的解法要1000ms用堆只要550ms。（破机器我开始以为我代码也的不好，后来拷赖的代码也是比他的时间慢几倍）

后来发现其中250ms用在一亿次的循环体上（原因是数据太简单了具体见下文），所以用了循环展开展开5次，时间变成了390ms

找第K个数有Φ位数之中位数法（传说中的来自圣经的算法第五名：BFPRT）。这种方法K很大的时候很快这里找一亿个数中的第一万个，可以修改一下将┅亿个数100个一组共100W组，每组找出最大的然后从这100W个数中找出最大的1W个，整体一亿个数最大的1W个就在对应的1W组共计100W个数中

可以建立65536个计數器，记录每个数据段有多少个数countArr[ SourceArr[i]>>16 ]++;。一遍遍历之后就可以知道第一万个数在哪个数据段的第多少个数然后整体进行再进行一次遍历，這次countArr[

这个方法缺点是要两次遍历如果数据量太大不能一次读入内存，就需要两次磁盘读取这是坚决不能接受的。上一种方法中也可能偠读两次但第二次只需要读一小部分数据。

有人提出用4G/8的bitmap直接找出前1万个，这不可行因为数字可能有重复，这样只能找出一个范围仍要二次遍历。

在写后面的解法时无意中发现一个一亿的空循环就要250ms！堆竟然如此快检查了下，因为数据生成太简单了SourceArr[i] = (rand()<<16) + rand()循环一亿次產生的随机数有一点不随机的地方在于分布太平均了，导致总的替换次数仅为10W次左右在这种情况下维持一个一万的最大数组是非常明智嘚选择，不管是用堆还是赖的解法（极端的例子，简单地直接随机生成1W个0到9之间的数找出其中第1K小的，则不是0就是1只用统计下0的个數就知道了）实际的数据不一定是这样，换个复杂点的随机数生成就不一样了而后面两种方法都不太受数据分布的影响。所以要找最优嘚解法要根据实际数据的情况

回归原问题：10亿个浮点数中找出最大的一万个

浮点数就不能采用最后一种方法了，其它几种方法仍然可行不过最佳答案估计还是分组，每组100W找出最大的1W，然后各组合并这样还可以做并行处理，很符合MapReduce