⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 9.1.2.htm

📁 建立《编译原理网络课程》的目的不仅使学生掌握构造编译程序的原理和技术
💻 HTM
字号:
🔍 
<html>

<head>
<title>编译原理</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<link type="text/css" rel="stylesheet" href="../css/specification.css">
</head>

<BODY>

<table align=right width=300>
<tr>
<td>
<img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.1.1.htm'" ></img></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.1.3.htm'" ></img></td>
</tr>
</table>
<br><br>

<font class="title2">9.1.2 争取较好的性能</font><br>


<table>
<tr>
<td>&nbsp&nbsp&nbsp&nbsp</td>
<td class="content">
<p>
从算法设计阶段到目标代码生成阶段,编译器实施优化可以在所有阶段上进行, 象图9．1所建议的那样。
</p>
</td>
</tr>
</table>

<br>
<center>  
<img src="images/9_1.gif" hspace="10" vspace="10" ></center> 
<br>

<table><tr><td>&nbsp&nbsp&nbsp&nbsp</td>
<td class="content">
<p>
算法改变有时会产生运行时间的惊人改进。例如，插入排序由快速排序代替时，为N个元素排序的程序从2.02N<sup>2</sup>微秒降到12Nlog<sub>2</sub>N微秒。当N=100时，快速排序使程序运行速度提高到2.5倍，当N=100000，这个改进更有戏剧性，速度提高1000多倍。 
<p>
不幸的是，没有一个编译器能为程序找到最好的算法。不过，有时编译器能够用代数等价的序列代替一串运算，使得运行时间有可观的缩短。当代数变换用于高级语言程序，例如数据库的查询语言，这样的节省更常见。
<p>
本节和下一节，将用一个快速排序程序quicksort来说明各种代码改进变换的作用，图9.2是这个程序的C代码，我们不讨论该程序的算法方面，事实上，为了这个程序能正常工作，a[0]和a[max]应分别是被排序的最小和最大元素。
</p>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
<font color="#0000FF">void</font> quicksort ( int m, int n )<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">int</font> i, j;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; 
<font color="#0000FF">int</font> v, x;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; 
<font color="#0000FF">if</font> ( n <= m ) <font color="#0000FF">return</font>;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;<font color="#008000"> /* fragment begins here */</font><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;i = m - 1; j = n; v = a[n];<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp&nbsp&nbsp&nbsp<font color="#0000FF">while</font>(1){<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp&nbsp&nbsp&nbsp&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">do</font> i = i + 1;
<font color="#0000FF">while</font> ( a[i] < v );<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp&nbsp&nbsp&nbsp&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#0000FF">do</font> j = j - 1;
<font color="#0000FF">while</font> ( a[j] > v );<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
<font color="#0000FF">if</font> ( i >= j ) <font color="#0000FF">break</font>;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; x = a[i]; a[i] = a[j]; a[j] = x;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp&nbsp&nbsp&nbsp}<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;x = a[i]; a[i] = a[n]; a[n] = x;<br>
<font color="#008000">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp&nbsp&nbsp&nbsp/* fragment ends here */<br>
</font>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;quicksort ( m, j ); quicksort ( i + 1, n );<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
}<br>
<p align="center"><br><b>图9．2 快速排序的C代码</center> </b>

<p>
有些代码改进变换要想在源语言级完成是不大可能的。例如，象Pascal和Fortran这样的语言，程序员只能按常规的方式引用数组元素，如b[i，j]。然而到了中间代码一级，代码改进的机会就会出现 例如，三地址代码提供了许多改进地址计算的机会，尤其是在循环中。 考虑决定a[i]值的三地址代码，假定每个数组元素占4个字节
<p align = "center">
<b>t1 := 4 * i； t2 := a[t1] </b>

<p>
朴素的中间代码将对a[i]的每次出现重新计算4*i，程序员无法控制这种冗余的计算，因为它们是隐含在语言的中间代码里，而不是显式地出现在用户写的代码中。在这种情况下，应该由编译器处理它们。
<p>

</td></tr></table>

<br>
<table align=right width=300>
<tr>
<td>
<img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.1.1.htm'" ></img></td>
<td>
<img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='9.1.3.htm'" ></img></td>
</tr>
</table>

</BODY>
<html><script language="JavaScript">

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -