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

Posted on | In
Symbols count in article: 4.6k | Reading time ≈ 4 mins.

前言

同学发来一道面试题，找了一些资料看了看，最终也没得到正确的结果。大致参考了末尾链接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

0%