面试题讨论(一)

     首先，请JE上的高手、老鸟们原谅我把这道题拿出来讨论，也许，这题对你们来说只是小菜一碟，我却是觉得这种题目比较少见，我也不太清楚。但是，我想拿出来与大家分享下，讨论讨论，希望能挖掘出它的原理，让不清楚的小鸟们长长见识，当然也包括我，呵呵！
    
      这是一道用友的面试题。题目是：请优化下面代码，并给出原因：
  
     

                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);\
                          }
                     }
                   }
      

      这道题优化起来也许很容易，但要说出其中的原理我觉得比较难，希望能看到更多的是原理方面的讨论，越深刻越好！

 

评论

42 楼 wkwj520 2010-12-04  

把循环次数最少的放到外面；另外可以把i++换成++i。

41 楼 taolei0628 2010-12-04  

初始化、比较、蛋疼。

40 楼 aws 2010-12-03  

原本
10000，1000,100
是在i=1，j=1,k=99的時候，變成i=1，j=2,k=1
结果是
99
2
4
而改变循环顺序之后
100,1000,10000
在i=1，j=1,K=99之后，是i=1，j=1，k=100
99
100
101
进行所谓优化之后，不论在毫秒级别提升了多少速度，但是结果的顺序却改变了

如果这个循环里执行的方法涉及到前后依赖的操作

那么这个改变符合不符合原本的业务要求，值得商榷

39 楼 抛出异常的爱 2010-12-02  

vootoss 写道

sam_kee 写道

就是把循环次数少的放在最外层也没啥用，刚才有个人提了三种方法，很好啊

大规模运算的时候能减少一些内存地址跳转的开销

抛出异常的爱 写道

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 性能的证明。但是如果您没有细看，就很容易会把两者混淆。

38 楼 vootoss 2010-12-02  

sam_kee 写道

就是把循环次数少的放在最外层也没啥用，刚才有个人提了三种方法，很好啊

大规模运算的时候能减少一些内存地址跳转的开销

37 楼 sam_kee 2010-12-02  

就是把循环次数少的放在最外层也没啥用，刚才有个人提了三种方法，很好啊

36 楼 vootoss 2010-12-02  

i++ , j++ , k++  都是要push/pop的 ，想办法换成 ++i , ++j , ++k,
同时调整循环位置就可以了

35 楼 aws 2010-09-15  

a123159521 写道

一般采用三层循环进行计算的，在实际的业务中一般是作为过滤条件，竟然程序数据已经到了W级别的了，必须对For循环进行优化，使用优化后的程序，可以少执行1000 000次，你说是不是一个优化.

这种过滤，还是插入临时表然后sql吧……

34 楼 aws 2010-09-15  

这种毫秒级别10%的提升有意义么？
一条执行时间以秒为单位的SQL语句就把你优化出来的这几毫秒给抵消了

33 楼 a123159521 2010-09-15  

一般采用三层循环进行计算的，在实际的业务中一般是作为过滤条件，竟然程序数据已经到了W级别的了，必须对For循环进行优化，使用优化后的程序，可以少执行1000 000次，你说是不是一个优化.

32 楼 抛出异常的爱 2010-09-15  

引用

采用优化策略却在时间上却提升了10%，虽然是毫妙级别的，
但是如果function是一个执行时间很长的程序，那么程序的提升将会很大.

压栈出栈提升10%
如果运算时间长
效率会提升很大....

这结论是怎么得出来的?

31 楼 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是一个执行时间很长的程序，那么程序的提升将会很大.

30 楼 pikachu 2010-09-15  

<div class="quote_title">躁动的绵羊 写道</div>
<div class="quote_div">
<p>     首先，请JE上的高手、老鸟们原谅我把这道题拿出来讨论，也许，这题对你们来说只是小菜一碟，我却是觉得这种题目比较少见，我也不太清楚。但是，我想拿出来与大家分享下，讨论讨论，希望能挖掘出它的原理，让不清楚的小鸟们长长见识，当然也包括我，呵呵！ <br>     <br>      这是一道用友的面试题。题目是：请优化下面代码，并给出原因： <br>   <br>      </p>
<pre name="code" class="java">                for(int i = 0;i&lt;10000;i++) {
                     for(int j = 0;j&lt;1000;j++) {
                          for(int k = 0;k&lt;100;k++) {
                             function(i,j,k);\
                          }
                     }
                   }
      </pre>
<p><br><br>      这道题优化起来也许很容易，但要说出其中的原理我觉得比较难，希望能看到更多的是原理方面的讨论，越深刻越好！</p>
<p> </p>
</div>
<p>没看到有任何需要优化的地方.程序不是跑的很好么?</p>
<p>除非整个程序设计都是错误的,不需要那么多循环</p>
<p> </p>

29 楼 flashing 2010-09-14  

这种题目挺无语的。实际当中尽量避免多重循环是一条重要的编码准则，另外还有一条重要的编码准则是：当性能问题没有成为问题前，不要做任何优化。
出现三重循环的时候应该考虑考虑是不是设计或者算法有问题。
几乎99%的时候性能取决于架构。

28 楼 qvjing520 2010-09-14  

用友的人是怎么说的？一楼的确实可以提高性能可以用计时器测一下

27 楼 weirhp 2010-09-14  

你们这么一优化，执行的结果还对嘛！！想想function的第一个参数是什么样的变化！！
这个优化？
是不是只需在循环前定义变量就OK吗？

26 楼 抛出异常的爱 2010-09-14  

参考:
http://www.iteye.com/topic/761731

25 楼 xiaoh08 2010-09-14  

zhlfz 写道

见过，个人觉得这个比较 好

for(int i = 0;i<100;i++) {   

    for(int j = 0;j<1000;j++) {   

          
          for(int k = 0;k<10000;k++) {   



         }   

    }   

   }

我觉得下面的会更好一些

int i=0,j=0,k=0;
for(i = 0;i<100;i++) {   

    for(j = 0;j<1000;j++) {   

          
          for(k = 0;k<10000;k++) {   



         }   

    }   

   }

24 楼 pouyang 2010-09-14  

瑞友（用友收购的公司）约我去面试，外包做项目，我还去吗？（现在也在做外包）

23 楼 javavaj 2010-09-14  

垃圾回收更及时