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