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

太过爱你忘了你带给我的痛 2022-02-15 15:38 187阅读 0赞

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

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

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

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

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，它在数量为十万级的时候仍有极好的性能。

## 参考资料： ##

\[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。

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

[http_blog.csdn.net_lanphaday]: http://blog.csdn.net/lanphaday