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 1, 16ms
Find 199981, 219ms
Find 199982, 219ms
Find 199983, 219ms
Find 199984, 219ms
Find 199985, 219ms
Find 199986, 219ms
Find 199987, 219ms
Find 199988, 219ms
Find 199989, 219ms
Find 199990, 219ms
Find 200000, 219ms
Find 200001, 219ms
Find 1599981, 1516ms
Find 1599982, 1516ms
Find 1599983, 1516ms
Find 1599984, 1516ms
Find 1599985, 1516ms
Find 1599986, 1516ms
Find 1599987, 1516ms
Find 1599988, 1516ms
Find 1599989, 1516ms
Find 1599990, 1516ms
Find 2600000, 2469ms
Find 2600001, 2469ms
Find 13199998, 12594ms
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, 453ms
Find 1599982, 453ms
Find 1599983, 453ms
Find 1599984, 453ms
Find 1599985, 453ms
Find 1599986, 453ms
Find 1599987, 453ms
Find 1599988, 453ms
Find 1599989, 453ms
Find 1599990, 453ms
Find 2600000, 765ms
Find 2600001, 765ms
Find 13199998, 4187ms

我们以最后一个找到的数字为例，前者的时间是后者的3倍，代码的其它部分完全一样，区别就是前者是转换为字符串查找1的个数，后者使用数学的取模运算计算。

作者: Cherami
原载: Google面试题解说性能之一：字符串运算VS数字运算
版权所有。转载时必须以链接形式注明作者和原始出处及本声明。

日志评价

相关日志

• 专题
• Google和百度
• Google面试题解说性能之七：缓存中间结果
• Google面试题解说性能之八：工欲善其事必先利其器

随机日志

• 申请到gmail domain
• 没有装订的书
• 将更多的工作转移到中国
• 阳澄湖大闸蟹

添加到网摘

[del.icio.us]  [新浪 VIVI]  [365key]  [YouNote]  [博采中心]  [Poco]  [SOHU狐摘]  [天极网摘]  [和讯网摘]
喜欢这个插件？