黑马程序员技术交流社区
标题: 从一个例子来看程序优化 [打印本页]
作者: pp6576134 时间: 2018-4-10 09:50
标题: 从一个例子来看程序优化
写程序最主要的目标就是使它在任何情况下都运行正确，另一方面，在很多情况下，让程序运行的快也是一个重要的因素。本文通过一个简单的实例，简要介绍几种不同类型的程序优化方法，让程序运行的更快，这里主要介绍的优化方法有:1、利用程序的局部性原理，2、代码移动，3、利用指令的并行性。
先来简单的介绍一下指令执行的过程，这里只是简单的介绍，如果要想详细了解可参考相关书籍。一条指令的执行通常包括如下几个阶段：取指（根据程序计数器的值从内存取出指令）、译码、执行、访问内存（可以将数据读入内存，或从内存读出数据）、写回及更新程序计数器。
废话不多说，从一个简单的例子说起。计算一个数组全部元素之和。直接上程序。
public void sumLow() {
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr;
}
System.out.println("sum" + sum);
}
上面的程序有优点也有缺点，优点是很好的利用了局部性原理。局部性通常包括两个方面，时间局部性与空间局部性。在一个好的时间局部性的程序中，被引用过一次的内存位置很可能在不远的将来再次被引用。在一个具有良好空间局部性的程序里，如果一个内存的位置被引用一次，那么程序很可能在不远的将来引用附近的一个内存位置。一般而言具有良好局部性的程序比局部性差的运行的更快。在这个例子中，变量sum在每次循环迭代中被引用一次，因此，对sum来说，有好的时间局部性，同时因为sum是变量，对于sum来说，没有空间局部性。对于数组而言，因为每次索引加1，即步长为1，所以有好的空间局部性，如果步长为k，则随着k的增加，空间局部性下降。再让我们看一看下面这个程序。
public void sumbetter() {
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int sum = 0;
int len = arr.length;
for (int i = 0; i < len; i++) {
sum += arr;
}
System.out.println("sum" + sum);
}
这个程序相比第一个程序有什么改进呢？我们很容易就发现这两个程序的细节差别，第二个程序将数组长度的求解放在了循环之外，称为代码移动。代码1里面每次循环，都需要对数组的长度进行求解，效率较低。而实际上，数组的长度每次迭代时，值都不会发生改变，因而执行代码1时，处理器每次循环中都做了一些无用功。代码2将其移至循环外部，消除了这个低效率。
再来看看代码3的程序，我们很容易发现代码3引入了两个新变量sum1和sum2，并且索引每次加2。这种做法是如何提高程序执行的效率的呢？大家很容易发现，其中索引每次加2，明显的减少了循环次数，节约了时间。大家都知道，在单核处理器上，指令的执行都是流水线形式执行的，上面我们已经提到过一个程序执行的流程。何为流水化，就是一条指令在译码的时候，处理器同时在对下一条指令进行取指，其他步奏以此类推，而不需要等某一条指令各个阶段全部执行完，再执行下一条指令。下面的程序使用了两个求和变量，每个变量的求和在处理器里都是独立进行的提高了程序的运行效率。
public void sumBest() {
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int sum1 = 0;
int sum2 = 0;
int sum = 0;
int len = arr.length;
for (int i = 0; i < len; i += 2) {
sum1 += arr;
sum2 += arr[i + 1];
}
sum = sum1 + sum2;
System.out.println("sum" + sum);
}
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |