Java性能优化之实战算法[2]

——当你拿着一把锤子的时候，所有的东西看起来都像钉子。

——当你看到钉子的时候，手上拿着的东西看起来就像一把锤子。

性能优化有时候很像玩一个策略游戏(免费)，对手不是计算机，程序员，设计架构，编译器，控制流，而是时间，内存，竞争条件，预算限制等等。有三个资源限制几乎所有应用都会面临：1.CPU速度和有效性2.系统内存3.磁盘I/O。

性能分析的关键是找到瓶颈所在，符合二八原理的是，计算机通常会将80%的时间花在20%的程序上，所以找出这20%的瓶颈很重要，这就是我上篇中所说的，为什么在优化之前一定要分析，不要相当然。我从二八原理学到的就是要统筹分析，使做事效率最优化，这个优化跟我们标题中提到Java性能优化道理上都是一样的。即应该把80%的时间花在造成问题的80%原因上面。呵呵，绕口吧。

比如，我在分析的时候，就发现了这么一个瓶颈，一个微不足道的步骤却消耗了大部分CPU资源，某些情况下CPU花了它96%的时间来处理它。

简化模型，描述起来，就是：

一维数组，每个元素都有保持它是第几个的一个index， 从头到尾插入元素，已有的元素的index需要做出调整，以保持一致性（即：array[i].index = i）。按照我们现在的算法，是每插入一条，其后面的每个元素记录的索引都要做出相应调整。简单估计一下，假设输入规模是N，大概需要O(N^2)的时间，当只有两三万的时候还好，大到8万就显得慢了(是两万时的16倍)。

这个问题本质上是个算法问题，就是怎么样把O(N^2)降到O(N)或者更低的问题，这样便可以大大的提高CPU效率和速度。

开始之前，我想了两种方法：

方法一：绕过这个问题，想办法直接计算出某元素在插入后的值，或者等到多次插入后，一起调整。

方法二：直接解决这个问题，不用字段index保存这个问题，想办法借助类似C++的指针地址，和数组地址来计算index。

对于方法二，需要借助语言特性，因为Java是没有办法取到对象值实例的地址，估计C++也悬，这条途径的复杂度和陷阱太多了，所以很快被抛弃了。

思考方法一：其实对于插入记录整个这个过程，许多记录被调整了多次，其实中间的这些调整是不用关心的，我们只需要知道最后状态是在某个位置就行了。因此，我们想要直接计算插入后的位置，让每条记录只进行一次索引调整。

最后的解决办法就是，首先将插入的记录排序，即从前往后插入，然后要做到取消中间的这些调整，使每条记录只调整一次，对于每个记录来说，只要用一个临时变量来记录它的前面已经插入的多少条记录，从前往后调整，轮到某条记录时，便可以计算出位置索引index的值，保证初始状态和插入结束后状态的一致性。

这个问题看起来是不是似乎很简单？但是，实际情况中的问题要复杂的多，比如，有可能这个插入是在某个大的循环中进行的，也可能在插入的同时，程序需要对这个数组中的记录做操作，可能还是个二维数组等等。关键的是，你需要做出某些努力，重构简化模型，然后抽象出模型，找出问题的本质。

原来的做法，每插入一次就调整一次为的是保证插入过程中每个记录状态都要保持一致性，这个要求太高了，所以导致了O(N^2)的高代价。真正的要求没有那么高，我们只需要开始和结束两个状态的一致性就行了，而这只需要N(O)就可以做到，这个代价就低了。这样这个瓶颈就通过算法来解决了，可以看出算法在性能优化中还是很重要的。

评论

1 楼 yangtsefisher 2009-05-20  

MakeLove 写道

居然没看懂

名字不错哈。。。
难道是我表达有问题？