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

//排序

文章评论

“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
每天工作4小时的程序员
每天工作4小时的程序员
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
总结2014中国互联网十大段子
总结2014中国互联网十大段子
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
漫画:程序员的工作
漫画:程序员的工作
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
程序员和编码员之间的区别
程序员和编码员之间的区别
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
程序员应该关注的一些事儿
程序员应该关注的一些事儿
10个调试和排错的小建议
10个调试和排错的小建议
我的丈夫是个程序员
我的丈夫是个程序员
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
中美印日四国程序员比较
中美印日四国程序员比较
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
旅行,写作,编程
旅行,写作,编程
代码女神横空出世
代码女神横空出世
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
Java程序员必看电影
Java程序员必看电影
鲜为人知的编程真相
鲜为人知的编程真相
程序员都该阅读的书
程序员都该阅读的书
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
 程序员的样子
程序员的样子
程序员的鄙视链
程序员的鄙视链
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
老程序员的下场
老程序员的下场
我是如何打败拖延症的
我是如何打败拖延症的
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
一个程序员的时间管理
一个程序员的时间管理
编程语言是女人
编程语言是女人
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有