历史上的一个非常牛的提高程序运行效率的案例出现在1985年。计算机科学家Andrew Appel编写了一个用于计算重力场中天体相互作用的经典物理问题的程序。在优化之前,该程序要完成在10000个天体相互作用时其中两个天体的物理作用问题的计算需要一年的时间,而在优化之后,这个时间缩短到了一天!
那么,Appel是如何做到的呢?他对程序的数据结构和算法进行了优化设计,对代码也重新进行了优化,当然还有就是对程序运行的硬件环境进行了升级。
我们今天主要谈谈如何通过优化代码来提高程序的运行效率。下面是一些具体的优化建议:
1. 简化循环条件
程序中的循环体在满足一定的条件后就会进行大量重复的工作,简化这些重复工作就可以提高效率。比如:
#include <stdio.h>
int getLength(char * str)
{
int sum = 0;
while(*(str+sum) != '\0')
sum++;
return sum;
}
int findChar(char pattern, char * sentence)
{
int i;
for(i = 0; i < getLength(sentence); i++){
if(pattern == *(sentence+i))
return i;
}
return -1;
}
void main()
{
char * text = "To be, or not be? That's the question!";
int result = findChar('x', text);
printf("%d\n", result);
}
这段代码的循环部分调用了函数getLength作为for循环的条件,这就意味着每次循环都要对这个字符串长度进行计算,这是毫无必要的。实际上我们只需计算一次字符串的长度,然后将其赋给一个变量,而每次循环只需要直接使用这个变量值就可以了。
2. 减少字符串的操作
在进行字符串操作时,我们需要给字符串分配内存。计算机是通过内存访问来获取字符串的。而计算机在进行内存访问时,访问一个字符不如访问一个字快,甚至有可能更慢。而字符串操作通常每次都是操作一个字符,即使像strlen()这样简单的函数(它用来计算一个字符串的长度)。如果有很多这样的操作,程序的运行效率会大大降低。
3. 注意函数调用的副作用
由于函数调用的机制非常复杂,因此函数调用也可能带来相当大的开销。比如:
#include <stdio.h>
int getLength(const char * str)
{
int sum = 0;
while(*(str+sum) != '\0')
sum++;
return sum;
}
char getElement(char * sentence, int index)
{
if(index < 0 || index >= getLength(sentence))
return NULL;
return sentence[index];
}
void main()
{
char * text = "To be, or not be? That's the question!";
char dest[50];
int i = 0;
int len = getLength(text);
for(i = 0; i < len; i++){
dest[i] = getElement(text, i);
}
dest[i] = '\0';
printf("%s\n", dest);
}
这段代码的主函数中的循环体每次循环迭代都会调用getElement来获取下一个字符串元素。这个函数调用的开销特别大,因为getElement函数运行时需要进行边界检查,而边界检查过程中需要调用函数getLength。在这个例子中,由于主函数中的循环体在循环条件检测环节已经能够确保不会出现越界访问了,所以在循环体内就没有必要反复地调用函数getElement。我们可能通过直接的字符数组访问方式对这段代码进行优化,像下面这样:
#include <stdio.h>
int getLength(const char * str)
{
int sum = 0;
while(*(str+sum) != '\0')
sum++;
return sum;
}
void main()
{
char * text = "To be, or not be? That's the question!";
char dest[50];
int i = 0;
int len = getLength(text);
for(i = 0; i < len; i++){
dest[i] = text[i];
}
dest[i] = '\0';
printf("%s\n", dest);
}
4. 多使用指针形式代码
C/C++语言的指针提供了一种更高效的数据访问方式。我们可以使用指针来替换掉非指针形式操作而使得程序性能大幅度提升。比如使用指针运算来替换掉数组引用。这在大多数的情况下都会提高程序的性能。但是,如果这个性能提升不是很大,出于可读性的考虑,使用数组代码更为明智。另外一种用指针替换的情况出现在函数调用里。比如在图像处理程序中,要载入一幅高分辨率的图像,在对该图像进行处理时,例如取反色、锐化、模糊或者再做一个边缘提取等。而这些功能通常都被封装在一些独立的函数中。当调用某个函数对图像进行处理时,有可能会将整张图像作为参数传递给函数。如果图像非常大,这种按值传递的方式会使得程序运行变慢。而如果使用指针,就只需要传递一个地址,程序运行效率自然大大加快。
(未完待续)
这正是:
效率提高有方法,需要优化好代码
八条建议逐个数,循环开销第一家
参考书目:代码揭秘——从C/C++的角度探秘计算机系统,作者:左飞,出版社:电子工业出版社
联系客服