长沙口碑好的做网站公司哪家好,亚马逊跨境电商怎么开店,wordpress增加分类与标签,小米手机做网站服务器转载自#xff1a;http://blog.csdn.net/winsunxu/article/details/6219376点击打开链接 引子 每年十一月各大IT公司都不约而同、争后恐后地到各大高校进行全国巡回招聘。与此同时#xff0c;网上也开始出现大量笔试面试题#xff1b;网上流传的题目往往都很精巧#xff0c…转载自http://blog.csdn.net/winsunxu/article/details/6219376点击打开链接 引子 每年十一月各大IT公司都不约而同、争后恐后地到各大高校进行全国巡回招聘。与此同时网上也开始出现大量笔试面试题网上流传的题目往往都很精巧既能让考查基础知识又在平淡中隐含了广阔的天地供优秀学生驰骋。 这两天在网上淘到一1道笔试题目注1虽然真假未知但的确是道好题题目如下 从10亿个浮点数中找出最大的1万个。 这是一道似易实难的题目一般同学最容易中的陷阱就是没有重视这个“亿”字。因为有10亿个单精度浮点数元素的数组在32位平台上已经达到3.7GB之巨在常见计算机平台如Win32上声明一个这样的数组将导致堆栈溢出。正确的解决方法是分治法比如每次处理100万个数然后再综合起来。不过这不是本文要讨论的主旨所以本文把上题的10亿改为1亿把浮点数改为整数这样可以直接地完成这个问题有利于清晰地讨论相关算法的优化注2。 不假思索 拿到这道题马上就会想到的方法是建立一个数组把1亿个数装起来然后用for循环遍历这个数组找出最大的1万个数来。原因很简单因为如果要找出最大的那个数就是这样解决的而找最大的1万个数只是重复1万遍而已。 template class T void solution_1( T BigArr[], T ResArr[] ) { for( int i 0; i RES_ARR_SIZE; i ) { int idx i; for( int j i1; j BIG_ARR_SIZE; j ) { if( BigArr[j] BigArr[idx] ) idx j; } ResArr[i] BigArr[idx]; std::swap( BigArr[idx], BigArr[i] ); } } 设BIG_ARR_SIZE 1亿RES_ARR_SIZE 1万运行以上算法已经超过40分钟注3远远超过我们的可接受范围。 稍作思考 从上面的代码可以看出跟SelectSort算法的核心代码是一样的。因为SelectSort是一个O(n^2)的算法solution_1的时间复杂度为O(n*m)因为solution_1没有将整个大数组全部排序而我们又知道排序算法可以优化到O(nlogn)那们是否可以从这方面入手使用更快的排序算法如MergeSor、QuickSort呢但这些算法都不具备从大至小选择最大的N个数的功能因此只有将1亿个数按从大到小用QuickSort排序然后提取最前面的1万个。 template class T, class I void solution_2( T BigArr[], T ResArr[] ) { 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%的时间已经取得了几何数量级的进展。 深入思考 压抑住兴奋回头再仔细看看solution_2你将发现一个大问题那就是在solution_2里所有的元素都排序了而事实上只需找出最大的1万个即可我们不是做了很多无用功吗应该怎么样来消除这些无用功 如果你一时没有头绪那就让我慢慢引导你。首先发掘一个事实如果这个大数组本身已经按从大到小有序那么数组的前1万个元素就是结果然后可以假设这个大数组已经从大到小有序并将前1万个元素放到结果数组再次事实上这结果数组里放的未必是最大的一万个因此需要将前1万个数字后续的元素跟结果数组的最小的元素比较如果所有后续的元素都比结果数组的最小元素还小那结果数组就是想要的结果如果某一后续的元素比结果数组的最小元素大那就用它替换结果数组里最小的数字最后遍历完大数组得到的结果数组就是想要的结果了。 template class T void solution_3( T BigArr[], T ResArr[] ) { //取最前面的一万个 memcpy( ResArr, BigArr, sizeof(T) * RES_ARR_SIZE ); //标记是否发生过交换 bool bExchanged true; //遍历后续的元素 for( int i RES_ARR_SIZE; i BIG_ARR_SIZE; i ) { int idx; //如果上一轮发生过交换 if( bExchanged ) { //找出ResArr中最小的元素 int j; for( idx 0, j 1; j RES_ARR_SIZE; j ) { if( ResArr[idx] ResArr[j] ) idx j; } } //这个后续元素比ResArr中最小的元素大则替换。 if( BigArr[i] ResArr[idx] ) { bExchanged true; ResArr[idx] BigArr[i]; } else bExchanged false; } } 上面的代码使用了一个布尔变量bExchanged标记是否发生过交换这是一个前文没有谈到的优化手段——用以标记元素交换的状态可以大大减少查找ResArr中最小元素的次数。也对solution_3进行测试一下结果用时2.0秒左右不使用bExchanged则高达32分钟远小于solution_2的用时。 深思熟虑 在进入下一步优化之前分析一下solution_3的成功之处。第一、solution_3的算法只遍历大数组一次即它是一个O(n)的算法而solution_1是O(n*m)的算法solution_2是O(nlogn)的算法可见它在本质上有着天然的优越性第二、在solution_3中引入了bExchanged这一标志变量从测试数据可见引入bExchanged减少了约99.99%的时间这是一个非常大的成功。 上面这段话绝非仅仅说明了solution_3的优点更重要的是把solution_3的主要矛盾摆上了桌面——为什么一个O(n)的算法效率会跟O(n*m)的算法差不多不使用bExchanged为什么使用了bExchanged能够减少99.99%的时间带着这两个问题再次审视solution_3的代码发现bExchanged的引入实际上减少了如下代码段的执行次数 for( idx 0, j 1; j RES_ARR_SIZE; j ) { if( ResArr[idx] ResArr[j] ) idx j; } 上面的代码段即是查找ResArr中最小元素的算法分析它可知这是一个O(n)的算法到此时就水落石出了原来虽然solution_3是一个O(n)的算法但因为内部使用的查找最小元素的算法也是O(n)的算法所以就退化为O(n*m)的算法了。难怪不使用bExchanged使用的时间跟solution_1差不多这也从反面证明了solution_3被上面的这一代码段导致性能退化。使用了bExchanged之后因为减少了很多查找最小元素的代码段执行所以能够节省99.99%的时间 至此可知元凶就是查找最小元素的代码段但查找最小元素是必不可少的操作在这个两难的情况下该怎么去优化呢答案就是保持结果数组即ResArr有序那样的话最小的元素总是最后一个从而省去查找最小元素的时间解决上面的问题。但这也引入了一个新的问题保持数组有序的插入算法的时间复杂度是O(n)的虽然在这个问题里插入的数次比例较小但因为基数太大1亿这一开销仍然会令本方案得不偿失。 难道就没有办法了吗记得小学解应用题时老师教导过我们如果解题没有思路那就多读几遍题目。再次审题注意到题目并没有要求找到的最大的1万个数要有序注4这意味着可以通过如下算法来解决 1) 将BigArr的前1万个元素复制到ResArr并用QuickSort使ResArr有序并定义变量MinElemIdx保存最小元素的索引并定义变量ZoneBeginIdx保存可能发生交换的区域的最小索引 2) 遍历BigArr其它的元素如果某一元素比ResArr最小元素小则将ResArr中MinElemIdx指向的元素替换如果ZoneBeginIdx MinElemIdx则扩展ZoneBeginIdx 3) 重新在ZoneBeginIdx至RES_ARR_SIZE元素段中寻找最小元素并用MinElemIdx保存其它索引 4) 重复2)直至遍历完所有BigArr的元素。 依上算法写代码如下 template class T, class I void solution_4( T BigArr[], T ResArr[] ) { //取最前面的一万个 memcpy( ResArr, BigArr, sizeof(T) * RES_ARR_SIZE ); //排序 std::sort( ResArr, ResArr RES_ARR_SIZE, std::greater_equal() ); //最小元素索引 unsigned int MinElemIdx RES_ARR_SIZE - 1; //可能产生交换的区域的最小索引 unsigned int ZoneBeginIdx MinElemIdx; //遍历后续的元素 for( unsigned int i RES_ARR_SIZE; i BIG_ARR_SIZE; i ) { //这个后续元素比ResArr中最小的元素大则替换。 if( BigArr[i] ResArr[MinElemIdx] ) { ResArr[MinElemIdx] BigArr[i]; if( MinElemIdx ZoneBeginIdx ) --ZoneBeginIdx; //查找最小元素 unsigned int idx ZoneBeginIdx; unsigned int j idx 1; for( ; j RES_ARR_SIZE; j ) { if( ResArr[idx] ResArr[j] ) idx j; } MinElemIdx idx; } } } 经过测试同样情况下solution_4用时约1.8秒较solution_3效率略高总算不负一番努力。 因为受到经济危机的影响我在 bokee.com 的博客可能随时出现无法访问的情况因此将2005年到2006年间在 bokee.com 撰写的博客文章全部迁移到 csdn 博客中来本文正是其中一篇迁移的文章。 声明本文最初发表于《电脑编程技巧与维护》2006年第5期版本所有如蒙转载敬请连此声明一起转载否则追究侵权责任。 从一道笔试题谈算法优化下 作者赖勇浩http://blog.csdn.net/lanphaday 苦想冥思 这次优化从solution_4产生的输出来入手。把solution_4的输出写到文件查看后发现数组基本无序了。这说明在程序运行一定时间后频繁的替换几乎将原本有序的结果数组全部换血。结果数组被替换的元素越多查找最小元素要遍历的范围就越大当被替换的元素个数接近结果数组的大小时solution_4就退化成solution_3。因为solution_4很快退化也就直接导致它的效率没有本质上的提高。 找出了原因就应该找出一个解决的办法。通过上面的分析知道solution_3和solution_4最消耗时间的是查找最小元素这一操作将它减少或去除才有可能从本质上提高效率。这样思路又回到保持结果数组有序这一条老路上来。在上一节我们谈到保持数组有序的插入算法将带来大量的元素移动频繁的插入操作将使这一方法在效率上得不偿失。有没有办法让元素移动去掉呢答案也是有的——那就是使用链表。这时新的问题又来了链表因为是非随机存取数据结构插入前寻找位置的算法又是O(n)的。解决新的问题的答案是使用AVL树但AVL树虽然插入和查找都是O(logn)可是需要在插入后进行调整保持平衡这又是一个耗费大量时间的操作。分析到现在发现我们像进了迷宫左冲右突都找不到突破口。 现在请静下来想一想如果思考结果没有跳出上面这个怪圈那我不幸地告诉你你被我误导了。这个故意的误导是要告诫大家进行算法优化必须时刻保持自己头脑清醒否则时刻都有可能陷入这样的迷宫当中。现在跳出这个怪圈重新思考根据前文的分析可知目标是减少或去除查找最小元素的操作次数或查找时间途径是让ResArr保持有序难点在于给ResArr排序太费时。反过来想一想是否需要时刻保持ResArr有序答案为否因为当查找最小元素需要遍历的范围较小时速度还是很快的这样就犯不着在每替换一个元素的时候都排序一次而仅需要在无序元素较多的时候适时地排序即可即保持查找最小元素要遍历的范围较小。这个思想有用吗写代码来测试一下 template class T, class I void solution_5( T BigArr[], T ResArr[] ) { //同solution_4略 //这个后续元素比ResArr中最小的元素大则替换。 if( BigArr[i] ResArr[MinElemIdx] ) { ResArr[MinElemIdx] BigArr[i]; if( MinElemIdx ZoneBeginIdx ) --ZoneBeginIdx; //太多杂乱元素的时候排序 if( ZoneBeginIdx 9400 ) { std::sort( ResArr, ResArr RES_ARR_SIZE, std::greater() ); ZoneBeginIdx MinElemIdx RES_ARR_SIZE - 1; continue; } //同solution_4略 } 代码中的9400是经过试验得出的最好数值即在有600个元素无序的时候进行一次排序。测试的结果令人惊喜用时仅400毫秒左右约为solution_4的五分之一这也证明了上述思想是正确的。 殚思极虑 脚步永远向前在取得solution_5这样的成果之后仍然有必要分析和优化它。对这一看似已经完美的算法进行下一次优化要从哪里着手这时候要借助于性能剖分工具了常用的有Intel的VTune以及Microsoft Visual C自带的profile等。使用MS profile对solution_5分析产生的报告如下略去一些无关数据 Func FuncChild Hit Time % Time % Count Function --------------------------------------------------------- 37.718 1.0 3835.317 99.5 1 _main (algo.obj) 111.900 2.9 3220.082 83.6 1 solution_5(int * ... 0.000 0.0 3074.063 79.8 112 _STL::sort(int *,... …… 可以发现sort函数的调用用去了将近80%的时间这表明sort函数是问题所在优化应该从这里着手。但正如前文所说STL的sort已经高度优化速度很快了再对他作优化是极难的而且sort函数里又调用了其它STL内部函数如蛛丝般牵来绕去读得懂已经不是一般人可完成的了优化从何谈起 我们不能左右天气但我们可以左右心情我们不能修改sort函数但我们可以控制sort的调用。再看看solution_5里对sort的调用有没有什么蛛丝马迹可寻 std::sort( ResArr, ResArr RES_ARR_SIZE, std::greater() ); 这个调用是把结果数组ResArr重新排序一遍。需要把整个ResArr完全重新排序吗答案是需要的但可以不使用这个方法。因为ResArr里的元素绝大部分是有序的结合上文可知前面94%的元素都有序待排序的只是6%。只要把这600个数据重新排序然后将前后两个有序数组归并为一个有序数组即可归并算法的时间复杂度为O(nm)将因为排序的数据量较少而大大节约时间。写代码如下 template class T, class I void solution_6( T BigArr[], T ResArr[] ) { //同solution_5略 //太多杂乱元素的时候排序 if( ZoneBeginIdx 9400 ) { std::sort( ResArr 9400, ResArr RES_ARR_SIZE, std::greater() ); std::merge(ResArr, ResArr 9400, ResArr 9400, ResArr RES_ARR_SIZE, BigArr, std::greater() ); memcpy( ResArr, BigArr, sizeof(T) * RES_ARR_SIZE ); //同solution_5略 } 经测试solutio_6的运行时间为250毫秒左右比solution_5快了将近一半通过profile分析报告计算sort函数和merge函数的占用时间总计约为执行时间的19.6%远小于solution_5的占用时间。 结束语 一番努力之后终于将一个原来需要近一个小时才能解决的问题用250毫秒完成文章到这里要完结不过上述算法仍有可优化的余地这就要读者朋友自己去挖掘了。我希望看到这篇文章的人不仅仅是赞叹算法的奇妙更希望能够学会算法优化的方法和技巧。对于算法优化的方法我总结如下仅供参考及抛砖引玉之用 l 不断地否定自己的方法[全文] l 减少重复计算[solution_3] l 不要做没要求你做的事[solution_3] l 深化对需求的理解[solution_4] l 温故而知新多重读自己的算法代码[solution_4] l 从程序的输出或者中间结果里找突破[solution_5] l 时刻保持头脑清醒常常跳出习惯的框框[solution_5] l 善于使用工具[solution_6] l 养成解决一个问题思考多个方案的习惯[全文]。 最后要讲的一点就是STL里提供了一个可以直接完成这一问题的算法——nth_element。经测试nth_element在大数组比较小的时候速度比以上算法都要快但在大数组尺寸为1亿的时候所用的时间为1.3秒左右是solution_6运行时间的5倍。原因在于nth_elenemt的实现方法跟本文介绍的算法大不相同有兴趣的朋友可以去阅读其源码。建议大家在一般情况下使用STL的nth_element它在数量为十万级的时候仍有极好的性能。
