`

一道简单的面试题

    博客分类：
  • 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注入
评论
41 楼 miaow 2010-04-06  
该优化的不优化，拍脑袋想性能？
先问自己，性能代价在哪里，++和>的判断代价和*、log()哪个是消耗性能的关键？
靠常识拍脑袋驱动也该先去优化减少*和log()的操作。

如果log是日志，在最外边判断log等级先。缓存外边两层的乘法结果。
如果log是对数，数学上先改成加法，然后缓存1000个值加就是了。
40 楼 抛出异常的爱 2010-04-06  
jakend 写道
抛出异常的爱 写道
呸。。。。


干嘛呢？

见太多人胡说八道。。。。。。
出题的人脑也不正常 
		count=0;
		int sub = 0;
		StringBuilder builder = new StringBuilder();
		start = System.nanoTime();
		for(int i = 0 ; i < 1000 ; i++){
			for(int j = 0 ; j< 100 ; j++){
				sub = i * j;
				count = 0;
				builder.append(count);
				builder.append(NEWLINE);
				count += sub;
				builder.append(count);
				builder.append(NEWLINE);
				count += sub;
				builder.append(count);
				builder.append(NEWLINE);
				count += sub;
				builder.append(count);
				builder.append(NEWLINE);
				count += sub;
				builder.append(count);
				builder.append(NEWLINE);
				count += sub;
				builder.append(count);
				builder.append(NEWLINE);
				count += sub;
				builder.append(count);
				builder.append(NEWLINE);
				count += sub;
				builder.append(count);
				builder.append(NEWLINE);
				count += sub;
				builder.append(count);
				builder.append(NEWLINE);
				count += sub;
				builder.append(count);
				builder.append(NEWLINE);				
			}
			
		}
		System.out.println(System.nanoTime()-start);
		System.out.println("-------------");
		Thread.sleep(10000);
		System.out.println(builder.toString());


39 楼 ggggqqqqihc 2010-04-06  
你们难道都不知道log(0)等于几？有意义吗？
38 楼 JE帐号 2010-04-06  
大家数学都很好啊.
看见log就想起对数.我只想起日志... ...
37 楼 docong 2010-04-06  
log(i*j*k) = logi+logj+logk
36 楼 jakend 2010-04-06  
抛出异常的爱 写道
呸。。。。


干嘛呢？
35 楼 pujia12345 2010-04-06  
你写个带按摩试试不就好了。我使用的过程是PrintWriter.println(i*j*k);
3个方案10次平均下来：
A:675
B:665
C:659


34 楼 keyboard2000 2010-04-06  
是否可以用递归压栈暂存值的办法也减少计算次数呢？
33 楼 hubeicaolei 2010-04-06  
lyw985 写道
1.i,j,k必须从1开始

2.i*j*k是有重复的

3.log(i*j*k)=logi+logj+logk

这才是这道题的关键吧，像这种初始化的东西，根本相差不大



这个是正解,负数和零是没有对数的,所有从0开始计数的都不是最优的


i=1,j=2,k=3时的值和i=3,j=1,k=2的值是一样的

可以采用空间换时间的做法来进行优化

利用缓存数组可以减少很多工作量
32 楼 kingdu_12 2010-04-06  
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);
	   }
   }
}

应该是正解。
31 楼 whywen_MoJian 2010-04-06  
imjl 写道
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); 

i*j*k 当i=0 或者j=0, 或者k=0时，，都相当于log(0),,也就是log(0)重复计算了1000×100×10次，，，类似的重复计算太多

优化点应该是把log的重复计算降低



顶下
30 楼 jiafu0773 2010-04-06  
感觉差不多，现在的服务器一般内存都很大，不会在乎那么一丁点的损耗
29 楼 JE帐号 2010-04-06   
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);
	   }
   }
}
28 楼 lyw985 2010-04-06  
1.i,j,k必须从1开始

2.i*j*k是有重复的

3.log(i*j*k)=logi+logj+logk

这才是这道题的关键吧，像这种初始化的东西，根本相差不大
27 楼 helin 2010-04-06  
怎么还不如原来的了呢.......
26 楼 aninfeel 2010-04-06  
听说递减效率更好
25 楼 MyEyeOfJava 2010-04-06  
zhangkaitao 写道
测试机器 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

大家看看结果吧。



有理有据，看样子10  100 1000的循环优化还是有效果的。
24 楼 imjl 2010-04-06  
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); 

i*j*k 当i=0 或者j=0, 或者k=0时，，都相当于log(0),,也就是log(0)重复计算了1000×100×10次，，，类似的重复计算太多

优化点应该是把log的重复计算降低
23 楼 zhanghaocool 2010-04-05  
laoshifu 写道
实例化次数计算不对，对于java来说，for语句的初始化只是执行一次。所以对于原代码，优化一和优化二实例化变量的实例化次数都是一。不对之处，多多指教。


for语句的初始化只是执行一次，循环体执行不只一次，所以第2、3层循环不只初始化一次。
22 楼 wxwx1215 2010-04-05  
学习了，感觉优化还是有效果的饿，但是如果不是太大的循环的话必要性不是太大
发表评论

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

相关推荐

    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