从一道笔试题谈算法优化（上）

我会带着你远行 2022-02-15 10:48 183阅读 0赞

因为受到经济危机的影响，我在 bokee.com 的博客可能随时出现无法访问的情况；因此将2005年到2006年间在 bokee.com 撰写的博客文章全部迁移到 csdn 博客中来，本文正是其中一篇迁移的文章。

声明：本文最初发表于《电脑编程技巧与维护》2006年第5期，版本所有，如蒙转载，敬请连此声明一起转载，否则追究侵权责任。

# 从一道笔试题谈算法优化（上） #

作者：赖勇浩（http://blog.csdn.net/lanphaday）

## 引子 ##

每年十一月各大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() );