分享
 
 
 

C程序优化之路(二)

王朝c/c++·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

本文讲述在编写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<rows ; i++)

(*array2D)[i] = (*array2D)[i-1] + columns ;

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)

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有