解惑

解己之惑,解人之惑

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

在例子四的基础上,我们可以进行更加深入的分析,我们还是以100为例,我们其实在大部分情况下可以省略循环,如果数字的百位数以上包含1的个数为0,而十位数不为1,那么当个位数大于1以后,我们可以中断底层的循环,这样我们又节省了很多的运算:
public class GoogleFn {
private static int MAX = 1320000000;

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 < 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 method2() {
long start = System.currentTimeMillis();
int result = 20;
for (int i = 1; i < MAX3; i++) {
int number = i * 100;
int value = count(i);
for (int j = 0; j < 10; j++) {
for (int k = 0; k < 10; k++) {
if (value == 0 && j != 1 && k > 1 && result < number) {
break;
}
int x = number + j * 10 + k;
result += value;
if (j == 1) {
result++;
}
if (k == 1) {
result++;
}
if (result == x && x != 0) {
print(x, start);
continue;
}
}
}
}

}

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, 32ms
Find 1599982, 32ms
Find 1599983, 32ms
Find 1599984, 32ms
Find 1599985, 32ms
Find 1599986, 32ms
Find 1599987, 32ms
Find 1599988, 32ms
Find 1599989, 32ms
Find 1599990, 32ms
Find 2600000, 47ms
Find 2600001, 47ms
Find 13199998, 204ms
Find 35000000, 532ms
Find 35000001, 579ms
Find 35199981, 594ms
Find 35199982, 594ms
Find 35199983, 594ms
Find 35199984, 594ms
Find 35199985, 594ms
Find 35199986, 594ms
Find 35199987, 594ms
Find 35199988, 594ms
Find 35199989, 594ms
Find 35199990, 594ms
Find 35200000, 594ms
Find 35200001, 594ms
Find 117463825, 1860ms
Find 500000000, 8079ms
Find 500000001, 8079ms
Find 500199981, 8141ms
Find 500199982, 8141ms
Find 500199983, 8141ms
Find 500199984, 8141ms
Find 500199985, 8141ms
Find 500199986, 8141ms
Find 500199987, 8141ms
Find 500199988, 8141ms
Find 500199989, 8141ms
Find 500199990, 8141ms
Find 500200000, 8141ms
Find 500200001, 8141ms
Find 501599981, 8157ms
Find 501599982, 8157ms
Find 501599983, 8157ms
Find 501599984, 8157ms
Find 501599985, 8157ms
Find 501599986, 8157ms
Find 501599987, 8157ms
Find 501599988, 8157ms
Find 501599989, 8157ms
Find 501599990, 8157ms
Find 502600000, 8188ms
Find 502600001, 8188ms
Find 513199998, 8485ms
Find 535000000, 8844ms
Find 535000001, 8844ms
Find 535199981, 8844ms
Find 535199982, 8844ms
Find 535199983, 8844ms
Find 535199984, 8844ms
Find 535199985, 8844ms
Find 535199986, 8844ms
Find 535199987, 8844ms
Find 535199988, 8844ms
Find 535199989, 8844ms
Find 535199990, 8844ms
Find 535200000, 8844ms
Find 535200001, 8844ms
Find 1111111110, 18172ms
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, 188ms
Find 35000000, 453ms
Find 35000001, 453ms
Find 35199981, 453ms
Find 35199982, 453ms
Find 35199983, 453ms
Find 35199984, 453ms
Find 35199985, 453ms
Find 35199986, 453ms
Find 35199987, 453ms
Find 35199988, 453ms
Find 35199989, 453ms
Find 35199990, 453ms
Find 35200000, 453ms
Find 35200001, 453ms
Find 117463825, 1406ms
Find 500000000, 6438ms
Find 500000001, 6438ms
Find 500199981, 6438ms
Find 500199982, 6438ms
Find 500199983, 6438ms
Find 500199984, 6438ms
Find 500199985, 6438ms
Find 500199986, 6438ms
Find 500199987, 6438ms
Find 500199988, 6438ms
Find 500199989, 6438ms
Find 500199990, 6438ms
Find 500200000, 6438ms
Find 500200001, 6438ms
Find 501599981, 6453ms
Find 501599982, 6453ms
Find 501599983, 6453ms
Find 501599984, 6453ms
Find 501599985, 6453ms
Find 501599986, 6453ms
Find 501599987, 6453ms
Find 501599988, 6453ms
Find 501599989, 6453ms
Find 501599990, 6453ms
Find 502600000, 6485ms
Find 502600001, 6485ms
Find 513199998, 6688ms
Find 535000000, 7031ms
Find 535000001, 7031ms
Find 535199981, 7031ms
Find 535199982, 7031ms
Find 535199983, 7031ms
Find 535199984, 7031ms
Find 535199985, 7031ms
Find 535199986, 7031ms
Find 535199987, 7031ms
Find 535199988, 7031ms
Find 535199989, 7031ms
Find 535199990, 7031ms
Find 535200000, 7031ms
Find 535200001, 7031ms
Find 1111111110, 14250ms

注意我们把MAX放大了100倍,这样才能看出差别,否则运算时间太短,就看不出来差异了。虽然这样做只提高了大约20%的性能,但是如果这个提升是发生在占用系统最多时间的部分,其累加效应将是惊人的。

  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)

8 Comments

  1. 如果数字的百位数以上包含1的个数为0,而十位数不为1,那么当个位数大于1以后,我们可以中断底层的循环

    这是为什么
    似乎这样子包括了结尾为00或01的情况
    是推理得出的 还是统计分析出的

    对了,Google面试题解说性能之三打不开

  2. 呵呵,中断循环是因为他对结果没有影响,也就是说,接下来的八个数字肯定不包含1了,所以就不用再计算了,你把f(1)到f(1000)的结果全部打印出来看看规律就知道了。

    三打不开你刷新一下应该就可以了。这个虚拟主机有时候是有这个问题的。

  3. 3的问题已经修正,不是服务器的问题,可能是URL太长了

  4. 呵呵,这就是我不同意的地方
    这个规律是对40亿以内的数成立呀
    那是因为我们已经知道结果了

  5. 呵呵,这个规律和数字的大小无关,但是实际上那个判断条件应该多加一个:
    value == 0 && j != 1 && k > 1 && result < number 这样才是万无一失,因为前三个条件对result没有影响,也就是不影响f(n)的结果,但是k增加的时候n是在变的,如果f(n)不变,而f(n)小于n,那么f(n+1)=f(n),所以f(n+1)必然小于n+1。 这个就是这篇日志的主题:分析问题找出本质规律,而这些规律电脑不会帮你分析的。

  6. 另外需要说明的是,这个额外的判断对于性能优化的效用是递减的,100以内,符合的只有80%,1000以内只有70%了,而10000以内只有60%了,以此类推。

  7. 呵呵
    是这个理,必须在result


  8. 居然没写完
    我想说的是必须判断result

发表评论

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

© 2019 解惑

本主题由Anders Noren提供向上 ↑