解惑

解己之惑,解人之惑

Google面试题解说性能之八:工欲善其事必先利其器

按照原先的计划,这个系列只应该有四篇,但是后来打算多写一些,把这个问题研究透彻,所以出现了总结篇先于其它篇的情况。
这次我们按照总结篇中提到的方法实际演示下代码覆盖工具如何帮助我们优化程序提高性能,先给出我们未经好好优化的程序:
package com.jiehoo.util;

public class GoogleFn {
private static final int MAX = 2600002;

private static long start = System.currentTimeMillis();

private static int[] bases = new int[15];

private static int[] values = new int[15];

static {
bases[0] = 0;
bases[1] = 10;
values[0] = 0;
values[1] = 1;
for (int i = 2; i < values.length; i++) {
bases[i] = (int) Math.pow(10, i);
values[i] = i * (int) Math.pow(10, i – 1);
}
}

    private static int fn(int number) {
if (number < 10) {
return number > 0 ? 1 : 0;
}
String s = number + “”;
int length = s.length();
int end = Integer.parseInt(s.substring(1, length));
int x = s.charAt(0) – ‘0’;
int result = 0;
if (x == 1) {
result = values[length – 1] + fn(end) + (end + 1);
} else {
result = values[length – 1] * x + bases[length – 1] + fn(end);
}
return result;
}

private static void print(int n) {
System.out.println(“Find ” + n + “, ” + (System.currentTimeMillis() – start) + “ms”);
}

public static void findMatch() {
for (int i = 1; i < MAX; i++) {
int result = fn(i);
if (result == i) {
print(i);
}
}
}
}

使用单元测试工具和代码覆盖工具运行一下,得到代码覆盖报告:
google_fn_code_coverage
从这个报告,我们看到fn方法的哪些部分被执行的次数最多,findMatch方法中直接调用fn的次数是2600001次,fn方法实际调用的次数是15860005,可以看到fn被自身递归调用了很多次(大致是数字的位数减一),最开始的那个判断是否小于10的部分我们不太可能优化,而那个取得数字的长度,尾数以及最高位的数字的调用执行的次数很多,是否可以优化呢?答案是肯定的,在单次执行的时候,那个字符串操作的速度的影响可以忽略不计,但是一旦是千万级以上,就很可观了,我们修改一下代码:
private static int fn(int number) {
if (number < 10) {
return number > 0 ? 1 : 0;
}
int length = 1;
int x = number / bases[length];
while (x > 0) {
length++;
x = number / bases[length];
}
x = number / bases[length – 1];
int end = number % bases[length – 1];
int result = 0;
if (x == 1) {
result = values[length – 1] + fn(end) + (end + 1);
} else {
result = values[length – 1] * x + bases[length – 1] + fn(end);
}
return result;
}
这个其实就是我们第一个例子说到的,如果可以使用数字运算,那么它往往比字符串运算要快(但是字符串运算有时候更简单直观)。
修改后运行的最后一个输出:
Find 2600001, 1953ms
而修改前的是:
Find 2600001, 14859ms
这个就可以看出这个差异的巨大了,相差了7倍多。
使用好的工具往往可以极大的帮助我们解决问题,找到问题的症结所在。

  1. Google面试题解说性能之一:字符串运算VS数字运算

  2. Google面试题解说性能之二:分析问题

  3. Google面试题解说性能之三:不要小看循环中的任何一个语句

  4. Google面试题解说性能之四:优化无止境

  5. Google面试题解说性能之五:人比电脑聪明

  6. Google面试题解说性能之六:数学显神威

  7. Google面试题解说性能之七:缓存中间结果

  8. Google面试题解说性能之八:工欲善其事必先利其器

  9. Google面试题解说性能之总结

(Visited 134 times, 1 visits today)

8 Comments

  1. 呵呵,我还有三篇没看完呢
    看来得抓紧了

  2. 呵呵,不用急,已经写完了

  3. 终于看完了
    虽然这个求单个比较快
    但还是比前面的慢
    javaeye的答案算法才看了一半
    没有注视,有些晦涩
    看完了再和你讨论

  4. 如果是求单个的fn值,那这个方法实现应该是最快的
    如果是遍历求匹配的n值的话,那还是例子五的那个最快

  5. 唉,又把那个c的答案看了一遍
    还是没看懂
    尤其是那个f和cal函数
    想放弃了

  6. 呵呵,算法有时候是很难理解的,实际上我也没有看过那些C的实现。
    我的这个算法是想了好几天才想出来的 :em47:

  7. 他那个f函数,虽然我看懂是干吗用的
    但我不知道为什么那么写(是不是用了数值分析?)
    至于cal就看不懂了,只能猜猜他是不是跳过了很多本身1的个数为零,且和前面算出的和加起来不可能使它们相等的数,至于怎么跳过去的就不明白了

  8. 可能也是使用到了一些分析,但是没有把分析的过程写出来。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

© 2019 解惑

本主题由Anders Noren提供向上 ↑