Google面试题解说性能之五：人比电脑聪明

在例子四的基础上，我们可以进行更加深入的分析，我们还是以100为例，我们其实在大部分情况下可以省略循环，如果数字的百位数以上包含1的个数为0，而十位数不为1，那么当个位数大于1以后，我们可以中断底层的循环，这样我们又节省了很多的运算：
public class GoogleFn {
  private static int MAX = 1320000000;

  private static int MAX2 = MAX / 10;

  private static int MAX3 = MAX2 / 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 = 0; i < MAX3; i++) {
      int number = i * 100;
      int value = count(number);
      for (int j = 0; j < 10; j++) {
        for (int k = 0; k < 10; k++) {
          int x = number + j * 10 + k;
          result += value;
          if (j == 1) {
            result++;
          }
          if (k == 1) {
            result++;
          }
          if (result == x && x != 0) {
            print(x, start);
          }
        }
      }
    }
  }

  private static void method2() {
    long start = System.currentTimeMillis();
    int result = 20;
    for (int i = 1; i < MAX3; i++) {
      int number = i * 100;
      int value = count(i);
      for (int j = 0; j < 10; j++) {
        for (int k = 0; k < 10; k++) {
          if (value == 0 && j != 1 && k > 1) {
            break;
          }
          int x = number + j * 10 + k;
          result += value;
          if (j == 1) {
            result++;
          }
          if (k == 1) {
            result++;
          }
          if (result == x && x != 0) {
            print(x, start);
            continue;
          }
        }
      }
    }

  }

  private static void print(int n, long start) {
    System.out.println("Find " + n + ", "
        + (System.currentTimeMillis() - start) + "ms");
  }

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

运行结果：
Find 1, 0ms
Find 199981, 16ms
Find 199982, 16ms
Find 199983, 16ms
Find 199984, 16ms
Find 199985, 16ms
Find 199986, 16ms
Find 199987, 16ms
Find 199988, 16ms
Find 199989, 16ms
Find 199990, 16ms
Find 200000, 16ms
Find 200001, 16ms
Find 1599981, 32ms
Find 1599982, 32ms
Find 1599983, 32ms
Find 1599984, 32ms
Find 1599985, 32ms
Find 1599986, 32ms
Find 1599987, 32ms
Find 1599988, 32ms
Find 1599989, 32ms
Find 1599990, 32ms
Find 2600000, 47ms
Find 2600001, 47ms
Find 13199998, 204ms
Find 35000000, 532ms
Find 35000001, 579ms
Find 35199981, 594ms
Find 35199982, 594ms
Find 35199983, 594ms
Find 35199984, 594ms
Find 35199985, 594ms
Find 35199986, 594ms
Find 35199987, 594ms
Find 35199988, 594ms
Find 35199989, 594ms
Find 35199990, 594ms
Find 35200000, 594ms
Find 35200001, 594ms
Find 117463825, 1860ms
Find 500000000, 8079ms
Find 500000001, 8079ms
Find 500199981, 8141ms
Find 500199982, 8141ms
Find 500199983, 8141ms
Find 500199984, 8141ms
Find 500199985, 8141ms
Find 500199986, 8141ms
Find 500199987, 8141ms
Find 500199988, 8141ms
Find 500199989, 8141ms
Find 500199990, 8141ms
Find 500200000, 8141ms
Find 500200001, 8141ms
Find 501599981, 8157ms
Find 501599982, 8157ms
Find 501599983, 8157ms
Find 501599984, 8157ms
Find 501599985, 8157ms
Find 501599986, 8157ms
Find 501599987, 8157ms
Find 501599988, 8157ms
Find 501599989, 8157ms
Find 501599990, 8157ms
Find 502600000, 8188ms
Find 502600001, 8188ms
Find 513199998, 8485ms
Find 535000000, 8844ms
Find 535000001, 8844ms
Find 535199981, 8844ms
Find 535199982, 8844ms
Find 535199983, 8844ms
Find 535199984, 8844ms
Find 535199985, 8844ms
Find 535199986, 8844ms
Find 535199987, 8844ms
Find 535199988, 8844ms
Find 535199989, 8844ms
Find 535199990, 8844ms
Find 535200000, 8844ms
Find 535200001, 8844ms
Find 1111111110, 18172ms
Find 199981, 16ms
Find 199982, 16ms
Find 199983, 16ms
Find 199984, 16ms
Find 199985, 16ms
Find 199986, 16ms
Find 199987, 16ms
Find 199988, 16ms
Find 199989, 16ms
Find 199990, 16ms
Find 200000, 16ms
Find 200001, 16ms
Find 1599981, 31ms
Find 1599982, 31ms
Find 1599983, 31ms
Find 1599984, 31ms
Find 1599985, 31ms
Find 1599986, 31ms
Find 1599987, 31ms
Find 1599988, 31ms
Find 1599989, 31ms
Find 1599990, 31ms
Find 2600000, 47ms
Find 2600001, 47ms
Find 13199998, 188ms
Find 35000000, 453ms
Find 35000001, 453ms
Find 35199981, 453ms
Find 35199982, 453ms
Find 35199983, 453ms
Find 35199984, 453ms
Find 35199985, 453ms
Find 35199986, 453ms
Find 35199987, 453ms
Find 35199988, 453ms
Find 35199989, 453ms
Find 35199990, 453ms
Find 35200000, 453ms
Find 35200001, 453ms
Find 117463825, 1406ms
Find 500000000, 6438ms
Find 500000001, 6438ms
Find 500199981, 6438ms
Find 500199982, 6438ms
Find 500199983, 6438ms
Find 500199984, 6438ms
Find 500199985, 6438ms
Find 500199986, 6438ms
Find 500199987, 6438ms
Find 500199988, 6438ms
Find 500199989, 6438ms
Find 500199990, 6438ms
Find 500200000, 6438ms
Find 500200001, 6438ms
Find 501599981, 6453ms
Find 501599982, 6453ms
Find 501599983, 6453ms
Find 501599984, 6453ms
Find 501599985, 6453ms
Find 501599986, 6453ms
Find 501599987, 6453ms
Find 501599988, 6453ms
Find 501599989, 6453ms
Find 501599990, 6453ms
Find 502600000, 6485ms
Find 502600001, 6485ms
Find 513199998, 6688ms
Find 535000000, 7031ms
Find 535000001, 7031ms
Find 535199981, 7031ms
Find 535199982, 7031ms
Find 535199983, 7031ms
Find 535199984, 7031ms
Find 535199985, 7031ms
Find 535199986, 7031ms
Find 535199987, 7031ms
Find 535199988, 7031ms
Find 535199989, 7031ms
Find 535199990, 7031ms
Find 535200000, 7031ms
Find 535200001, 7031ms
Find 1111111110, 14250ms

注意我们把MAX放大了100倍，这样才能看出差别，否则运算时间太短，就看不出来差异了。虽然这样做只提高了大约20％的性能，但是如果这个提升是发生在占用系统最多时间的部分，其累加效应将是惊人的。

评论

3 楼 cherami 2007-07-14  

直接得到f(n)的值很简单啊，在这个系列的算法显神威就是可以直接得到，但是要得到所有匹配的，以及可以匹配的最大值，还是要一个一个算的，在这个时候，n以前的f(n)是有价值的。

2 楼 zqrain 2007-07-12  

这种方法需要吧n以前的数据都算一遍，才能得到f(n)的值，是不是太慢了！

cherami 是不是没有理解题意！

1 楼 cherami 2007-04-10  

实际上那个判断条件应该多加一个：
value == 0 && j != 1 && k > 1 && result < number
这样才是万无一失，因为前三个条件对result没有影响，也就是不影响f(n)的结果，但是k增加的时候n是在变的，如果f(n)不变,而f(n)小于n，那么f(n+1)=f(n)，所以f(n+1)必然小于n+1。