从无重复大数组找TOP N元素的最优解说起

有一类面试题,既可以考察工程师算法、也可以兼顾实践应用、甚至创新思维,这些题目便是好的题目,有区分度表现为可以有一般解,也可以有最优解。最近就发现了一个这样的好题目,拿出来晒一晒。

1 题目 原文:

There is an array of 10000000 different int numbers. Find out its largest 100 elements. The implementation should be optimized for executing speed.

翻译:

有一个长度为1000万的int数组,各元素互不重复。如何以最快的速度找出其中最大的100个元素?

2 分析与解 (接下来的算法均以Java语言实现。)

首先,第一个冒出来的想法是——排序。各种排序算法对数组进行一次sort,然后limit出max的100个即可,时间复杂度为O(nLogN)。

2.1 堆排序思路 我以堆排序来实现这个题目,这样可以使用非常少的内存空间,始终维护一个100个元素大小的最小堆,堆顶int[0]即是100个元素中最小的,插入一个新的元素的时候,将这个元素和堆顶int[0]进行交换,也就是淘汰掉堆顶,然后再维护一个最小堆,使int[0]再次存储最小的元素,循环往复,不断迭代,最终剩下的100个元素就是结果,该算法时间复杂度仍然是O(nLogN),优点在于节省内存空间,算法时间复杂度比较理想,平均耗时400ms。

代码实现如下,

那么挖掘下题目,两个点是我们的优化线索:

1、元素互不重复

2、最快的速度,没有提及对于系统资源以及空间的要求

2.2 多线程分而治之策略 顺着#2条线索,可以给出一个多线程的优化版本,使用分而治之的策略,将1000万大小的数组分割为1000个元素组成的若干小数组,利用JDK自带的高效排序算法void java.util.Arrays.sort(int[] a)来进行排序,多线程处理,主线程汇总结果后取出各个小数组的top 100,归并后再进行一次排序得出结果。

代码实现如下,

分析看来,这个解的优势在于充分利用了系统资源,使用了分而治之的思想,将时间复杂度平均分配到了每个子线程中,但是代码中大量用到了System.arraycopy进行数组拷贝,占用内存过于多,甚至需要指定JVM的内存-Xmx才可以正常运行起来,平均耗时250ms。

2.3 位图数组思路 这个思路属于比较创新的方式,考虑到优化线索#1提到的无重复元素,那么可以使用位图数组存储元素,一个int占用4个字节,32个bit,也就是说1个int可以表示32个数字的位置。 维护一个数组长度/32+1的位图数组x,遍历给定的数组,将数字安插进入这个位图数组x中,例如int[0]=62,那么

那么就置位图数组的x[1]=x[1] | 30,采用“位或”是为了不丢掉以前处理过的数字。

代码实现如下,

这个算法的时间复杂度是O(N),非常理想,平均耗时可以减少到50ms作用,性能比排序算法提升了10倍以上,不足在于位图数组的长度取决于给定数组的最大值,如果分布比较平均,并且最大值比较小,那么占用内存空间就可以得到有效的控制。

3 总结

综上给出的题目,可以看出解决一个实际问题,既可以用纯算法的思路来解决,我们甚至可以自己动手实现,例如自己写的堆排序,非常节省空间,如果用JDK自带的快速排序,那么无疑这一点不会好于我们的实现。 现今,处理大数据问题一个倾向的思路就是充分利用系统资源,充分发挥多核、大内存计算型服务器的能力,为我们提高效率,多线程是在JAVA中以及有了非常好用的API以及concurrent包下的工具类,能否有效利用这些工具提速我们的程序也很关键。同时,问题总有一些点可以让我们找到最适合的场景来解决,例如位图数组的思路,在性能上达到了最佳,同时多消耗的内存对于现代的服务器来说完全在可控范围内,因此不失为一种创新的好思路。

3 4 收藏 5 评论

关于作者:蓝猫163

自由职业者,追求技术,追求自由 个人主页 · 我的文章 · 7 ·   

相关文章

可能感兴趣的话题



直接登录
最新评论
  • JeffYe   2016/06/15

    可不可以直接max heapify输入数组然后从堆顶取100次呢?

    无需除输入以外的额外空间,heapify时间复杂度O(n),取100次复杂度为100Logn,总复杂度O(n)

  • 灰灰 游戏码农 2016/06/17

    最后那个就是桶排序吧

  • 王伯   2016/06/24

    最后那个位操作应该是x[1]=x[1] | 1<< 30

    代码中的&gt; &lt; 之类麻烦改过来,写完文章不能自己检查一下吗?

    • 蓝猫163 java 2016/06/25

      原文在这里:http://www.cnblogs.com/bymax/p/5246691.html

      我分别用 ` 进行代码缩进和四个空格进行缩进,在后台markdown编辑器测试了好久,更新的结果还是一样, 引号、大于号、小于号 等都被自动进行转义了。

      不知道是不是伯乐在线进行了更新, 其他人的文章都没有发现这个问题,

      我把markdown原文发到其他网站都没有出现过这个问题的,烦

      • 黄利民 站长 2016/06/25

        刚代修改了。

        其实不需要非得要 MD。
        上次(6月15日)站内私信你,那篇文章中有【代码段】用法示例图。

跳到底部
返回顶部