关于3层for循环优化问题的讨论

前言

同学发来一道面试题,找了一些资料看了看,最终也没得到正确的结果。大致参考了末尾链接1和2的内容,自个分析总结了一下,没有完全解出来,还是先贴出来,请高手过路时顺便解答吧。

关于如下优化问题讨论

1
2
3
4
5
6
7
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 100; j++) {
for (int k = 0; k < 10; k++) {
function(i, j, k);
}
}
}

分两种情况讨论:

  1. function(i, j, k)中i, j, k参数不参与function函数体代码执行;
  2. 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
2
3
4
5
6
7
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 100; j++) {
for (int k = 0; k < 1000; k++) {
function(i, j, k);
}
}
}

则,此时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

Enjoy it ? Donate me ! 求鼓励,求支持!
0%