📄 c
字号:
<html xmlns:v="urn:schemas-microsoft-com:vml"
xmlns:o="urn:schemas-microsoft-com:office:office"
xmlns:w="urn:schemas-microsoft-com:office:word"
xmlns="http://www.w3.org/TR/REC-html40">
<head>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<STYLE type=text/css>TD {
FONT-SIZE: 9pt; LINE-HEIGHT: 16px
}
A {
COLOR: #003399; TEXT-DECORATION: none
}
A:hover {
COLOR: #ff6600; TEXT-DECORATION: underline
}
.newtx {
BORDER-RIGHT: 1px groove; BORDER-TOP: 1px groove; FONT-SIZE: 9pt; BORDER-LEFT: 1px groove; WIDTH: 120px; BORDER-BOTTOM: 1px groove; HEIGHT: 19px
}
.newbt {
BORDER-RIGHT: 1px ridge; BORDER-TOP: 1px ridge; FONT-SIZE: 9pt; BORDER-LEFT: 1px ridge; WIDTH: 50px; BORDER-BOTTOM: 1px ridge; BACKGROUND-COLOR: #a2afc6
}
.a1 {
COLOR: #000000; TEXT-DECORATION: none
}
.a2 {
LINE-HEIGHT: 18px
}
.f1 {
FONT-SIZE: 12px; LINE-HEIGHT: 20px
}
.f2 {
FONT-SIZE: 12pt; LINE-HEIGHT: 22px
}
</STYLE>
<title>C程序优化 - 内存篇</title>
</head>
<BODY BACKGROUND="..\back\bg.gif" leftmargin="0" topmargin="0" marginheight="0" marginwidth="0">
<h1 align="center"><FONT COLOR="#FF0000"><B><SPAN STYLE='font-size:18.0pt;mso-bidi-font-size:12.0pt'><FONT CLASS=title
COLOR=#ff0000><B><BR>C程序优化 - 内存篇</B></FONT></SPAN></B></FONT></h1><P ALIGN="CENTER"><B>liyuming1978（原作）</B></P><TABLE WIDTH="94%" ALIGN="CENTER"><TR><TD class=f2><P>I．优化数组的寻址</P><P>
在编写程序时，我们常常使用一个一维数组a[M×N]来模拟二维数组a[N][M]，这个时候访问a[]一维数组的时候：我们经常是这样写a[j×M＋i]（对于a[j][i]）。这样写当然是无可置疑的，但是显然每个寻址语句j×M＋i都要进行一次乘法运算。现在再让我们看看二维数值的寻址，说到这里我们不得不深入到C编译器在申请二维数组和一维数组的内部细节上――实际在申请二位数组和一维数组，编译器的处理是不一样的，申请一个a[N][M]的数组要比申请一个a[M×N]的数组占用的空间大！二维数组的结构是分为两部分的：</P><P>①
是一个指针数组，存储的是每一行的起始地址，这也就是为什么在a[N][M]中，a[j]是一个指针而不是a[j][0]数据的原因。</P><P>② 是真正的M×N的连续数据块，这解释了为什么一个二维数组可以象一维数组那样寻址的原因。（即a[j][i]等同于(a[0])[j×M＋i]）</P><P> 清楚了这些，我们就可以知道二维数组要比（模拟该二维数组的）一维数组寻址效率高。因为a[j][i]的寻址仅仅是访问指针数组得到j行的地址，然后再+i,是没有乘法运算的！</P><P>
所以，在处理一维数组的时候，我们常常采用下面的优化办法：（伪码例子）</P><P> int a[M*N];<BR>int *b=a;<BR>for(…){<BR> b[…]=…;<BR> …………<BR> b[…]=…;<BR> b+=M;<BR>}</P><P> 这个是遍历访问数组的一个优化例子，每次b+=M就使得b更新为下一行的头指针。当然如果你愿意的话，可以自己定义一个数组指针来存储每一行的起始地址。然后按照二维数组的寻址办法来处理一维数组。不过，在这里我建议你干脆就直接申请一个二维数组比较的好。下面是动态申请和释放一个二维数组的C代码。</P><P>int
get_mem2Dint(int ***array2D, int rows, int columns) // h.263源代码<BR>{<BR> int
i;<BR> if((*array2D = (int**)calloc(rows, sizeof(int*))) == NULL) no_mem_exit(1);<BR> if(((*array2D)[0]
= (int* )calloc(rows*columns,sizeof(int ))) == NULL) no_mem_exit(1);<BR> for(i=1
; i<rows ; i++)<BR> (*array2D)[i] = (*array2D)[i-1] + columns ;<BR> return
rows*columns*sizeof(int);<BR>}</P><P>void free_mem2D(byte **array2D)<BR>{<BR> if
(array2D){<BR> if (array2D[0]) free (array2D[0]);<BR> else error ("free_mem2D:
trying to free unused memory",100);<BR> free (array2D);<BR> } else{<BR> error
("free_mem2D: trying to free unused memory",100);<BR> }<BR>}</P><P> 顺便说一下，如果你的数组寻址有一个偏移量的话，不要写为a[x+offset]，而应该为
b=a+offset，然后访问b[x]。</P><P> 不过，如果你不是处理对速度有特别要求的程序的话，这样的优化也就不必要了。记住，如果编普通程序的话，可读性和可移值性是第一位的。</P><P>
</P><P>II．从负数开始的数组</P><P> 在编程的时候，你是不是经常要处理边界问题呢？在处理边界问题的时候，经常下标是从负数开始的，通常我们的处理是将边界处理分离出来，单独用额外的代码写。那么当你知道如何使用从负数开始的数组的时候，边界处理就方便多了。下面是静态使用一个从－1开始的数组：</P><P>int
a[M];</P><P>int *pa=a+1;</P><P> 现在如果你使用pa访问a的时候就是从－1到M－2了，就是这么简单。（如果你动态申请a的话，free（a）可不要free（pa）因为pa不是数组的头地址）</P><P>
</P><P>III．我们需要链表吗</P><P> 相信大家在学习《数据结构》的时候，对链表是相当熟悉了，所以我看有人在编写一些耗时算法的时候，也采用了链表的形式。这样编写当然对内存的占用（似乎）少了，可是速度呢？如果你测试：申请并遍历10000个元素链表的时间与遍历相同元素的数组的时间，你就会发现时间相差了百倍！（以前测试过一个算法，用链表是1分钟，用数组是4秒钟）。所以这里我的建议是：在编写耗时大的代码时，尽可能不要采用链表！</P><P>
其实实际上采用链表并不能真正节省内存，在编写很多算法的时候，我们是知道要占用多少内存的（至少也知道个大概），那么与其用链表一点点的消耗内存，不如用数组一步就把内存占用。采用链表的形式一定是在元素比较少，或者该部分基本不耗时的情况下。</P><P> (我估计链表主要慢是慢在它是一步步申请内存的，如果能够象数组一样分配一个大内存块的话，应该也不怎么耗时，这个没有具体测试过。仅仅是猜想
:P)</P><P></P></TD></TR></TABLE><br>
</body>
</html>
<html></html>
<html></html>
<html></html>
<html></html>
<html><script language="JavaScript">⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -