Chinaunix首页 | 论坛 | 博客
  • 博客访问: 962385
  • 博文数量: 128
  • 博客积分: 10012
  • 博客等级: 上将
  • 技术积分: 2050
  • 用 户 组: 普通用户
  • 注册时间: 2008-10-15 17:49
文章分类

全部博文(128)

文章存档

2011年(16)

2009年(57)

2008年(55)

分类: C/C++

2008-10-18 12:37:59

每年十一月各大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的用时。
阅读(1193) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~