从一道笔试题谈算法优化

《从一道笔试题谈算法优化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、声明：本文最初发表于《电脑编程技巧与维护》2006年第5期，版本所有，如蒙转载，敬请连此声明一起转载，否则追究侵权责任。从一道笔试题谈算法优化（上）作者：赖勇浩（http://blog.csdn.net/lanphaday）引子每年十一月各大IT公司都不约而同、争后恐后地到各大高校进行全国巡回招聘。与此同时，网上也开始出现大量笔试面试题；网上流传的题目往往都很精巧，既能让考查基础知识，又在平淡中隐含了广阔的天地供优秀学生驰骋。这两天在网上淘到一道笔试题目（注1），虽然真假未知，但的确是道好题，题目如下：从10亿个浮点数中找出最大的1万个。这是一道似易实难的题目

2、，一般同学最容易中的陷阱就是没有重视这个“亿”字。因为有10亿个单精度浮点数元素的数组在32位平台上已经达到3.7GB之巨，在常见计算机平台（如Win32）上声明一个这样的数组将导致堆栈溢出。正确的解决方法是分治法，比如每次处理100万个数，然后再综合起来。不过这不是本文要讨论的主旨，所以本文把上题的10亿改为1亿，把浮点数改为整数，这样可以直接地完成这个问题，有利于清晰地讨论相关算法的优化（注2）。不假思索拿到这道题，马上就会想到的方法是建立一个数组把1亿个数装起来，然后用for循环遍历这个数组，找出最大的1万个数来。原因很简单，因为如果要找出最大的那个数，

3、就是这样解决的；而找最大的1万个数，只是重复1万遍而已。templatevoidsolution_1(TBigArr[],TResArr[]){for(inti=0;iBigArr[idx])idx=j;}ResArr[i]=BigArr[idx];std::swap(BigArr[idx],BigArr[i]);}}设BIG_ARR_SIZE＝1亿，RES_ARR_SIZE=1万，运行以上算法已经

4、超过40分钟（注3），远远超过我们的可接受范围。稍作思考从上面的代码可以看出跟SelectSort算法的核心代码是一样的。因为SelectSort是一个O(n^2)的算法（solution_1的时间复杂度为O(n*m)，因为solution_1没有将整个大数组全部排序），而我们又知道排序算法可以优化到O(nlogn)，那们是否可以从这方面入手使用更快的排序算法如MergeSort、QuickSort呢？但这些算法都不具备从大至小选择最大的N个数的功能，因此只有将1亿个数按从大到小用QuickSort排序，然后提取最前面的1万个。template

5、classI>voidsolution_2(TBigArr[],TResArr[]){std::sort(BigArr,BigArr+BIG_ARR_SIZE,std::greater_equal());memcpy(ResArr,BigArr,sizeof(T)*RES_ARR_SIZE);}因为STL里的sort算法使用的是QuickSort，在这里直接拿来用了，是因为不想写一个写一个众人皆知的QuickSort代码来占篇幅（而且STL的sort高度优化、速度快）。对solution_2进行测试，运行时间是32秒，约为solution_1的1.5%的时间，

6、已经取得了几何数量级的进展。深入思考压抑住兴奋回头再仔细看看solution_2，你将发现一个大问题，那就是在solution_2里所有的元素都排序了！而事实上只需找出最大的1万个即可，我们不是做了很多无用功吗？应该怎么样来消除这些无用功？如果你一时没有头绪，那就让我慢慢引导你。首先，发掘一个事实：如果这个大数组本身已经按从大到小有序，那么数组的前1万个元素就是结果；然后，可以假设这个大数组已经从大到小有序，并将前1万个元素放到结果数组；再次，事实上这结果数组里放的未必是最大的一万个，因此需要将前1万个数字后续的元素跟结果数组的最小的元素比较，如果所有后续的元

7、素都比结果数组的最小元素还小，那结果数组就是想要的结果，如果某一后续的元素比结果数组的最小元素大，那就用它替换结果数组里最小的数字；最后，遍历完大数组，得到的结果数组就是想要的结果了。templatevoidsolution_3(TBigArr[],TResArr[]){//取最前面的一万个memcpy(ResArr,BigArr,sizeof(T)*RES_ARR_SIZE);//标记是否发生过交换boolbExchanged=true;//遍历后续的元素for(inti=RES_ARR_SIZE;i

8、tidx;//如果上一轮发生过交换if