解惑

解己之惑,解人之惑

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个结果无异。当然,肯定还有其他的更优解。

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

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

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

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

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

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

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

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

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

(Visited 41 times, 1 visits today)

2 Comments

  1. private static void print(int n, long start) {
    System.out.println(“Find ” + n + “, ”
    + (System.currentTimeMillis() – start) + “ms”);
    }
    是不是增加了输出的开销
    我发现method1比第二个例子中的要慢

  2. 应该不会,如果你使用代码覆盖工具查看打话,这个方法被调用的次数非常的少,不会影响性能

发表评论

电子邮件地址不会被公开。 必填项已用*标注

© 2019 解惑

本主题由Anders Noren提供向上 ↑