MILY: 宋體; mso-font-kerning: 18.0pt; mso-bidi-font-family: 宋體">Google面試題解說性能之一：字符串運算VS數字運算

看到JavaEye上的幾個人在討論算法問題，其中一個就是Google的一個面試題，我也試了一下，而且可能比一般人試得程度更深一些，借這個題目簡單的說說幾個性能問題。這個是第一個，后面還會繼續幾個其它的討論。討論只是提點一下，主要還是要你自己讀源代碼并比較不同的實現為什么會有這么大的差別。
注意，程序的運行結果是在JDK1.4.2上的，其它版本的JDK的運行結果可能稍有不同。

先看代碼：
public class GoogleFn {
    private static int MAX = 13200000;

    private static int count1(int number) {
        int result = 0;
        String target = number + "";
        int index = target.indexOf("1");
        while (index >= 0) {
            result++;
            index = target.indexOf("1", index + 1);
        }
        return result;
    }

    private static int count2(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 += count1(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 = 1; i < MAX; i++) {
            result += count2(i);
            if (result == i) {
                System.out.println("Find " + i + ", " + (System.currentTimeMillis() - start) + "ms");
            }
        }
    }

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

運行結果
Find 13199998, 4187ms

我們以最后一個找到的數字為例，前者的時間是后者的3倍，代碼的其它部分完全一樣，區別就是前者是轉換為字符串查找1的個數，后者使用數學的取模運算計算。

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

文章來源于領測軟件測試網 http://www.kjueaiud.com/