java 从一亿个数中,如何找出最小的1000个数?

最近看到的一条算法题。刚看到时一点思路都没有,所以研究一下。

参考:http://blog.csdn.net/zyq522376829/article/details/47686867

 

在大规模数据处理中,经常会遇到的一类问题:在海量数据中找出出现频率最高(即出现次数最多)的前k个数,或者从海量数据中找出最大的前k个数,这类问题通常被称为top K问题。

例如,在搜索引擎中,统计搜索最热门的10个查询词;在歌曲库中统计下载最高的前10首歌等。

参考文章的原作者介绍的是如何“找最大的k”。为了加以区别,我决定研究如何找“最小的k”(其实思路和实现方法都是类似的)。

一、全排序法

把所有数按大小进行排序,最后取前10个数,即为最小数(简单粗暴好想)。

在实践前我们先讨论一下这种做法的可行性:在java中一个整型占4字节,一亿个整型数就是4亿字节,需要400多mb内存(空闲内存),我相信大部分主机这点内存还是有的。

全排序法的问题是效率太差了。如果选择的算法选择不科学(只需要10个最小的数,却要不停地遍历/排序1亿个数),就会导致耗时极长。

全排序有几种简单的算法选择,冒泡排序、插入排序、选择排序。拿最常见的冒泡排序做个例子:

TestAllSort.java

我们都知道冒泡排序效率低,那么这段程序能跑多长时间呢?运行之后我去泡了杯茶,茶都凉了,还是没跑完…

换个插入排序怎么样?

TestAllSort.java

效果是差不多的…运行时间长到我没有跑完。

所以,在处理大量数据的情况下千万不要使用全排序法(如果数据量少,也许可以考虑一下,数据量具体到多少可以用,我也没研究过…最好先实践一下效果如何)。

现在想来,最开始编码时我直接使用了冒泡排序(遍历时,每个元素都要和上方所有元素比较,效率最差),绝对是错误的示范,应该引以为戒。

二、局部淘汰法

参考:http://www.oschina.net/code/snippet_2349747_50840?p=2#comments

既然我们需要找到10个最小的数,那么我们就创建长度为10的双链表(任意容器,数组也可以,我们在这里使用了双链表),让这100000000个数陆续经过双链表的筛选,不停地比较直至留下最小的数(不停地留下最小的数,踢走最大的数)。最后我们就会在双链表中获得10个最小的数。

TestEliminate.java

运行结果为:

三、分治法

将1亿个数据分成100份,每份100万个数据,找到每份数据中最大的10000个,最后一共可以找到100 * 10000 = 100万个数据。如果这100万数据足够理想,就可以过滤掉1亿数据里面99%的数据。

在个方案的最难之处在于“如何从100万个数据里面查找最小的10000个数据”。借鉴快速排序的思想,有以下解法:

用快速排序的方法,将数据分为2堆(只是分堆而已(可以理解为不完全的快速排序),所以只能分成大堆和小堆,堆中的数据不一定是有序的)。如果小堆个数N大于10000个,继续对小堆快速排序,一次分成2堆(不停持续此过程,直至小于10000个)。如果小堆个数N小于10000个,就在大的那堆里面快速排序一次,找第1至10000 – N大的数字(加起来凑够10000个数据,或者换个思路,如果再分堆就小于10000个,那么就不继续分堆,直接对整个堆进行一次快速排序,取前10000个数据即可)。

重复以上过程,就可以找到每份数据中最小的10000个数据。最后我们合并所有数据,再进行简单排序(数据量少了,排序的效率就高了)),就能得到最小的十个数据。

举个简单例子:

TestDivideAndConquer.java

运行结果为:

可以使用多线程完成这一步骤,从而提高执行的效率。

四、Hash法

Hash法不是排序算法,而是排序前的处理(看到Hash就应该联想到去重)。如果这1亿个数中存在许多重复(前提是数据存在许多重复,而且你并不想要重复的数据),可以先通过Hash法进行去重,从而减少内存用量,缩小运算空间。

在java中,一般会用hashset对数组进行去重:

TestHashSet.java

运行结果为:

去重之后可以通过上面提到的各种方法查找最小的10个数。

五、最大堆法

参考:http://www.w2bc.com/article/232857

首先读入前10个数来创建大小为10的最大堆,然后遍历后续的数字,并与堆顶(最大)数字进行比较。如果比堆顶数字小,则替换堆顶元素并重新调整堆为最大堆;如果比堆顶数字大,就跳过这个数字(比最大的数要大,没资格留下来),继续向后读取。

当1亿个数全部遍历完,留在最大堆中的数就是最小的10个数。

TestMaxHeap.java

运行结果为:

最大堆中一开始并没有2(是我们手工插入的),最后这个2留在了最大堆中,说明该算法确实留下了最小的数。

根据堆的特性,此方法速度奇快,最大堆法在这几种算法中是最靠谱的。

六、总结

top K问题抽象到最后就变成了纯算法问题。

解决方案有很多,不难搜到,最终考验的是开发者的数据结构基础(如何实现),在这方面还需要多多加强。

1 对 “java 从一亿个数中,如何找出最小的1000个数?”的想法;

  1. 这篇文章写的太棒了!给楼主点个赞,分析的很到位,先看到了双链表的处理,mark下,晚上接着回去看!

发表评论

电子邮件地址不会被公开。 必填项已用*标注