`

一道简单的面试题

    博客分类：
  • 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注入
评论
21 楼 lyy3323 2010-04-05  
乱七八糟的呀。。。这样的优化只能说是“硬”优化吧。。
20 楼 zhangkaitao 2010-04-05  
测试机器 CPU P8700 @ 2.53GHZ  MEMORY 2GB 

public static void testFor0() {
        int count = 0;
        int i = 1;
        int j = 1;
        int k = 1;
        long startTime = System.nanoTime();
        for (; i <= 100; i++) 
            for (j = 1; j <= 1000; j++)
                for (k = 1; k <= 10000; k++) {
                    count++;
                }
        System.out.println("zero count==" + count);
        long endTime = System.nanoTime();
        System.out.println("zero time==== " + (endTime - startTime));
    }
    
    public static void testFor1() {
        int count = 0;
        int i = 1;
        int j = 1;
        int k = 1;
        long startTime = System.nanoTime();
        for (; i <= 10000; i++) 
            for (j = 1; j <= 1000; j++)
                for (k = 1; k <= 100; k++) {
                    count++;
                }
        System.out.println("first count==" + count);
        long endTime = System.nanoTime();
        System.out.println("first time==== " + (endTime - startTime));
    }
    
    public static void testFor2() {
        int count = 0;
        int i = 1;
        int j = 1;
        int k = 1;
        long startTime = System.nanoTime();
        for (; i <= 100; i++) 
            for (j = i; j <= 1000; j++)
                for (k = j; k <= 10000; k++) {
                    count++;
                }
        System.out.println("second count==" + count);
        long endTime = System.nanoTime();
        System.out.println("second time==== " + (endTime - startTime));
    }
    
    public static void testFor3() {
        int ii = 10000, jj = 1000, kk = 100, sum = ii * jj * kk, iii = 0, kkk = 0, jjj = 0;  
        int count = 0;
        long startTime = System.nanoTime();
        for (ii = 0, jj = 0, kk = 0; kk < sum; kk++) {  
            kkk = kk % 100;  
            if (kkk == 0 && kk > 0) {  
                jj++;  
                jjj = jj % 1000;  
                if (jjj == 0) {  
                    ii++;  
                    iii = ii%10000;  
                }
            }
            count++;
        }
        System.out.println("third count==" + count);
        long endTime = System.nanoTime();
        System.out.println("third time==== " + (endTime - startTime));
    }



结果

zero count==1000000000
zero time==== 858950788
first count==1000000000
first time==== 941317961
second count==900711700
second time==== 756062573
third count==1000000000
third time==== 6520663101 


    public static void testFor0() {
        int count = 0;
        int i = 1;
        int j = 1;
        int k = 1;
        long startTime = System.nanoTime();
        for (; i <= 10; i++) 
            for (j = 1; j <= 100; j++)
                for (k = 1; k <= 1000; k++) {
                    count++;
                }
        System.out.println("zero count==" + count);
        long endTime = System.nanoTime();
        System.out.println("zero time==== " + (endTime - startTime));
    }
    
    public static void testFor1() {
        int count = 0;
        int i = 1;
        int j = 1;
        int k = 1;
        long startTime = System.nanoTime();
        for (; i <= 1000; i++) 
            for (j = 1; j <= 100; j++)
                for (k = 1; k <= 10; k++) {
                    count++;
                }
        System.out.println("first count==" + count);
        long endTime = System.nanoTime();
        System.out.println("first time==== " + (endTime - startTime));
    }
    
    public static void testFor2() {
        int count = 0;
        int i = 1;
        int j = 1;
        int k = 1;
        long startTime = System.nanoTime();
        for (; i <= 10; i++) 
            for (j = i; j <= 100; j++)
                for (k = j; k <= 1000; k++) {
                    count++;
                }
        System.out.println("second count==" + count);
        long endTime = System.nanoTime();
        System.out.println("second time==== " + (endTime - startTime));
    }
    
    public static void testFor3() {
        int ii = 1000, jj = 100, kk = 10, sum = ii * jj * kk, iii = 0, kkk = 0, jjj = 0;  
        int count = 0;
        long startTime = System.nanoTime();
        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;  
                }
            }
            count++;
        }
        System.out.println("third count==" + count);
        long endTime = System.nanoTime();
        System.out.println("third time==== " + (endTime - startTime));
    }


结果
zero count==1000000
zero time==== 1811683
first count==1000000
first time==== 2361474
second count==905620
second time==== 2054730
third count==1000000
third time==== 7406249

大家看看结果吧。
19 楼 windywany 2010-04-05   
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的三次方.
18 楼 抛出异常的爱 2010-04-05  
呸。。。。

17 楼 qiaoqinqie 2010-04-05  
学习了 很不错
16 楼 yysolo 2010-04-05  
loga（MN）=logaM+logaN， 所以前面算过的结果可以保存
15 楼 szmq2 2010-04-05  
测试发现优化效果不是很大,也许Java中已经内部对循环进行了优化
14 楼 fei1502816 2010-04-05  
没感觉出有多大的优化.
13 楼 yangzhanchun 2010-04-05  
我认为：
1、特殊值不需要计算，比如=0，=1
2、最主要瓶颈的可能在log中，不管log输出到哪里，循环来上这么多次不行，要做缓冲。

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

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

12 楼 shuiguozheng 2010-04-05  
你们谁说的是对的啊！
11 楼 zhangkaitao 2010-04-05   
public static void testFor() {
        int count = 0;
        int i = 1;
        int j = 1;
        int k = 1;
        
        for (; i <= 4; i++) 
            for (j = i; j <= 4; j++)
                for (k = j; k <= 4; k++) {
                    count++;
                }
        /*
            111
            112
            113
            114
            122
            123
            124
            133
            134
            144
            222
            223
            224
            233
            234
            244
            333
            334
            344
            444
         */
        System.out.println("first==" + count);
        
        count = 0;
        for (i = 1; i <= 10; i++) 
            for (j = 1; j <= 100; j++)
                for (k = 1; k <= 1000; k++)
                    count++;
        System.out.println("second==" + count);
    }



如果可以排除重复的结果的话，可以采用排列组合的思想。
10 楼 beneo 2010-04-05  
wangzaixiang 写道
想起某位大师关软件优化的一段话：

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

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



有道理，我觉得这个优化看上去很没有区别。

此外，是不是应该看看bytecode，编译器有没有自己帮你做优化呢？？
9 楼 laoshifu 2010-04-05  
实例化次数计算不对，对于java来说，for语句的初始化只是执行一次。所以对于原代码，优化一和优化二实例化变量的实例化次数都是一。不对之处，多多指教。
8 楼 wangzaixiang 2010-04-05  
想起某位大师关软件优化的一段话：

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

说实在的，上面的代码，在99%的情况下，是不需要进行优化的。如果你的情况正好是那个1%，那么你
7 楼 wangzaixiang 2010-04-05  
至于优化二、优化三，对于Java/C这样的语言来说，应该是一样的。局部变量都不存在实例化的问题，因为它是在堆栈中分配的，在函数入口时就确定好了位置了。

换个加法试一试。

for (int i = 0; i < 10; i++)
   for (int j = 0; j < 100; j++) {
       int ij = i * j;
       int s = 0 - ij;
       for (int k = 0; k < 1000; k++)
           log(s+=ij);
   }
6 楼 topcloud 2010-04-04  
<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) ;
       <span style="color: #ff0000;"><strong>break;</strong></span>
    }
   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>
5 楼 linghongli 2010-04-04  
<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>
4 楼 風一樣的男子 2010-04-04  
langqing 写道
优化过的代码和原来的代码的输出结果是不是不一样了？log总次数一样，但顺序是不一样的。

i、j和k可以从1开始遍历，它们只要其中一个为0，i*j*k必然为0，这样会减少一些运算


一点启发
这样的话 k 从 2 开始遍历
因为 k = 1 还是 i*j 
int i, j, k;  
for (i = 0; i < 10; i++)  
   for (j = 1; j < 100; j++)  
       for (k = 2; k < 1000; k++)  
           log(i * j * k);

3 楼 crane.ding 2010-04-04  
magicway 写道
我是不是眼花了...优化代码一好像和优化代码二 一样的...

优化代码一是把变量实例化放在for循环里面，而优化代码二则是放在for循环外，所以你可以在表二和表三看到变量的实例化的次数是不相同的
2 楼 magicway 2010-04-04  
我是不是眼花了...优化代码一好像和优化代码二 一样的...
发表评论

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

相关推荐

    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. 这是一道年龄...

    暴雪面试题整理

    线程间通信则相对简单，可以直接访问共享内存。 【用户点击网页链接的流程】 用户点击链接后，浏览器解析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中，面试者被要求在有限的内存空间内复制...

    微软面试100题

    面试题1：水杯与玻璃杯的区别 在软件开发中，“水杯”与“玻璃杯”的类比，可以引申为抽象类与具体类的关系。抽象类定义了类的基本属性和方法，但不能实例化，而具体类则继承自抽象类，实现了抽象类中定义的所有...

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