上次已經說了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倍。