关于3层for循环优化问题的讨论 |
您所在的位置:网站首页 › 内大外小怎么判断 › 关于3层for循环优化问题的讨论 |
¶前言
同学发来一道面试题,找了一些资料看了看,最终也没得到正确的结果。大致参考了末尾链接1和2的内容,自个分析总结了一下,没有完全解出来,还是先贴出来,请高手过路时顺便解答吧。 ¶关于如下优化问题讨论 1234567for (int i = 0; i < 1000; i++) { for (int j = 0; j < 100; j++) { for (int k = 0; k < 10; k++) { function(i, j, k); } }} ¶分两种情况讨论: 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 中的内大外小优化,优化方案如下: 1234567for (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 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |