Google面试题解说性能之二：分析问题

前面我们已经说了字符串运算和数学运算对性能的巨大影响，接下来我们看看分析程序，多思考给我们带来的好处。
如果我们做一个简单的分析就可以知道，在尾数从0到9的连续十个数字中，只有尾数为1的数字的1的个数比其它的数字多，那么我们可以以10个数为单位进行分隔，计算尾数为0的数字包含1的个数，其它的9个值就以此为基础计算：
public class GoogleFn {
    private static int MAX = 13200000;

    private static int MAX2 = MAX / 10;

    private static int count(int n) {
        int count = 0;
        while (n > 0) {
            int mod = n % 10;
            if (mod == 1)
                count++;
            n = n / 10;
        }
        return count;
    }

    private static void method1() {
        long start = System.currentTimeMillis();
        int result = 0;
        for (int i = 1; i < MAX; i++) {
            result += count(i);
            if (result == i) {
                System.out.println("Find " + i + ", " + (System.currentTimeMillis() - start) + "ms");
            }
        }
    }

    private static void method2() {
        long start = System.currentTimeMillis();
        int result = 0;
        for (int i = 0; i < MAX2; i++) {
            int number = i * 10;
            int value = count(number);
            for (int j = 0; j < 10; j++) {
                result += value;
                if (j == 1) {
                    result++;
                }
                int x = number + j;
                if (x != 0 && result == x) {
                    System.out.println("Find " + x + ", " + (System.currentTimeMillis() - start) + "ms");
                }
            }
        }
    }

    public static void main(String[] args) {
        method1();
        method2();
    }
}

运算结果：
Find 1, 0ms
Find 199981, 47ms
Find 199982, 47ms
Find 199983, 47ms
Find 199984, 47ms
Find 199985, 47ms
Find 199986, 47ms
Find 199987, 47ms
Find 199988, 47ms
Find 199989, 47ms
Find 199990, 47ms
Find 200000, 47ms
Find 200001, 47ms
Find 1599981, 454ms
Find 1599982, 454ms
Find 1599983, 454ms
Find 1599984, 454ms
Find 1599985, 454ms
Find 1599986, 454ms
Find 1599987, 454ms
Find 1599988, 454ms
Find 1599989, 454ms
Find 1599990, 454ms
Find 2600000, 766ms
Find 2600001, 766ms
Find 13199998, 4204ms
Find 1, 0ms
Find 199981, 0ms
Find 199982, 0ms
Find 199983, 0ms
Find 199984, 0ms
Find 199985, 0ms
Find 199986, 0ms
Find 199987, 0ms
Find 199988, 0ms
Find 199989, 0ms
Find 199990, 0ms
Find 200000, 0ms
Find 200001, 0ms
Find 1599981, 62ms
Find 1599982, 62ms
Find 1599983, 62ms
Find 1599984, 62ms
Find 1599985, 62ms
Find 1599986, 62ms
Find 1599987, 62ms
Find 1599988, 62ms
Find 1599989, 62ms
Find 1599990, 62ms
Find 2600000, 93ms
Find 2600001, 93ms
Find 13199998, 515ms

同样以1319998为例，前者花费的时间是后者的8倍以上，因为每10个数，我们只需要计算一次1的个数，所以差不多只需要1/10的时间，但是后者的逻辑比较复杂一些，多了一些中间变量的使用，并且多了一个判断条件。
如果你不具备深厚的数学功底，对于算法并不精通，有时候对问题进行简单分析就可能大幅度的提高性能。

评论

1 楼 cepvoggg 2008-11-19