MyException - 我的异常网
当前位置:我的异常网» Java Web开发 » 最近遇到一个笔试题,求高手解决!解决方案

最近遇到一个笔试题,求高手解决!解决方案(2)

www.MyException.Cn  网友分享于:2013-01-29  浏览:26次


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 );

//排序

文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有