注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

简约男人

简约,不能简单

 
 
 

日志

 
 
关于我

一个过分渴望被理解的人其实就是一个软弱的人, 勇往直前的力量来自斩钉截铁的决心,不是来自别人的理解.

网易考拉推荐

一小时与250毫秒的差别(转)  

2009-12-16 17:35:34|  分类: 算法学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

出处:http://hi.baidu.com/lctigerose/blog/index/13

        每年十一月各大IT公司都不约而同、争后恐后地到各大高校进行全国巡回招聘。与此同时,网上也开始出现大量笔试面试题;网上流传的题目往往都很精巧,既能让考查基础知识,又在平淡中隐含了广阔的天地供优秀学生驰骋。

        这两天在网上淘到一道笔试题目(注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 = i+1; 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效率略高,总算不负一番努力。


苦想冥思


        这次优化从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              Func+Child            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(n+m)),将因为排序的数据量较少而大大节约时间。写代码如下:

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毫秒完成,文章到这里要完结,不过上述算法仍有可优化的余地,这就要读者朋友自己去挖掘了。我希望看到这篇文章的人不仅仅是赞叹算法的奇妙,更希望能够学会算法优化的方法和技巧。对于算法优化的方法,我总结如下(仅供参考及抛砖引玉之用):

不断地否定自己的方法[全文]

减少重复计算[solution_3];

不要做没要求你做的事[solution_3]; 

深化对需求的理解[solution_4];

温故而知新,多重读自己的算法代码[solution_4];

从程序的输出(或者中间结果)里找突破[solution_5];

时刻保持头脑清醒,常常跳出习惯的框框[solution_5];

善于使用工具[solution_6];

养成解决一个问题思考多个方案的习惯[全文]。

最后要讲的一点就是STL里提供了一个可以直接完成这一问题的算法——nth_element。经测试,nth_element在大数组比较小的时候速度比以上算法都要快,但在大数组尺寸为1亿的时候所用的时间为1.3秒左右,是solution_6运行时间的5倍。原因在于nth_elenemt的实现方法跟本文介绍的算法大不相同,有兴趣的朋友可以去阅读其源码。建议大家在一般情况下使用STL的nth_element,它在数量为十万级的时候仍有极好的性能。

 

参考资料:


        [1] 侯捷 《STL源码剖析》 华中科技大学出版社 2002年6月

        [2] Anany Levitin 潘彦[译] 《算法设计与分析基础》 清华大学出版社 2004年6月

        [3] http://job.csdn.net/n/20051216/31105.html

注:


        [1] 此题目版权归出题人或者其单位所有

        [2] 本文所有的优化都针对于平均情况,即大数组由随机数构成且无序

        [3] 所有测试均设BIG_ARR_SIZE = 1亿,RES_ARR_SIZE = 1万,测试的机器配置为:CPU P4EE 3.0G + 512 M memory,HyperThreading Enabled,操作系统:Windows 2000 pro,编译器: MS VC++ 6.0 + sp6,STL库: STLport 4.6.2;可从我的博客http://lanphaday.bokee.com下载本文所有算法源码和测试程序。

        [4] 如果要求有序,可以通过先找出结果,再对结果排序完成要求

  评论这张
 
阅读(1016)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017