一道简单的面试题

   前几天有位朋友跟我聊天说，最近他去面试遇到一个面试题，叫我帮他分析一下，是一道Java的面试题目；题目是这样的：请对以下的代码进行优化
原题代码如下

for (int i = 0; i < 1000; i++)
   for (int j = 0; j < 100; j++)
       for (int k = 0; k < 10; k++)
           log(i * j * k);

对于以上的代码，我给出了两个优化方案，优化一代码如下

for (int i = 0; i < 10; i++)
   for (int j = 0; j < 100; j++)
       for (int k = 0; k < 1000; k++)
           log(i * j * k);

优化二代码如下

int i, j, k;
for (i = 0; i < 10; i++)
   for (j = 0; j < 100; j++)
       for (k = 0; k < 1000; k++)
           log(i * j * k);

首先先来分析一下这三段代码，如下三个表
原题代码分析表

变量	实例化(次数)	初始化(次数)	比较(次数)	自增(次数)
i	1	1	1000	1000
j	1000	1000	1000 * 100	1000 * 100
k	1000 * 100	1000 * 100	1000 * 100 * 10	1000 * 100 * 10

优化一代码分析表

变量	实例化(次数)	初始化(次数)	比较(次数)	自增(次数)
i	1	1	10	10
j	10	10	10 * 100	10 * 100
k	10 * 100	10 * 100	10 * 100 * 1000	10 * 100 * 1000

优化二代码分析表

变量	实例化(次数)	初始化(次数)	比较(次数)	自增(次数)
i	1	1	10	10
j	1	10	10 * 100	10 * 100
k	1	10 * 100	10 * 100 * 1000	10 * 100 * 1000

    从以上三个表的分析看，优化一的性能和优化二比原代码性能好，其中优化二的性能是最好的。从而也可以说在以上的条件下，将大的循环放在内侧，小的循环放在外侧，其性能会提高；减少变量的实例化，其性能也会提高。对于以上的优化，如果在循环次数少的情况下，其运行出来的效果不大；而在循环次数较多的情况下，则其效果是比较明显的。
    以上是我自己对该题的一个优化和分析，如果大家有更好的优化方法或我又错误的地方，请大家多多指教。

评论

61 楼 yang02301 2010-12-03  

crane.ding 写道

   前几天有位朋友跟我聊天说，最近他去面试遇到一个面试题，叫我帮他分析一下，是一道Java的面试题目；题目是这样的：请对以下的代码进行优化
原题代码如下

for (int i = 0; i < 1000; i++)
   for (int j = 0; j < 100; j++)
       for (int k = 0; k < 10; k++)
           log(i * j * k);

对于以上的代码，我给出了两个优化方案，优化一代码如下

for (int i = 0; i < 10; i++)
   for (int j = 0; j < 100; j++)
       for (int k = 0; k < 1000; k++)
           log(i * j * k);

优化二代码如下

int i, j, k;
for (i = 0; i < 10; i++)
   for (j = 0; j < 100; j++)
       for (k = 0; k < 1000; k++)
           log(i * j * k);

首先先来分析一下这三段代码，如下三个表
原题代码分析表

变量	实例化(次数)	初始化(次数)	比较(次数)	自增(次数)
i	1	1	1000	1000
j	1000	1000	1000 * 100	1000 * 100
k	1000 * 100	1000 * 100	1000 * 100 * 10	1000 * 100 * 10

优化一代码分析表

变量	实例化(次数)	初始化(次数)	比较(次数)	自增(次数)
i	1	1	10	10
j	10	10	10 * 100	10 * 100
k	10 * 100	10 * 100	10 * 100 * 1000	10 * 100 * 1000

优化二代码分析表

变量	实例化(次数)	初始化(次数)	比较(次数)	自增(次数)
i	1	1	10	10
j	1	10	10 * 100	10 * 100
k	1	10 * 100	10 * 100 * 1000	10 * 100 * 1000

    从以上三个表的分析看，优化一的性能和优化二比原代码性能好，其中优化二的性能是最好的。从而也可以说在以上的条件下，将大的循环放在内侧，小的循环放在外侧，其性能会提高；减少变量的实例化，其性能也会提高。对于以上的优化，如果在循环次数少的情况下，其运行出来的效果不大；而在循环次数较多的情况下，则其效果是比较明显的。
    以上是我自己对该题的一个优化和分析，如果大家有更好的优化方法或我又错误的地方，请大家多多指教。

数读得越多，怎么脑袋的含水量就越多呢，

中国白领的悲哀啊！

我对上面的优化就非常简单：

   System.out.println("");

60 楼 sam_kee 2010-12-02  

javaeye，我爱你，在这里学到很多东西，也很有激励

59 楼 mercyblitz 2010-10-01  

<div class="quote_title">linghongli 写道</div>
<div class="quote_div">
<pre name="code" class="java"> int i, j, k;   
for (i = 0; i &lt; 10; i++)
{     
    if(i==0) 
    {
       log(0) ;
       continue;
    }
   else
    {  
       for (j = 1; j &lt; 100; j++)   
         for (k = 1; k &lt; 1000; k++)   
             log(i * j * k);
     }
}</pre>
 
<p> </p>
</div>
<p> </p>
<p>各位大大，编译器连这个都不能做的话，那就没有意义了。</p>
<p> </p>
<p>所以不要讨论这个没有必要的话题。</p>

58 楼 qn_lf 2010-10-01  

我个人觉得楼主写得很好，虽然是个简单的问题，但是楼主一步步分析的很透彻。支持楼主。

57 楼 nurenok 2010-09-15  

优化的第一原则，不要优化

56 楼 Qian_络此 2010-09-15  

  怎么说的都不一样，我都看晕了，上面说的优化方案一和二到底能不能做到优化呢？

55 楼 a123159521 2010-09-15  

代码如下:
/*
* 0.0.0 ~99.9.0
* 执行次数 100*10*1=1000次
* 执行时间 812
*/
public void doThing(){
for(int i = 0;i<10000;i++) {
     for(int j = 0;j<1000;j++) {
          for(int k = 0;k<100;k++) {
             function(i,j,k);
          }
     }
   }
}

/*
* 0.0.0 ~ 0.9.99
* 执行次数 1*10*100=1000次
* 执行时间 703
*/
public void doOpThing(){
for(int i = 0;i<100;i++) {
     for(int j = 0;j<1000;j++) {
          for(int k = 0;k<10000;k++) {
             function(i,j,k);
          }
     }
   }
}

/*
* 0.0.0 ~ 0.9.99
* 执行次数 1*10*100=1000次
* 执行时间 703
*/
public void doOp2Thing(){
int i,j,k;
for(i = 0;i<100;i++) {
     for(j = 0;j<1000;j++) {
          for(k = 0;k<10000;k++) {
             function(i,j,k);
          }
     }
   }
}
其实这道题的目的并不是让你写出优化的方法，而是考你JVM的编译解析原理.
/ Method descriptor #6 ()V
  // Stack: 4, Locals: 4
  public void doThing();
     0  iconst_0             --将int型0推送至栈顶
     1  istore_1 [i]           --将栈顶int型数值存入第二个本地变量
     2  goto 44              --无条件转移
     5  iconst_0             --将int型0推送至栈顶
     6  istore_2 [j]           --将栈顶int型数值存入第三个本地变量
     7  goto 34              --无条件转移
    10  iconst_0             --将int型0推送至栈顶
    11  istore_3 [k]          --将栈顶int型数值存入第四个本地变量
    12  goto 25             --无条件转移
    15  aload_0 [this]        --将第一个引用类型本地变量推送至栈顶
    16  iload_1 [i]            --将第二个int型本地变量推送至栈顶
    17  iload_2 [j]            --将栈顶int型数值存入第三个本地变量
    18  iload_3 [k]            --将栈顶int型数值存入第四个本地变量
19  invokevirtual org.yclframework.auth.test.dao.ibatis.Optimize.function(int, int, int) : void [24] –执行方法
[以上执行过程都是一致的，两个方法]
    22  iinc 3 1 [k]    --将指定int型变量增加指定值,这里是++
    25  iload_3 [k]    --将第四个int型本地变量推送至栈顶
    26  bipush 100    --将单字节的常量值(-128~127)推送至栈顶
    28  if_icmplt 15   --比较栈顶两int型数值大小，当结果小于0时跳转
    31  iinc 2 1 [j]    --将指定int型变量增加指定值,这里是++
    34  iload_2 [j]    --将栈顶int型数值存入第三个本地变量
    35  sipush 1000   --将一个短整型常量值(-32768~32767)推送至栈顶
    38  if_icmplt 10   --比较栈顶两int型数值大小，当结果小于0时跳转
    41  iinc 1 1 [i]    --将指定int型变量增加指定值,这里是++
    44  iload_1 [i]    --将栈顶int型数值存入第二个本地变量
    45  sipush 10000  --将一个短整型常量值(-32768~32767)推送至栈顶
    48  if_icmplt 5    --比较栈顶两int型数值大小，当结果小于0时跳转
    51  return        --方法返回
      Line numbers:
        [pc: 0, line: 17]
        [pc: 5, line: 18]
        [pc: 10, line: 19]
        [pc: 15, line: 20]
        [pc: 22, line: 19]
        [pc: 31, line: 18]
        [pc: 41, line: 17]
        [pc: 51, line: 24]
      Local variable table:
        [pc: 0, pc: 52] local: this index: 0 type: org.yclframework.auth.test.dao.ibatis.Optimize
        [pc: 2, pc: 51] local: i index: 1 type: int
        [pc: 7, pc: 41] local: j index: 2 type: int
        [pc: 12, pc: 31] local: k index: 3 type: int
编译成Calss的doThing()，其与doOpThing()唯一不同的是执行顺序，其执行顺序如下:
    22  iinc 3 1 [k]
    25  iload_3 [k]
    26  sipush 10000
    29  if_icmplt 15
    32  iinc 2 1 [j]
    35  iload_2 [j]
    36  sipush 1000
    39  if_icmplt 10
    42  iinc 1 1 [i]
    45  iload_1 [i]
    46  bipush 100
    48  if_icmplt 5
51  return
doOpThing()与doOp2Thing()的执行顺序一模一样.
在出入栈操作中，doThing出入栈如下:
变量    出入栈次数 /比较次数
K        100*1000*10000
J        1000*10000
I        10000
在出入栈操作中，doOpThing的出入栈如下:
变量    出入栈次数 /比较次数
K       10000*1000*100
J        1000*100
I        100
其实For循环里面使用的都是局部变量，其变量采用的是本地变量，只初始化一次
接下来都是出入栈和比较的操作，大家可以看到出入栈和比较次数都是相当快的.
采用优化策略却在时间上却提升了10%，虽然是毫妙级别的，但是如果function是一个执行时间很长的程序，那么程序的提升将会很大.

54 楼 laodizhuq 2010-09-15  

优化，如果是纯粹的代码优化，我觉得这个题目没有什么意义。
现实中如果要优化，我们得现搞清楚原先这段代码要做什么，根据代码的目标然后提出优化方案。

比如楼主的这个题目，我们就需要搞清楚这个方法的目的是要否要输出遍历值
如果是要遍历值，那么可以这么写：

StringBuffer sb = new StringBuffer(1024);
for (int i = 0; i < 1000; i++){
   for (int j = 0; j < 100; j++){  
       for (int k = 0; k < 10; k++){  
           sb.append(i * j * k);
           sb.append("\n");
        }
   }
}
log(sb.toString());

纯粹的代码优化还是少做，意义不是非常大，除非是严重性能问题。（当然有些人有代码洁癖，另论）。
优化应该是根据功能目的，对原有功能进行更高效的方式实现，所以原先代码实现的目标要先搞清楚。

53 楼 笑我痴狂 2010-09-14  

laoshifu 写道

实例化次数计算不对，对于java来说，for语句的初始化只是执行一次。所以对于原代码，优化一和优化二实例化变量的实例化次数都是一。不对之处，多多指教。

你确定吗？

52 楼 polaris1119 2010-09-13  

JE帐号 写道

大家数学都很好啊.
看见log就想起对数.我只想起日志... ...

有同感。见到只想到日志，没想到对数……

51 楼 shake822 2010-04-20  

wangzaixiang 写道

想起某位大师关软件优化的一段话：

1、编写代码时，不要进行优化。
2、如果没有给你带来麻烦，就不要优化。

说实在的，上面的代码，在99%的情况下，是不需要进行优化的。如果你的情况正好是那个1%，那么你

是有這個印象,嘿嘿.我也被面試過這道題,當時只是把最小的循環放在外面,最大的放在裡面,沒有考慮太多.
也覺的沒有必要考慮的那么複雜了

50 楼 强强爱妍妍 2010-04-16  

int buf[] = new int[1000];
for(int x=1; x<1000; x++)
{
    buf[x] = log(x);
}

for (int i = 0; i < 1000; i++)  
   for (int j = 0; j < 100; j++)  
       for (int k = 0; k < 10; k++)  
           buf[i] + buf[j] + buf[k]; 

49 楼 抛出异常的爱 2010-04-15  

java -server StupidThreadTest 

public class StupidThreadTest {
    public static void doSomeStuff() {
        double uselessSum = 0;
        for (int i=0; i<1000; i++) {
            for (int j=0;j<1000; j++) {
                uselessSum += (double) i + (double) j;
            }
        }
    }
    public static void main(String[] args) throws InterruptedException {
        doSomeStuff();
        
        int nThreads = Integer.parseInt(args[0]);
        Thread[] threads = new Thread[nThreads];
        for (int i=0; i<nThreads; i++)
            threads[i] = new Thread(new Runnable() {
                public void run() { doSomeStuff(); }
            });
        long start = System.currentTimeMillis();
        for (int i = 0; i < threads.length; i++)
            threads[i].start();
        for (int i = 0; i < threads.length; i++)
            threads[i].join();
        long end = System.currentTimeMillis();
        System.out.println("Time: " + (end-start) + "ms");
    }
}
      

引用

表面上看， doSomeStuff() 方法可以给线程分点事做，所以我们能够从 StupidThreadBenchmark 的运行时间推导出多线程调度开支的一些情况。但是，因为 uselessSum 从没被用过，所以编译器能够判断出 doSomeStuff 中的全部代码是死的，然后把它们全部优化掉。一旦循环中的代码消失，循环也就消失了，只留下一个空空如也的 doSomeStuff。表 1 显示了使用客户机和服务器方式执行 StupidThreadBenchmark 的性能。两个 JVM 运行大量线程的时候，都表现出差不多是线性的运行时间，这个结果很容易被误解为服务器 JVM 比客户机 JVM 快 40 倍。而实际上，是服务器编译器做了更多优化，发现整个 doSomeStuff 是死代码。虽然确实有许多程序在服务器 JVM 上会提速，但是您在这里看到的提速仅仅代表一个写得糟糕的评测，而不能成为服务器 JVM 性能的证明。但是如果您没有细看，就很容易会把两者混淆。

48 楼 playboyb 2010-04-12  

上次去深圳一家软件公司面试，正好里面有这么一道题。
当时写的答案就是LZ给出的第二个优化方法。
   今天在这里看到这么牛人的回复，才发现自己写的答案跑题了。
汗一个先，顺便说一句，里面的log(i*j*k),我以为是日志，就没想到是Math.log().

47 楼 ggggqqqqihc 2010-04-10  

抛出异常的爱 写道

jakend 写道

抛出异常的爱 写道

呸。。。。

干嘛呢？

见太多人胡说八道。。。。。。
出题的人脑也不正常

赞同抛老，大家用电脑计算一下log(0)吧

46 楼 thevone 2010-04-07  

kingdu_12 写道

JE帐号 写道

int i, j, k, m;  
for (i = 0; i < 10; i++){
   for (j = 0; j < 100; j++){
	   m=i*j;
	   for (k = 0; k < 100; k++){
		   log(m * k);
	   }
   }
}

应该是正解。

支持！

45 楼 王者之剑 2010-04-07  

windywany 写道

int ii = 1000, jj = 100, kk = 10, sum = ii * jj * kk, iii = 0, kkk = 0, jjj = 0;

	     for (ii = 0, jj = 0, kk = 0; kk < sum; kk++) {

		kkk = kk % 10;

		if (kkk == 0 && kk > 0) {
		    jj++;
		    jjj = jj % 100;
		    if (jjj == 0) {
			ii++;
			iii = ii%1000;
		     }
		}
                log(iii * jjj * kkk));
	      }

优化是这样做的,这是O(n) 和 O(n3)的区别,n3 表示n的三次方.

44 楼 王者之剑 2010-04-07  

搞笑
1.假设log的执行要一秒，有没有算过i,j,k要多大才能节省出有效的时间来？假设要1分钟呢？
2.如果程序的执行顺序是不可变的，你能这样改吗？
  原题执行了1000个log(0)以后很快遇到log(1)
  你改了以后要执行100000个log(0)以后才能遇难到log(1)
离开了一个合理的逻辑界定的业务范围谈什么优化？

当然不是说这个程序不能再提高速度
这个程序的目的是执行
log(0*0*0);
log(0*0*1);
log(0*0*2);
...
log(999*99*9);
这样一序列的函数调用

43 楼 wujiazhao88 2010-04-06  

都很厉害。这个是循环的挑战损耗时间的问题

42 楼 helin 2010-04-06  

我又来了.....优化得怎么样了?