¶前言
同学发来一道面试题,找了一些资料看了看,最终也没得到正确的结果。大致参考了末尾链接1和2的内容,自个分析总结了一下,没有完全解出来,还是先贴出来,请高手过路时顺便解答吧。
¶关于如下优化问题讨论
1 | for (int i = 0; i < 1000; i++) { |
¶分两种情况讨论:
- function(i, j, k)中i, j, k参数不参与function函数体代码执行;
- function(i, j, k)中i, j, k参数作为function函数体代码执行;
¶在情况1前提下,3层for循环代码的执行次数如下:
int i = 0; 执行 1 次
int j = 0; 执行 1 次
int k = 0; 执行 1 次
i < 1000; 执行 1000 次
i++; 执行 1000 次
j < 100; 执行 1000 x 100 次
j++; 执行 1000 x 100 次
k < 10; 执行 1000 x 100 x 10 次
k++; 执行 1000 x 100 x 10 次
function(i, j, k) 执行 1000 x 100 x 10 次
也即,如参考资料 1 中的叫法内小外大,
执行次数共: 1+1+1+(1000+1000x100+1000x100x10)x2+1000x100x10=3202003(次)
此时,由于function函数中i, j, k不参与函数体的运算,对于function函数来说,
可按照参考资料 1 中的内大外小优化,优化方案如下:
1 | for (int i = 0; i < 10; i++) { |
则,此时3层for循环代码的执行次数如下:
int i = 0; 执行 1 次
int j = 0; 执行 1 次
int k = 0; 执行 1 次
i < 10; 执行 10 次
i++; 执行 10 次
j < 100; 执行 10 x 100 次
j++; 执行 10 x 100 次
k < 1000; 执行 1000 x 100 x 10 次
k++; 执行 1000 x 100 x 10 次
function(i, j, k) 执行 1000 x 100 x 10 次
也即,如参考资料 1 中的叫法内大外小,
执行次数共: 1+1+1+(10+10x100+1000x100x10)x2+1000x100x10=3002023(次)
显然,"内大外小"的方式比"内小外大"的方式代码的执行次数少的多,
减少了: 3202003 - 3002023 = 199980(次)
当然,更加扇脸的是,此种方法,我师妹看过后来了句:
从代码规范角度来说,既然function(i, j, k)跟i, j, k都毛线关系,
只想执行N多次function函数体的部分,那弄一个for循环指定次数,一下不就完事了,这又何苦呢?
瞬间,懵逼~~~
按照这种分析,"内大外小"方式确实优化了不少,但这只是逻辑上的;在具体的测试中,
参考资料2中讨论使用时间判断方法(考量代码的执行时间比较),但我的测试结果显示:
这种方式不可靠,受JVM和具体平台环境的影响,每次的执行时间不一样且"内小外大"和
"内大外小"时间比较并不是总是一个大一个小。
¶在情况2前提下, function(i, j, k)中i, j, k参与方法体内运算
那么原题中,此时i的范围为[0, 1000), j的范围为[0, 100), k的范围为[0, 10);
若还按照情况1中的优化做法,完全错误,两种方案根本不等价。
情况2 的优化方案未解…
¶参考资料:
[1] http://www.debugease.com/j2se/301740.html
[2] http://bbs.csdn.net/topics/350159482