Google面试题解说性能之四：优化无止境

其实在例子二的基础上，我们进一步的分析，可以把缓存10个结果换成缓存100个结果，性能可以得到进一步提升：
public class GoogleFn {
  private static int MAX = 13200000;

  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 < 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 (result == x && x != 0) {
          print(x, start);
        }
      }
    }
  }

  private static void method2() {
    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 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, 78ms
Find 1599982, 78ms
Find 1599983, 78ms
Find 1599984, 78ms
Find 1599985, 78ms
Find 1599986, 78ms
Find 1599987, 78ms
Find 1599988, 78ms
Find 1599989, 78ms
Find 1599990, 78ms
Find 2600000, 125ms
Find 2600001, 125ms
Find 13199998, 625ms
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, 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, 219ms

可以看出，缓存100个结果比缓存10个结果又快了近3倍，这个时候我们可能会想，那么我缓存1000个结果呢，很遗憾，按照这个方法缓存1000个的结果和缓存100个结果无异。当然，肯定还有其他的更优解。