Oracle技术：代码的执行效率与算法浅谈

会计考友 · 发表于 2012-8-4 14:06:19

前一段时间在博客园里看到这样一篇文章，那位兄弟谈到程序效率的关键是“简短”。他说，“程序越简短，其可执行代码就越少，就越有效率”，而在编写程序的时候，“要尽量改进我们的算法，而改进算法中最重要的一条，就是减少语句”。这句话从表面上似乎正确，但我认为性能这问题不能用“简短”这种方式去思考，否则会进入一些误区。我整理了一下思路，希望可以从几个方面把详细谈一下这个问题。
首先，如果说“简短的代码效率高”，那么什么叫作“简短”呢？姑且理解为“代码少”吧。如果“代码少”能够得出“效率高”，那我认为还需要其他一些条件，例如：
代码完全是顺序执行的
每行代码的效率相同
但是，这对于使用高级语言的程序员来说，这两条基本上都无法成立，因为：
代码中有条件跳转（如循环），因此一段简短的代码最终执行的“次数”可能比一段复杂的代码要多。这是很常见的情况，并非如那位兄弟所说“两三行代码写出死循环”这样的“特例”。
每行代码的效率几乎不可能相同。试想一个i++和一个方法调用，他们的性能开销怎么可能相同呢？再者，这个特性并非是“高级语言”特有的，连CPU指令也是一样（以后我们再来详谈这个问题）。
其实这就是目前编程工作中不可能回避的现状，那就是高级语言并不直接反映出机器的执行过程。同时，我们不能从代码表面的简短程度来判断程序效率的高低。正如那位朋友所谈，影响程序的关键因素之一是算法的选择，但我不同意他说算法优化的关键在于“减少语句”。从一定程度上讲，选择高效的算法的确是为了减少指令执行的“总量”，但它并不是如那篇文章所说通过“少一些变量”，“少一些判断”来进行的，而是在于大幅的逻辑改变来减少总体的操作。
事实上，我们很容易便能举出代码简短，但是性能较差的算法。就拿最常见的排序算法来说，冒泡排序不可谓不简单：
点此展开点此折叠
public void BubbleSort(int[] array)
{
for (int i = array.Length - 1; i >= 0; i--)
{
for (int j = 1; j array[j])
{
int temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
}
}
}

会计考友 · 发表于 2012-8-4 14:06:20

}而快速排序与之相比实在是复杂太多了：
点此展开点此折叠
public void QuickSort(int[] array)
{
QuickSortInternal(array, 0, array.Length);
}
private void QuickSortInternal(int[] array, int begin, int end)
{
if (end == begin)
{
return;
}
else
{
int pivot = FindPivotIndex(array, begin, end);
if (pivot > begin) QuickSortInternal(array, begin, pivot - 1);
if (pivot < end) QuickSortInternal(array, pivot + 1, end);
}
}
private int FindPivotIndex(int[] array, int begin, int end)
{
int pivot = begin;
int m = begin + 1;
int n = end;
while (m < end && array[pivot] >= array[m])
{
m++;
}
while (n > begin && array[pivot] = array[m])
{
m++;
}
while (n > begin && array[pivot]

		自动登录	找回密码
密码			立即注册

[考试辅导] Oracle技术：代码的执行效率与算法浅谈

Oracle技术：代码的执行效率与算法浅谈