解惑

解己之惑，解人之惑

2007年4月 (第3页共4页)

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

2007年4月9日 / / 8 评论

按照原先的计划，这个系列只应该有四篇，但是后来打算多写一些，把这个问题研究透彻，所以出现了总结篇先于其它篇的情况。
这次我们按照总结篇中提到的方法实际演示下代码覆盖工具如何帮助我们优化程序提高性能，先给出我们未经好好优化的程序：
package com.jiehoo.util;

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];

static {
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);
}
}

阅读全文

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

2007年4月9日 / / 3 评论

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

阅读全文

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

2007年4月9日 / / 3 评论

其实很多问题一旦涉及到数学问题或者数据处理密集型问题，那么最终显现神威的就是数学公式，这个面试题也是这类问题，所以如果我们能够推导出一个数学公式就是最理想的，在前面的例子中，我们进行了一些深入的分析，根据前面的例子，你可能会尝试把步长从100扩展到1000或者10000，但是实际上这个方法遇到了瓶颈，因为循环嵌套的层次太多，计算公式太复杂也会导致问题。如果我们最开始尝试的时候把全部的f(n)的结果打印出来，你会发现这样的内容：

  1. f(9) = 1
  2. f(99) = 20
  3. f(999) = 300
  4. f(9999) = 4000
  5. ……

这个是我们的第一个规律：位数乘以（（位数－1）的10的次方）。
根据这个f(n)的说明，我们定义另外一个方法x(n)，它的定义就是n这个数包含的1的个数，例如x(1)=1，x(2)=0，x(11)=2，那么我们可以把f(n)展开为：
f(n)=x(0)+x(1)+……+x(n)
同时我们可以把x(n)也展开，假设n=XYZ，那么x(n)的展开式为：
x(n)= x(X)+x(Y)+x(Z)
也等于：
x(n)= x(X)+x(YZ)
再结合上面的规律我们就可以推导出一个规律了，先用例子来说明，以106为例：
f(106) = x(0)+…+x(99)+x(100)+…+x(106) = f(99) + x(100)+…+x(106)
f(99)我们使用上面的第一个规律很容易计算得到，那么后面的这7个数包含多少个1呢，其实也很简单，应用可能小学就学过的公因子概念，当然这里不是真正的公因子，而是这些数里面包含的1的个数相同的部分，结合x(n)的展开式，我们进一步推演出：
f(106) = f(99) + x(1)+ x(00)+x(1)+x(01)+…+x(1)+x(06) = f(99) + x(1) * (6+1) + x(00) + .. x(06) = f(99) + x(1) * (6+1) + f(6)
这样计算就很简单了，不是吗？
好，再看看f(345)的情况，有点不太一样：
f(345) = x(0)+…x(99)+x(100)+…+x(199)+x(200)+..+x(299)+x(300)+…+x(345)= f(99) + x(1) * (99+1) + f(99)+ x(2)*(99+1)+f(99)+x(3)*(45+1)+f(45)
这个例子足够典型了吗？看到规律了吗？
给定一个数n，假设最高位为x，除去最高位的数字为y，位数为z，那么
如果x=1，那么f(n)等于f(pow(10,z-1)-1)+(y+1)+f(y)
如果x>1，那么f(n)等于f(pow(10,z-1)-1)*x+pow(10,z-1)+f(y)

转换为代码就是：

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 = (length – 1) * (int) Math.pow(10, length – 1 – 1) + fn(end)
+ (end + 1);
} else {
result = (length – 1) * (int) Math.pow(10, length – 1 – 1) * x
+ (int) Math.pow(10, length – 1) + fn(end);
}
return result;
}

你可以运行试试这个公式是否准确。
最后需要强调一下的是，这个方法可以快速的计算给定的一个数的f(n)的结果，但是如果用一个简单的循环来查找符合f(n)=n的结果是不合适的，这个我会另外再谈的。

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

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

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

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

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

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

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

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

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

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

2007年4月7日 / / 8 评论

在例子四的基础上，我们可以进行更加深入的分析，我们还是以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;
}

阅读全文

Google面试题解说性能之总结

2007年4月6日 / / 3 评论

呵呵，说了这么多，到底怎么优化性能还是没有说多少，而且一个产品的代码比这个例子复杂得多，怎么才能优化产品代码呢？
很简单，找到性能瓶颈，而大部分的性能瓶颈都有一个特点：被执行的次数太多。一个耗时2分钟的操作，如果系统运行一天才需要运行一次，那么我们根本就不要去理会它，如果一个操作耗时2秒，但是一般运行一天它要被执行几千亿次，那么你就要小心了。
如何才能知道系统中的哪些代码被执行的次数最多呢？有很多工具可以，有的是挂到系统上一起运行，有的是可以单独运行，但是我推荐的方法就是使用单元测试工具和代码覆盖工具，运行所有的单元测试，查看代码覆盖报告中被执行的次数最多的那些语句，看看他们是否可以被优化，或者可以被减少执行的次数。
可以参考我以前的一些日志：
Ant+JUnit+Cobertura
成功提高20倍性能

很多情况下，找到性能的瓶颈并不是很困难，真正困难的是如何进行优化。这个没有通用的解决方法，只能结合具体的问题具体解决，一个大部分情况下有效的方法是使用某种缓存机制（实际上，我的第二个例子也是使用了缓存机制，把运算结果缓存了9次）。

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

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

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

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

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

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

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

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

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

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

2007年4月6日 / / 2 评论

其实在例子二的基础上，我们进一步的分析，可以把缓存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;
}

阅读全文

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

2007年4月6日 / / 0条评论

对于任何语言来讲，循环永远是非分布式系统的性能的最大杀手，循环中的任何一个简单的语句对性能都是有影响的，只是影响的大小不同而已。第一个例子中的影响是比较大的，不同的实现方法的时间开销不同，然后这个微小的差异被循环次数放大后就非常的明显（3倍），而第二个例子，其本质是减少了循环执行的次数，虽然总的循环次数是一样的，但是最耗时的操作的执行次数被减少到1/10，所以产生的差异是非常巨大的（8倍）。我们再来看一个很不起眼的微小差异带来的影响：
public class GoogleFn {
private static int MAX = 132000000;

private static int MAX2 = MAX / 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;
}

阅读全文

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

2007年4月6日 / / 5 评论

前面我们已经说了字符串运算和数学运算对性能的巨大影响，接下来我们看看分析程序，多思考给我们带来的好处。
如果我们做一个简单的分析就可以知道，在尾数从0到9的连续十个数字中，只有尾数为1的数字的1的个数比其它的数字多，那么我们可以以10个数为单位进行分隔，计算尾数为0的数字包含1的个数，其它的9个值就以此为基础计算：
public class GoogleFn {
private static int MAX = 13200000;

private static int MAX2 = MAX / 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;
}

阅读全文

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

2007年4月6日 / / 5 评论

看到JavaEye上的几个人在讨论算法问题，其中一个就是Google的一个面试题，我也试了一下，而且可能比一般人试得程度更深一些，借这个题目简单的说说几个性能问题。这个是第一个，后面还会继续几个其它的讨论。讨论只是提点一下，主要还是要你自己读源代码并比较不同的实现为什么会有这么大的差别。
注意，程序的运行结果是在JDK1.4.2上的，其它版本的JDK的运行结果可能稍有不同。

先看代码：
public class GoogleFn {
private static int MAX = 13200000;

private static int count1(int number) {
int result = 0;
String target = number + “”;
int index = target.indexOf(“1”);
while (index >= 0) {
result++;
index = target.indexOf(“1”, index + 1);
}
return result;
}

阅读全文

房产证到手

2007年4月5日 / / 0条评论

昨天经历的惟一的一件值得高兴的事情就是把房产证拿到手了，把中介的钱付了，物业也过户了，还付了一年的物业费，一个平方4毛5每月。
这次买房和装修的过程中，买房我们非常的小心，因为我们之前听了很多关于二手房买卖的陷阱，我老婆还在一个房地产网站公司里面做过一段时间，所以一路下来我们非常小心，几乎就是谁的话都不信（中介和上家），一定要按照正规的流程走，有一次还特意晚上跑到上家的家里问她的女儿是否同意卖房，因为之前我们从来没有见过她的女儿，只是上家说女儿在读书，很忙。
因为这次买房还算比较顺利，到装修前其实都没有遇到真正的问题，中介和上家说的其实都是实话，所以这次装修老婆说倾向于让那个老板装，我开始很担心，后来跑去老板家看了下，感觉人还是比较可靠的（包括老板的老婆），再想想自己办事一直都太小心谨慎了，这次买房都没有什么，装修应该也不会有什么吧？况且是后付款，也不怕有什么事情，所以后来也就同意了。加之买房的时候查了很多注意事项，实在是比较累，所以就想这次装修就不那么费心休息下好了，结果闹到这个地步

所以人不能想着偷懒，在上海做事情还是按照正规的流程走，合同什么的一定要仔细签。

更早的文章 更新的文章

© 2025 解惑

本主题由Anders Noren提供 — 向上 ↑