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

使用单元测试工具和代码覆盖工具运行一下，得到代码覆盖报告：

从这个报告，我们看到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倍多。
使用好的工具往往可以极大的帮助我们解决问题，找到问题的症结所在。

---

作者: Cherami
原载: 解惑
版权所有。转载时必须以链接形式注明作者和原始出处及本声明。
分类: Java

评论

1 楼 jiazhigang 2008-06-19  

引用

使用单元测试工具和代码覆盖工具

能分享这两个是什么工具吗