关闭

关闭

封号提示

内容

首页 从10亿个浮点数中找出最大的1万个.doc

从10亿个浮点数中找出最大的1万个.doc

从10亿个浮点数中找出最大的1万个.doc

上传者: 天是无限高 2012-03-27 评分1 评论0 下载43 收藏0 阅读量49 暂无简介 简介 举报

简介:本文档为《从10亿个浮点数中找出最大的1万个doc》,可适用于IT/计算机领域,主题内容包含从亿个浮点数中找出最大的万个这是一道似易实难的题目一般同学最容易中的陷阱就是没有重视这个“亿”字。因为有亿个单精度浮点数元素的数组在位平台上已经达到符等。

从亿个浮点数中找出最大的万个这是一道似易实难的题目一般同学最容易中的陷阱就是没有重视这个“亿”字。因为有亿个单精度浮点数元素的数组在位平台上已经达到GB之巨在常见计算机平台(如Win)上声明一个这样的数组将导致堆栈溢出。正确的解决方法是分治法比如每次处理万个数然后再综合起来。不过这不是本文要讨论的主旨所以本文把上题的亿改为亿把浮点数改为整数这样可以直接地完成这个问题有利于清晰地讨论相关算法的优化(注)。不假思索       拿到这道题马上就会想到的方法是建立一个数组把亿个数装起来然后用for循环遍历这个数组找出最大的万个数来。原因很简单因为如果要找出最大的那个数就是这样解决的而找最大的万个数只是重复万遍而已。template<classT>voidsolution(TBigArr,TResArr){for(inti=i<RESARRSIZEi){intidx=ifor(intj=ij<BIGARRSIZEj){if(BigArrj>BigArridx)idx=j}ResArri=BigArridxstd::swap(BigArridx,BigArri)}}设BIGARRSIZE = 亿RESARRSIZE = 万运行以上算法已经超过分钟(注)远远超过我们的可接受范围。稍作思考从上面的代码可以看出跟SelectSort算法的核心代码是一样的。因为SelectSort是一个O(n^)的算法(solution的时间复杂度为O(n*m)因为solution没有将整个大数组全部排序)而我们又知道排序算法可以优化到O(nlogn)那们是否可以从这方面入手使用更快的排序算法如MergeSor、QuickSort呢?但这些算法都不具备从大至小选择最大的N个数的功能因此只有将亿个数按从大到小用QuickSort排序然后提取最前面的万个。template<classT,classI>voidsolution(TBigArr,TResArr){std::sort(BigArr,BigArrBIGARRSIZE,std::greaterequal())memcpy(ResArr,BigArr,sizeof(T)*RESARRSIZE)}因为STL里的sort算法使用的是QuickSort在这里直接拿来用了是因为不想写一个写一个众人皆知的QuickSort代码来占篇幅(而且STL的sort高度优化、速度快)。对solution进行测试运行时间是秒约为solution的的时间已经取得了几何数量级的进展。深入思考       压抑住兴奋回头再仔细看看solution你将发现一个大问题那就是在solution里所有的元素都排序了!而事实上只需找出最大的万个即可我们不是做了很多无用功吗?应该怎么样来消除这些无用功?       如果你一时没有头绪那就让我慢慢引导你。首先发掘一个事实:如果这个大数组本身已经按从大到小有序那么数组的前万个元素就是结果然后可以假设这个大数组已经从大到小有序并将前万个元素放到结果数组再次事实上这结果数组里放的未必是最大的一万个因此需要将前万个数字后续的元素跟结果数组的最小的元素比较如果所有后续的元素都比结果数组的最小元素还小那结果数组就是想要的结果如果某一后续的元素比结果数组的最小元素大那就用它替换结果数组里最小的数字最后遍历完大数组得到的结果数组就是想要的结果了。template<classT>voidsolution(TBigArr,TResArr){取最前面的一万个memcpy(ResArr,BigArr,sizeof(T)*RESARRSIZE)标记是否发生过交换boolbExchanged=true遍历后续的元素for(inti=RESARRSIZEi<BIGARRSIZEi){intidx如果上一轮发生过交换则最小元素将发生变化需要重新找否则最小元素仍然是ResArridxif(bExchanged){找出ResArr中最小的元素intj记录ResArr中最小元素的下标for(idx=,j=j<RESARRSIZEj){if(ResArridx>ResArrj)idx=j}}这个后续元素比ResArr中最小的元素大则替换。if(BigArri>ResArridx){bExchanged=trueResArridx=BigArri}elsebExchanged=false}}       上面的代码使用了一个布尔变量bExchanged标记是否发生过交换这是一个前文没有谈到的优化手段用以标记元素交换的状态可以大大减少查找ResArr中最小元素的次数。也对solution进行测试一下结果用时秒左右(不使用bExchanged则高达分钟)远小于solution的用时。深思熟虑       在进入下一步优化之前分析一下solution的成功之处。第一、solution的算法只遍历大数组一次即它是一个O(n)的算法而solution是O(n*m)的算法solution是O(nlogn)的算法可见它在本质上有着天然的优越性第二、在solution中引入了bExchanged这一标志变量从测试数据可见引入bExchanged减少了约的时间这是一个非常大的成功。       上面这段话绝非仅仅说明了solution的优点更重要的是把solution的主要矛盾摆上了桌面为什么一个O(n)的算法效率会跟O(n*m)的算法差不多(不使用bExchanged)?为什么使用了bExchanged能够减少的时间?带着这两个问题再次审视solution的代码发现bExchanged的引入实际上减少了如下代码段的执行次数:for(idx=,j=j<RESARRSIZEj){if(ResArridx>ResArrj)idx=j}上面的代码段即是查找ResArr中最小元素的算法分析它可知这是一个O(n)的算法到此时就水落石出了!原来虽然solution是一个O(n)的算法但因为内部使用的查找最小元素的算法也是O(n)的算法所以就退化为O(n*m)的算法了。难怪不使用bExchanged使用的时间跟solution差不多这也从反面证明了solution被上面的这一代码段导致性能退化。使用了bExchanged之后因为减少了很多查找最小元素的代码段执行所以能够节省的时间!       至此可知元凶就是查找最小元素的代码段但查找最小元素是必不可少的操作在这个两难的情况下该怎么去优化呢?答案就是保持结果数组(即ResArr)有序那样的话最小的元素总是最后一个从而省去查找最小元素的时间解决上面的问题。但这也引入了一个新的问题:保持数组有序的插入算法的时间复杂度是O(n)的虽然在这个问题里插入的数次比例较小但因为基数太大(亿)这一开销仍然会令本方案得不偿失。       难道就没有办法了吗?记得小学解应用题时老师教导过我们如果解题没有思路那就多读几遍题目。再次审题注意到题目并没有要求找到的最大的万个数要有序(注)这意味着可以通过如下算法来解决:)        将BigArr的前万个元素复制到ResArr并用QuickSort使ResArr有序并定义变量MinElemIdx保存最小元素的索引并定义变量ZoneBeginIdx保存可能发生交换的区域的最小索引)        遍历BigArr其它的元素如果某一元素比ResArr最小元素大则将ResArr中MinElemIdx指向的元素替换如果ZoneBeginIdx == MinElemIdx则扩展ZoneBeginIdx)        重新在ZoneBeginIdx至RESARRSIZE元素段中寻找最小元素并用MinElemIdx保存其它索引)        重复)直至遍历完所有BigArr的元素。依上算法写代码如下:template<classT,classI>voidsolution(TBigArr,TResArr){取最前面的一万个memcpy(ResArr,BigArr,sizeof(T)*RESARRSIZE)排序std::sort(ResArr,ResArrRESARRSIZE,std::greaterequal())最小元素索引unsignedintMinElemIdx=RESARRSIZE可能产生交换的区域的最小索引unsignedintZoneBeginIdx=MinElemIdx遍历后续的元素for(unsignedinti=RESARRSIZEi<BIGARRSIZEi){这个后续元素比ResArr中最小的元素大则替换。if(BigArri>ResArrMinElemIdx){ResArrMinElemIdx=BigArriif(MinElemIdx==ZoneBeginIdx)ZoneBeginIdx查找最小元素unsignedintidx=ZoneBeginIdxunsignedintj=idxfor(j<RESARRSIZEj){if(ResArridx>ResArrj)idx=j}MinElemIdx=idx}}}       经过测试同样情况下solution用时约秒较solution效率略高总算不负一番努力。苦想冥思       这次优化从solution产生的输出来入手。把solution的输出写到文件查看后发现数组基本无序了。这说明在程序运行一定时间后频繁的替换几乎将原本有序的结果数组全部换血。结果数组被替换的元素越多查找最小元素要遍历的范围就越大当被替换的元素个数接近结果数组的大小时solution就退化成solution。因为solution很快退化也就直接导致它的效率没有本质上的提高。       找出了原因就应该找出一个解决的办法。通过上面的分析知道solution和solution最消耗时间的是查找最小元素这一操作将它减少(或去除)才有可能从本质上提高效率。这样思路又回到保持结果数组有序这一条老路上来。在上一节我们谈到保持数组有序的插入算法将带来大量的元素移动频繁的插入操作将使这一方法在效率上得不偿失。有没有办法让元素移动去掉呢?答案也是有的那就是使用链表。这时新的问题又来了链表因为是非随机存取数据结构插入前寻找位置的算法又是O(n)的。解决新的问题的答案是使用AVL树但AVL树虽然插入和查找都是O(logn)可是需要在插入后进行调整保持平衡这又是一个耗费大量时间的操作。分析到现在发现我们像进了迷宫左冲右突都找不到突破口。       现在请静下来想一想如果思考结果没有跳出上面这个怪圈那我不幸地告诉你:你被我误导了。这个故意的误导是要告诫大家:进行算法优化必须时刻保持自己头脑清醒否则时刻都有可能陷入这样的迷宫当中。现在跳出这个怪圈重新思考根据前文的分析可知目标是减少(或去除)查找最小元素的操作次数(或查找时间)途径是让ResArr保持有序难点在于给ResArr排序太费时。反过来想一想是否需要时刻保持ResArr有序?答案为否因为当查找最小元素需要遍历的范围较小时速度还是很快的这样就犯不着在每替换一个元素的时候都排序一次而仅需要在无序元素较多的时候适时地排序即可(即保持查找最小元素要遍历的范围较小)。这个思想有用吗?写代码来测试一下:template<classT,classI>voidsolution(TBigArr,TResArr){同solution略这个后续元素比ResArr中最小的元素大则替换。if(BigArri>ResArrMinElemIdx){ResArrMinElemIdx=BigArriif(MinElemIdx==ZoneBeginIdx)ZoneBeginIdx太多杂乱元素的时候排序if(ZoneBeginIdx<){std::sort(ResArr,ResArrRESARRSIZE,std::greater())ZoneBeginIdx=MinElemIdx=RESARRSIZEcontinue}同solution略}}       代码中的是经过试验得出的最好数值即在有个元素无序的时候进行一次排序。测试的结果令人惊喜用时仅毫秒左右约为solution的五分之一这也证明了上述思想是正确的。殚思极虑       脚步永远向前在取得solution这样的成果之后仍然有必要分析和优化它。对这一看似已经完美的算法进行下一次优化要从哪里着手?这时候要借助于性能剖分工具了常用的有Intel的VTune以及Microsoft Visual C自带的profile等。使用MS profile对solution分析产生的报告如下(略去一些无关数据):          Func             FuncChild           Hit        Time            Time            Count  Function                         main (algoobj)                        solution(int *                         STL::sort(int *,       ……可以发现sort函数的调用用去了将近的时间这表明sort函数是问题所在优化应该从这里着手。但正如前文所说STL的sort已经高度优化速度很快了再对他作优化是极难的而且sort函数里又调用了其它STL内部函数如蛛丝般牵来绕去读得懂已经不是一般人可完成的了优化从何谈起?       我们不能左右天气但我们可以左右心情我们不能修改sort函数但我们可以控制sort的调用。再看看solution里对sort的调用有没有什么蛛丝马迹可寻:       std::sort( ResArr, ResArr  RESARRSIZE, std::greater() )这个调用是把结果数组ResArr重新排序一遍。需要把整个ResArr完全重新排序吗?答案是需要的但可以不使用这个方法。因为ResArr里的元素绝大部分是有序的(结合上文可知前面的元素都有序)待排序的只是。只要把这个数据重新排序然后将前后两个有序数组归并为一个有序数组即可(归并算法的时间复杂度为O(nm))将因为排序的数据量较少而大大节约时间。写代码如下:***#include<algorithm>*outputiteratormerge(inputiteratorstart,inputiteratorend,inputiteratorstart,*inputiteratorend,outputiteratorresult)**outputiteratormerge(inputiteratorstart,inputiteratorend,inputiteratorstart,*inputiteratorend,outputiteratorresult,StrictWeakOrderingcmp)*template<classT,classI>voidsolution(TBigArr,TResArr){同solution略太多杂乱元素的时候排序if(ZoneBeginIdx<){std::sort(ResArr,ResArrRESARRSIZE,std::greater())std::merge(ResArr,ResArr,ResArr,ResArrRESARRSIZE,BigArr,std::greater())memcpy(ResArr,BigArr,sizeof(T)*RESARRSIZE)同solution略}}       经测试solutio的运行时间为毫秒左右比solution快了将近一半通过profile分析报告计算sort函数和merge函数的占用时间总计约为执行时间的远小于solution的占用时间。结束语       一番努力之后终于将一个原来需要近一个小时才能解决的问题用毫秒完成文章到这里要完结不过上述算法仍有可优化的余地这就要读者朋友自己去挖掘了。我希望看到这篇文章的人不仅仅是赞叹算法的奇妙更希望能够学会算法优化的方法和技巧。对于算法优化的方法我总结如下(仅供参考及抛砖引玉之用):不断地否定自己的方法全文减少重复计算solution不要做没要求你做的事solution 深化对需求的理解solution温故而知新多重读自己的算法代码solution从程序的输出(或者中间结果)里找突破solution时刻保持头脑清醒常常跳出习惯的框框solution善于使用工具solution养成解决一个问题思考多个方案的习惯全文。最后要讲的一点就是STL里提供了一个可以直接完成这一问题的算法nthelement。经测试nthelement在大数组比较小的时候速度比以上算法都要快但在大数组尺寸为亿的时候所用的时间为秒左右是solution运行时间的倍。原因在于nthelenemt的实现方法跟本文介绍的算法大不相同有兴趣的朋友可以去阅读其源码。建议大家在一般情况下使用STL的nthelement它在数量为十万级的时候仍有极好的性能。参考资料:        侯捷 《STL源码剖析》 华中科技大学出版社 年月        Anany Levitin 潘彦译 《算法设计与分析基础》 清华大学出版社 年月        http:jobcsdnnetnhtml注:        此题目版权归出题人或者其单位所有        本文所有的优化都针对于平均情况即大数组由随机数构成且无序        所有测试均设BIGARRSIZE = 亿RESARRSIZE = 万测试的机器配置为:CPU PEE G   M memoryHyperThreading Enabled操作系统:Windows  pro编译器: MS VC   spSTL库: STLport 可从我的博客http:lanphadaybokeecom下载本文所有算法源码和测试程序。        如果要求有序可以通过先找出结果再对结果排序完成要求注意:ResArr中的元素是按照从大到小排列的。

类似资料

编辑推荐

[闻一多寻觅时空最佳点].刘介民.扫描版.pdf

[王国维独上高楼].潘知常.扫描版.pdf

[宋词之旅].李元洛.扫描版.pdf

100个成功的品牌策划.pdf

[史学与红学].唐德刚.扫描版.pdf

职业精品

精彩专题

结婚彩礼真有那么重要吗?

原创于西周而后沿袭至今的彩礼,虽然被一部分家长奉为圭臬,但越来越多的年轻人对结婚必须要彩礼不以为然。彩礼引发的社会矛盾越来越受到关注,结婚是自己的事,如人饮水冷暖自知,至于要不要彩礼或者要多少彩礼,因人而异,因财力而已,不可一概而论。

用户评论

0/200
    暂无评论
上传我的资料

精选资料

热门资料排行换一换

  • 幸福女人的芳香生活 珍藏版[扫…

  • 幸福发美人[扫描版].pdf

  • 心学之思王阳明哲学的阐释[扫描版…

  • 心态的能量[扫描版].pdf

  • 心理学与驭心术 掌控他人的诀窍…

  • 心理画绘画心理分析图典[扫描版]…

  • 小巫厨房蜜语[扫描版].pdf

  • 小胖妞的减肥日志[扫描版].pdf

  • 小空间家具装饰收纳[扫描版].p…

  • 资料评价:

    / 8
    所需积分:0 立即下载

    意见
    反馈

    返回
    顶部