上次已经说了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;
}