`

一道简单的面试题

    博客分类：
  • JAVA
面试J#软件测试thread 
阅读更多
   前几天有位朋友跟我聊天说，最近他去面试遇到一个面试题，叫我帮他分析一下，是一道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);

首先先来分析一下这三段代码，如下三个表
原题代码分析表
变量实例化(次数)初始化(次数)比较(次数)自增(次数)
i1110001000
j100010001000 * 1001000 * 100
k1000 * 1001000 * 1001000 * 100 * 101000 * 100 * 10

优化一代码分析表
变量实例化(次数)初始化(次数)比较(次数)自增(次数)
i111010
j101010 * 10010 * 100
k10 * 10010 * 10010 * 100 * 100010 * 100 * 1000

优化二代码分析表
变量实例化(次数)初始化(次数)比较(次数)自增(次数)
i111010
j11010 * 10010 * 100
k110 * 10010 * 100 * 100010 * 100 * 1000

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

首先先来分析一下这三段代码，如下三个表
原题代码分析表
变量实例化(次数)初始化(次数)比较(次数)自增(次数)
i1110001000
j100010001000 * 1001000 * 100
k1000 * 1001000 * 1001000 * 100 * 101000 * 100 * 10

优化一代码分析表
变量实例化(次数)初始化(次数)比较(次数)自增(次数)
i111010
j101010 * 10010 * 100
k10 * 10010 * 10010 * 100 * 100010 * 100 * 1000

优化二代码分析表
变量实例化(次数)初始化(次数)比较(次数)自增(次数)
i111010
j11010 * 10010 * 100
k110 * 10010 * 100 * 100010 * 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  
我又来了.....优化得怎么样了?
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    cocos2d-x 一道简单面试题，触摸事件的重新分发

    本文通过一道面试题来探讨如何有效地管理和控制触摸事件，尤其是在多层界面交互的情况下。题目是：“当弹出一个新窗口时，如何屏蔽掉下面层的触摸事件？”这个问题涉及到对cocos2d-x触摸事件系统的基本理解和应用。 ...

    js面试题面试题面试题

    根据给定的文件信息，以下是对每一道JS面试题的知识点进行详细解析： ### 第一题：编写一个方法求一个字符串的字节长度 #### 解析： 在这道题目中，我们需要编写一个函数来计算字符串的字节长度。这里的重点在于...

    一道微软面试题

    根据给定的信息，我们可以推断出这是一道与算法相关的微软面试题目，主要涉及的是如何在1到100000的范围内寻找一个缺失的数字。从标题和描述来看，这个问题旨在测试应聘者的逻辑思维能力和解决问题的能力。下面将...

    整理C#面试题10套

    "C#面试题10套" 本资源摘要信息涵盖了C#面试题10套，涵盖了C#、.NET、面试题等知识点，详细解释了每一个问题和答案。 问题一： 密码问题，涉及到逻辑思维和规则应用。问题中给出了五个字母K、L、M、N、O，要求在...

    算法面试题实用知识库分享

    这个问题是算法面试题中的一道经典题目，开发者需要掌握这个问题的解决方法。 算法笔记_面试题_2.移动零 本篇笔记主要介绍了移动零问题的解决方法，包括问题分析、解决方法等。这个问题是算法面试题中的一道常见...

    Java 面试题 Java 面试题

    根据给定的文件内容，我们可以总结出一系列与Java面试相关的知识点。下面将详细解析每一道题目涉及的关键概念。 ### 第一部分：基础知识 #### 1. final, finally, finalize的区别 - **final**: 用于声明变量、方法...

    hadoop2面试题 - 2012腾讯笔试的一道算法题.pdf

    ### hadoop2面试题 - 2012腾讯笔试的一道算法题 #### 背景与题目概述 本文档提供了2012年腾讯笔试中一道关于字符串处理的算法题，该题目要求将字符串中的所有大写字母移动到字符串的末尾，同时保持其他字符的相对...

    这是一道广为流传的微软面试题

    本篇文章将详细探讨一道经典的微软面试题——链表的反转，并通过分析其背后的逻辑和技术要点，帮助读者更好地理解和掌握这一问题。 #### 题目背景与解析 题目要求：给定一个链表的头结点，反转该链表，并返回反转...

    软件工程师经典面试题

    11. 这是一道简单的减法计算题。9305 - 5126 - 1107 = 3072，答案是C。 12. 这是一道百分比和小数计算题。4.5的40%加上2/3的Y%等于10的20%，即1.8 + (2/3)*Y% = 2，解得Y% = 30%，所以答案是D。 13. 这是一道年龄...

    幼儿园教师资格证面试真题10套.pdf

    通过对这道面试真题的详细分析，我们可以看出，幼儿园教师资格证面试不仅仅是一个简单的知识测试，更是对教师全面素质的深入考察。面试真题10套中的每一道题目都有其独特之处，但都离不开对教学理念、教学技能和互动...

    暴雪面试题整理

    线程间通信则相对简单，可以直接访问共享内存。 【用户点击网页链接的流程】 用户点击链接后，浏览器解析URL，发起HTTP/HTTPS请求到服务器。服务器接收到请求后，处理请求，可能涉及到动态脚本执行、数据库查询等，...

    Golang 面试题汇编

    记一道字节跳动的算法面试题 多协程查询切片问题 对已经关闭的的chan进行读写，会怎么样？为什么？ 简单聊聊内存逃逸？ 字符串转成byte数组，会发生内存拷贝吗？ http包的内存泄漏 sync.Map 的用法 Golang 理论 Go...

    百度面试题大收集算法

    这是一道经典的二维数组处理问题，可以应用Kadane's algorithm进行解决，寻找连续子数组的最大和。对于01矩阵，目标是找到连续的1的最大数量。 6. **判断点分十进制IP合法性**： IP地址是四个0-255之间的数字，用...

    vcc软件软件工程师面试题[文].pdf

    首先，让我们来看一道常见的面试题——实现一个`strcpy`函数。`strcpy`函数在C/C++编程中扮演着基础且重要的角色，用于复制字符串。面试官可能会要求面试者现场编写这个函数，以此来评估面试者的编程基础和对内存...

    C/C++程序员应聘常见面试题深入剖析

    通过这些面试题，我们可以看到，即使是看似简单的编程任务，也需要全面考虑多种因素。对于面试者来说，不仅要扎实掌握基础知识，还要具备问题分析和解决的能力。只有这样，才能在面试中展现出自己的专业素养和技术...

    高质量c++（内含面试题）

    - **简单应用程序命名规则**：根据不同的操作系统环境，制定相应的命名规范。 #### 四、表达式和基本语句 - **运算符优先级**：理解不同运算符的优先级顺序，合理使用括号以明确计算过程。 - **复合表达式**：在单...

    一道华为的面试题 关于JAVA来的

    根据给定的信息，本文将详细解析这道华为的面试题，并深入探讨其涉及的Java编程技巧及相关的知识点。 ### 领域背景 在软件开发过程中，字符串处理是非常常见的任务之一。无论是处理配置文件、JSON数据还是其他类型...

    一道优雅面试题分析js中fn()和return fn()的区别.docx

    首先，让我们看一个简单的例子： ```javascript var i = 0; var result = fn(); function fn() { console.log(result); i++; } ``` 这个例子中，我们定义了一个函数 `fn`，它将在调用时输出当前的 `result` 值，...

    golang面试题集合.zip

    记一道字节跳动的算法面试题 多协程查询切片问题 对已经关闭的的chan进行读写，会怎么样？为什么？ 简单聊聊内存逃逸？ 字符串转成byte数组，会发生内存拷贝吗？ http包的内存泄漏 sync.Map 的用法 Golang 理论 Go...

    CC++程序员应聘常见面试题.docx

    首先，让我们来看一道经典的面试题——手动实现`strcpy`函数。`strcpy`函数是C语言中用于复制字符串的库函数，它的正确实现是衡量一个C/C++程序员基本功的重要指标。题目1中，面试者被要求在有限的内存空间内复制...

Magicbox
Global site tag (gtag.js) - Google Analytics