Google面试题解说性能之七：缓存中间结果

上次已经说了fn的实现不能用来查找符合条件的n，因为这样做比前面的第一个例子中的性能比较差的那个还要差，原因就是有太多的重复计算，如果只是计算一个指定的数的结果，那么那个实现是无与匹敌的。但是我们是讲的性能优化，所以，我们就用它来做，放慢速度，然后使用其它的技巧来提高性能，这次的方法就是简单的使用缓存：
public class GoogleFn {
private static final int MAX = 2600002;

private static long start = System.currentTimeMillis();

private static int[] bases = new int[15];

private static int[] values = new int[15];

private static int fn(int number) {
if (number < 10) {
return number > 0 ? 1 : 0;
}
String s = number + “”;
int length = s.length();
int end = Integer.parseInt(s.substring(1, length));
int x = s.charAt(0) – ‘0’;
int result = 0;
if (x == 1) {
result = values[length – 1] + fn(end) + (end + 1);
} else {
result = values[length – 1] * x + bases[length – 1] + fn(end);
}
return result;
}

    private static int fnOld(int number) {
if (number < 10) {
return number > 0 ? 1 : 0;
}
String s = number + “”;
int length = s.length();
int end = Integer.parseInt(s.substring(1, length));
int x = s.charAt(0) – ‘0’;
int result = 0;
if (x == 1) {
result = (length – 1) * (int) Math.pow(10, length – 1 – 1) + fnOld(end) + (end + 1);
} else {
result = (length – 1) * (int) Math.pow(10, length – 1 – 1) * x + (int) Math.pow(10, length – 1) + fnOld(end);
}
return result;
}

private static void print(int n) {
System.out.println(“Find ” + n + “, ” + (System.currentTimeMillis() – start) + “ms”);
}

public static void main(String[] args) {
for (int i = 1; i < MAX; i++) {
if (i == fnOld(i)) {
print(i);
}
}
bases[0] = 0;
bases[1] = 10;
values[0] = 0;
values[1] = 1;
for (int i = 2; i < values.length; i++) {
bases[i] = (int) Math.pow(10, i);
values[i] = i * (int) Math.pow(10, i – 1);
}
start = System.currentTimeMillis();
for (int i = 1; i < MAX; i++) {
if (i == fn(i)) {
print(i);
}
}
}
}
运行结果：
Find 1, 0ms
Find 199981, 1672ms
Find 199982, 1672ms
Find 199983, 1672ms
Find 199984, 1672ms
Find 199985, 1672ms
Find 199986, 1672ms
Find 199987, 1672ms
Find 199988, 1672ms
Find 199989, 1672ms
Find 199990, 1672ms
Find 200000, 1672ms
Find 200001, 1672ms
Find 1599981, 17032ms
Find 1599982, 17032ms
Find 1599983, 17032ms
Find 1599984, 17032ms
Find 1599985, 17032ms
Find 1599986, 17032ms
Find 1599987, 17032ms
Find 1599988, 17032ms
Find 1599989, 17032ms
Find 1599990, 17032ms
Find 2600000, 29875ms
Find 2600001, 29875ms
Find 1, 0ms
Find 199981, 1000ms
Find 199982, 1000ms
Find 199983, 1000ms
Find 199984, 1000ms
Find 199985, 1000ms
Find 199986, 1000ms
Find 199987, 1000ms
Find 199988, 1000ms
Find 199989, 1000ms
Find 199990, 1000ms
Find 200000, 1000ms
Find 200001, 1000ms
Find 1599981, 8563ms
Find 1599982, 8563ms
Find 1599983, 8563ms
Find 1599984, 8563ms
Find 1599985, 8563ms
Find 1599986, 8563ms
Find 1599987, 8563ms
Find 1599988, 8563ms
Find 1599989, 8563ms
Find 1599990, 8563ms
Find 2600000, 14594ms
Find 2600001, 14594ms

可以看到，我们仅仅是缓存了几个简单的中间结果，就将性能提升了一倍。另外请和第一个例子的结果对比一下，我们优化后的结果也比那个差的实现的结果大5倍。

1. Google面试题解说性能之一：字符串运算VS数字运算

2. Google面试题解说性能之二：分析问题

3. Google面试题解说性能之三：不要小看循环中的任何一个语句

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

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

6. Google面试题解说性能之六：数学显神威

7. Google面试题解说性能之七：缓存中间结果

8. Google面试题解说性能之八：工欲善其事必先利其器

9. Google面试题解说性能之总结