当前页面: 开发资料首页 → Java 专题 → C程序优化之路(二)
C程序优化之路(二)
摘要: C程序优化之路(二)
本文讲述在编写C程序代码的常用优化办法，分为I/O篇，内存篇，算法篇，MMX汇编篇。
二．内存篇
在上一篇中我们讲述了如何优化文件的读写，这一篇则主要讲述对内存操作的优化，主要有数组的寻址，指针链表等，还有一些实用技巧。
I．优化数组的寻址
在编写程序时，我们常常使用一个一维数组a[M×N]来模拟二维数组a[N][M]，这个时候访问a[]一维数组的时候：我们经常是这样写a[j×M＋i]（对于a[j][i]）。这样写当然是无可置疑的，但是显然每个寻址语句j×M＋i都要进行一次乘法运算。现在再让我们看看二维数值的寻址，说到这里我们不得不深入到C编译器在申请二维数组和一维数组的内部细节上――实际在申请二位数组和一维数组，编译器的处理是不一样的，申请一个a[N][M]的数组要比申请一个a[M×N]的数组占用的空间大！二维数组的结构是分为两部分的：
① 是一个指针数组，存储的是每一行的起始地址，这也就是为什么在a[N][M]中，a[j]是一个指针而不是a[j][0]数据的原因。
② 是真正的M×N的连续数据块，这解释了为什么一个二维数组可以象一维数组那样寻址的原因。（即a[j][i]等同于(a[0])[j×M＋i]）
清楚了这些，我们就可以知道二维数组要比（模拟该二维数组的）一维数组寻址效率高。因为a[j][i]的寻址仅仅是访问指针数组得到j行的地址，然后再+i,是没有乘法运算的！
所以，在处理一维数组的时候，我们常常采用下面的优化办法：（伪码例子）
int a[M*N];
int *b=a;
for(…){
b[…]=…;
…………
b[…]=…;
b+=M; }
这个是遍历访问数组的一个优化例子，每次b+=M就使得b更新为下一行的头指针。当然如果你愿意的话，可以自己定义一个数组指针来存储每一行的起始地址。然后按照二维数组的寻址办法来处理一维数组。不过，在这里我建议你干脆就直接申请一个二维数组比较的好。下面是动态申请和释放一个二维数组的C代码。
int get_mem2Dint(int ***array2D, int rows, int columns) //h.263源代码
{
int i;
if((*array2D = (int**)calloc(rows, sizeof(int*))) == NULL) no_mem_exit(1);
if(((*array2D)[0] = (int* )calloc(rows*columns,sizeof(int ))) == NULL) no_mem_exit(1);
for(i=1 ; i
return rows*columns*sizeof(int); }
void free_mem2D(byte **array2D) {
if (array2D){
if (array2D[0]) free (array2D[0]);
else error ("free_mem2D: trying to free unused memory",100);
free (array2D);
} else{
error ("free_mem2D: trying to free unused memory",100); } }
顺便说一下，如果你的数组寻址有一个偏移量的话，不要写为a[x+offset]，而应该为 b=a+offset，然后访问b[x]。
不过，如果你不是处理对速度有特别要求的程序的话，这样的优化也就不必要了。记住，如果编普通程序的话，可读性和可移值性是第一位的。
II．从负数开始的数组
在编程的时候，你是不是经常要处理边界问题呢？在处理边界问题的时候，经常下标是从负数开始的，通常我们的处理是将边界处理分离出来，单独用额外的代码写。那么当你知道如何使用从负数开始的数组的时候，边界处理就方便多了。下面是静态使用一个从－1开始的数组：
int a[M];
int *pa=a+1;
现在如果你使用pa访问a的时候就是从－1到M－2了，就是这么简单。（如果你动态申请a的话，free（a）可不要free（pa）因为pa不是数组的头地址）
III．我们需要链表吗
相信大家在学习《数据结构》的时候，对链表是相当熟悉了，所以我看有人在编写一些耗时算法的时候，也采用了链表的形式。这样编写当然对内存的占用（似乎）少了，可是速度呢？如果你测试：申请并遍历10000个元素链表的时间与遍历相同元素的数组的时间，你就会发现时间相差了百倍！（以前测试过一个算法，用链表是1分钟，用数组是4秒钟）。所以这里我的建议是：在编写耗时大的代码时，尽可能不要采用链表！
其实实际上采用链表并不能真正节省内存，在编写很多算法的时候，我们是知道要占用多少内存的（至少也知道个大概），那么与其用链表一点点的消耗内存，不如用数组一步就把内存占用。采用链表的形式一定是在元素比较少，或者该部分基本不耗时的情况下。
(我估计链表主要慢是慢在它是一步步申请内存的，如果能够象数组一样分配一个大内存块的话，应该也不怎么耗时，这个没有具体测试过。仅仅是猜想 :P)
作者相关文章： C程序优化之路(三)(原作) C程序优化之路(原作)
对该文的评论 xrenwu(2002-12-12 12:07:43)
您的文章真是cool，我一路支持!!!!!!!!!!!!
Analyst(2002-12-11 15:54:26)
第一条是在胡说八道，哪个编译器在实现二维数组的时候用指针数组的？至少我没见过。 第三条也是在误导初学者，用什么数据结构是要根据选用的算法来决定的，哪能一概而论？
qimans(2002-12-11 15:06:15)
文章不错，有道理。 但是第三点的数组和链表的关系我不敢苟同。 我的工作与用户数有关，用户数是个未知数，今天少点明天多点， 所以我用的是数组链表，即每个节点都是一个数组， 这样既避免了大内存的浪费，也避免了小内存的溢出。
同意leizhengdeng的观点， goldenlinn提到的“Memory Pool”内存池技术不错， 但也存在申请不到或造成浪费的不足。
goldenlinn(2002-12-11 9:51:55)
我想在使用大规模链表的时候如果先申请到足够大的内存（比如先申请10000个元素）保留起来，在需要的时候按顺序将元素指针赋给申请代码，这样就可以不用每次链表增加元素时都要动态申请内存，节约大量时间。有人称此做法为“Memory Pool”，即内存池技术。
liyuming1978(2002-12-10 21:57:06)
我觉得语言学到一定程度就不能光看书了，做点东西，主要要看别人得代码，要优秀得代码才看， 我这些东西很多是从h263的代码知道的
liyuming1978(2002-12-10 21:54:53)
呵呵 ，有道理，改用链表的时候还是得用链表，主要我目前是搞图像处理，所以速度第一，而且图像处理中，一般没有插入等操作，导致了我对链表是“深恶痛绝”。
realdreamer(2002-12-10 19:21:40)
说老实话. 这些东西书上都有.
不懂的, 想学的朋友应该找本好书系统的学习.
leizhengdeng(2002-12-10 18:51:26)
编程时尽可能用栈，既不产生内存碎片，速度又快。
leizhengdeng(2002-12-10 18:49:20)
链表慢的原因： 1。分配内存需要时间 2。栈上的数组成员比堆上的快（堆上是先把指针变量放到寄存器，再去取元素）
作者忽略了链表和数组的优点： 数组随机访问快，而链表对成员插入删除快。 比如10000个数据，我要频繁的删除插入，在排序，这时数组就比链表慢。
crazybit(2002-12-10 14:11:05)
您的文章真是cool，我一路支持。
↑返回目录
前一篇: C程序优化之路(三)
后一篇: CREATING ROUND SWING BUTTONS