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的个数，后者使用数学的取模运算计算。

评论

6 楼 morfil 2008-06-01  

的确String.valueOf()的效率最高

5 楼 tovegar 2007-09-25  

个人认为遇到这种问题一定要先建立数据模型!可以分析得到
if num =0  return 0
if 0<num<10 return 1
if num startWith 1 return f(10^(len(num)-1)-1)+num(去掉最高位数字)+1+f(num(去掉最高位数字))
else
10^(len(num)-1) + num(去掉最高位数字)* cal(10^(len(num)-1)-1) + f(num(去掉最高位数字));

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		long start = System.currentTimeMillis(); 
		Integer num = 535200001;
		int a = cal(num);
		System.out.println("TIME = " + (System.currentTimeMillis()-start));; 
	}
	
	public static int cal(Integer num) {
		int a = 0;
		System.out.println(num);
		if (num == 0)
			a = 0;
		else if (num >=1 &&num <= 9)
			a = 1;
		else if ((num.toString()).startsWith("1")) {
			int b1 = index(10,String.valueOf(num).length() - 1) - 1;
			int b2 = Integer.parseInt(num.toString().substring(1));
			a = cal(b1) + b2 + 1 + cal(b2);
		} else {
			int b1 = index(10,String.valueOf(num).length() - 1) - 1;
			int b2 = Integer.parseInt(num.toString().substring(1));
			int b3 = Integer.parseInt(num.toString().substring(0,1));
			a = index(10,String.valueOf(num).length()-1) + b3 * cal(b1) + cal(b2);
		}
			
		return a;
	}
	
	public static int index(int number, int size) {
		int num = 1;
		for (int i=0;i<size;i++) {
			num = num * number;
		}
		return num;
	}

4 楼 orange0513 2007-08-10  

我用netbeans6.0运行上面的算法  使用number+""
Find 1, 0ms
Find 199981, 78ms
Find 199982, 78ms
Find 199983, 78ms
Find 199984, 78ms
Find 199985, 78ms
Find 199986, 78ms
Find 199987, 78ms
Find 199988, 78ms
Find 199989, 78ms
Find 199990, 78ms
Find 200000, 78ms
Find 200001, 78ms
Find 1599981, 438ms
Find 1599982, 438ms
Find 1599983, 438ms
Find 1599984, 438ms
Find 1599985, 438ms
Find 1599986, 438ms
Find 1599987, 438ms
Find 1599988, 438ms
Find 1599989, 438ms
Find 1599990, 438ms
Find 2600000, 719ms
Find 2600001, 719ms
Find 13199998, 3813ms
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, 406ms
Find 1599982, 406ms
Find 1599983, 406ms
Find 1599984, 406ms
Find 1599985, 406ms
Find 1599986, 406ms
Find 1599987, 406ms
Find 1599988, 406ms
Find 1599989, 406ms
Find 1599990, 406ms
Find 2600000, 703ms
Find 2600001, 703ms
Find 13199998, 3890ms
使用String.valueOf（number）；
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, 281ms
Find 1599982, 281ms
Find 1599983, 281ms
Find 1599984, 281ms
Find 1599985, 281ms
Find 1599986, 281ms
Find 1599987, 281ms
Find 1599988, 281ms
Find 1599989, 281ms
Find 1599990, 281ms
Find 2600000, 453ms
Find 2600001, 453ms
Find 13199998, 2453ms
Find 1, 0ms
Find 199981, 62ms
Find 199982, 62ms
Find 199983, 62ms
Find 199984, 62ms
Find 199985, 62ms
Find 199986, 62ms
Find 199987, 62ms
Find 199988, 62ms
Find 199989, 62ms
Find 199990, 62ms
Find 200000, 62ms
Find 200001, 62ms
Find 1599981, 422ms
Find 1599982, 422ms
Find 1599983, 422ms
Find 1599984, 422ms
Find 1599985, 422ms
Find 1599986, 422ms
Find 1599987, 422ms
Find 1599988, 422ms
Find 1599989, 422ms
Find 1599990, 422ms
Find 2600000, 703ms
Find 2600001, 703ms
Find 13199998, 3891ms
字符串分析更快

3 楼 cherami 2007-07-03  

那好像还是没有数字运算快，不过还是有所提高c

2 楼 ueseu 2007-07-03  

按楼上的改了后

Find 1, 0ms
Find 199981, 63ms
Find 199982, 63ms
Find 199983, 63ms
Find 199984, 63ms
Find 199985, 63ms
Find 199986, 63ms
Find 199987, 63ms
Find 199988, 63ms
Find 199989, 63ms
Find 199990, 63ms
Find 200000, 63ms
Find 200001, 63ms
Find 1599981, 516ms
Find 1599982, 516ms
Find 1599983, 516ms
Find 1599984, 516ms
Find 1599985, 516ms
Find 1599986, 516ms
Find 1599987, 516ms
Find 1599988, 516ms
Find 1599989, 516ms
Find 1599990, 516ms
Find 2600000, 844ms
Find 2600001, 844ms
Find 13199998, 4391ms
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, 297ms
Find 1599982, 297ms
Find 1599983, 297ms
Find 1599984, 297ms
Find 1599985, 297ms
Find 1599986, 297ms
Find 1599987, 297ms
Find 1599988, 297ms
Find 1599989, 297ms
Find 1599990, 297ms
Find 2600000, 484ms
Find 2600001, 484ms
Find 13199998, 2781ms

1 楼 lazy 2007-06-20  

count1里面，把
String target = number + "";
换成
String target = String.valueOf(number);

效率马上得到极大的提升。