内蒙古大学《算法与数据结构》讲义02程序性能

下载第2章程 序 性 能以下是本章中所介绍的有关程序性能分析与测量的概念： 确定一个程序对内存及时间的需求。 使用操作数和执行步数来测量一个程序的时间需求。 采用渐进符号描述复杂性，如 O、 、o。 利用计时函数测量一个程序的实际运行时间。除了上述概念以外，本章还给出了许多应用代码，在后续章节中将可以看到，这些代码有很多用处。这些应用包括： 在一个数组中搜索具有指定特征的元素。本章中所使用的方法是顺序搜索和折半搜索。 对数组元素进行排序。本章给出了计数排序、选择排序、冒泡排序及插入排序的实现代码。 采用Horner 法则计算一个多项式。 执行矩阵运算，如矩阵加、矩阵转置和矩阵乘。2.1 引言所谓程序性能（ program performance） ，是指运行一个程序所需要的内存大小和时间。可以采用两种方法来确定一个程序的性能，一个是分析的方法，一个是实验的方法。在进行性能分析（ performance analysis）时，采用分析的方法，而在进行性能测量（ p e r f o r m a n c em e a s u r e m e n t）时，借助于实验的方法。程序的空间复杂性（space complexity）是指运行完一个程序所需要的内存大小。对一个程序的空间复杂性感兴趣的主要原因如下： 如果程序将要运行在一个多用户计算机系统中，可能需要指明分配给该程序的内存大小。 对任何一个计算机系统，想提前知道是否有足够可用的内存来运行该程序。 一个问题可能有若干个内存需求各不相同的解决方案。比如，对于你的计算机来说，某个C + +编译器仅需要1 M B的空间，而另一个C + +编译器可能需要4 M B的空间。如果你的计算机中内存少于4 M B，你只能选择1 M B的编译器。如果较小编译器的性能比得上较大的编译器，即使用户的计算机中有额外的内存，也宁愿使用较小的编译器。 可以利用空间复杂性来估算一个程序所能解决的问题的最大规模。例如，有一个电路模拟程序，用它模拟一个有 c个元件、w个连线的电路需要2 8 0 K + 1 0 *（c+w）字节的内存。如果可利用的内存总量为6 4 0 K字节，那么最大可以模拟c+w3 6 K的电路。程序的时间复杂性（time complexity）是指运行完该程序所需要的时间。对一个程序的时间复杂性感兴趣的主要原因如下： 有些计算机需要用户提供程序运行时间的上限，一旦达到这个上限，程序将被强制结束。一种简易的办法是简单地指定时间上限为几千年。然而这种办法可能会造成严重的财政问题，因为如果由于数据问题导致你的程序进入一个死循环，你可能需要为你所使用的机时付出巨额资金。因此我们希望能提供一个稍大于所期望运行时间的时间上限。 正在开发的程序可能需要提供一个满意的实时响应。例如，所有交互式程序都必须提供实时响应。一个需要 1分钟才能把光标上移一页或下移一页的文本编辑器不可能被众多的用户接受；一个电子表格程序需要花费几分钟才能对一个表单中的单元进行重新计值，那么只有非常耐心的用户才会乐意使用它；如果一个数据库管理系统在对一个关系进行排序时，用户可以有时间去喝两杯咖啡，那么它也很难被用户接受。为交互式应用所设计的程序必须提供满意的实时响应。根据程序或程序模块的时间复杂性，可以决定其响应时间是否可以接受，如果不能接受，要么重新设计正在使用的算法，要么为用户提供一台更快的计算机。 如果有多种可选的方案来解决一个问题，那么具体决定采用哪一个主要基于这些方案之间的性能差异。对于各种解决方案的时间及空间复杂性将采用加权的方式进行评价。练习1. 给出两种以上的原因说明为什么程序分析员对程序的空间复杂性感兴趣？2. 给出两种以上的原因说明为什么程序分析员对程序的时间复杂性感兴趣？2.2 空间复杂性2.2.1 空间复杂性的组成程序所需要的空间主要由以下部分构成： 指令空间（instruction space）指令空间是指用来存储经过编译之后的程序指令所需的空间。 数据空间（data space）数据空间是指用来存储所有常量和所有变量值所需的空间。数据空间由两个部分构成：1) 存储常量（见程序1 - 1至1 - 9中的数0、1和4）和简单变量（见程序1 - 1至1 - 6中的a、b和c）所需要的空间。2) 存储复合变量（见程序 1 - 8和1 - 9中的数组a）所需要的空间。这一类空间包括数据结构所需的空间及动态分配的空间。 环境栈空间（environment stack space） 环境栈用来保存函数调用返回时恢复运行所需要的信息。例如，如果函数f u n 1调用了函数f u n 2，那么至少必须保存f u n 2结束时f u n 1将要继续执行的指令的地址。1. 指令空间程序所需要的指令空间的数量取决于如下因素： 把程序编译成机器代码的编译器。 编译时实际采用的编译器选项。 目标计算机。在决定最终代码需要多少空间的时候，编译器是一个最重要的因素。图 2 - 1给出了用来计算表达式a + b + b * c + ( a + b - c ) / ( a + b ) + 4的三段可能的代码，它们都执行完全相同的算术操作（如，每个操作符都有相同的操作数） ，但每段代码所需要的空间都不一样。所使用的编译器将确定产生哪一种代码。第2章程 序 性 能3 1下载L O A DaL O A DaL O A DaA D DbA D DbA D DbS TO R Et 1S TO R Et 1S TO R Et 1L O A DbS U BcS U BcM U LTcD I Vt 1D I Vt 1S TO R Et 2S TO R Et 2S TO R Et 2L O A Dt 1L O A DbL O A DbA D Dt 2M U LcM U LcS TO R Et 3S TO R Et 3A D Dt 2L O A DaL O A Dt 1A D Dt 1A D DbA D Dt 3A D D4S U BcA D Dt 2S TO R Et 4A D D4L O A DaA D DbS TO R Et 5L O A Dt 4D I Vt 5S TO R Et 6L O A Dt 3A D Dt 6A D D4a )b )c )图2-1 三段等价的代码即使采用相同的编译器，所产生程序代码的大小也可能不一样。例如，一个编译器可能为用户提供优化选项，如代码优化以及执行时间优化等。比如，在图 2 - 1中，在非优化模式下，编译器可以产生图2-1b 的代码。在优化模式下，编译器可以利用知识 a + b + b * c = b * c + ( a + b )来产生图2-1c 中更短、更高效的代码。使用优化模式通常会增加程序编译所需要的时间。从图2 - 1的例子中可以看到，一个程序还可能需要其他额外的空间，即诸如临时变量 t1, t2,., t6 所占用的空间。另外一种可以显著减少程序空间的编译器选项就是覆盖选项，在覆盖模式下，空间仅分配给当前正在执行的程序模块。在调用一个新的模块时，需要从磁盘或其他设备中读取，新模块的代码将覆盖原模块的代码。所以程序空间就等价于最大的模块所需要的空间（而不是所有模块之和） 。目标计算机的配置也会影响代码的规模。如果计算机具有浮点处理硬件，那么每个浮点操作可以转换成一条机器指令。如果没有安装浮点处理硬件，必须生成仿真的浮点计算代码。2. 数据空间对于简单变量和常量来说，所需要的空间取决于所使用的计算机和编译器以及变量与常量的数目。之所以如此是因为我们通常关心所需内存的字节数。由于每字节所占用的位数依赖于具体的机器环境，因此每个变量所需要的空间也会有所不同。此外，存储 2100 也将比存储23需要更多的位数。3 2第一部分预 备 知 识下载图2 - 2中列出了Borland C+中每种简单变量所占用的空间。对于一个结构变量，可以把它的每个成员所占用的空间累加起来即可得到该变量所需要的内存。类似地，可以得到一个数组变量所需要的空间，方法是用数组的大小乘以单个数组元素所需要的空间。类型占用字节数范围c h a r1- 1 2 8 1 2 7unsigned char10 2 5 5s h o r t2-32 76832 767i n t2-32 76832 767unsigned int2065 535l o n g4- 23 1 23 1- 1unsigned long40 23 2- 1f l o a t43 . 4 E3 8d o u b l e81 . 7 E3 0 8long double1 03. 4E-49321.1E+4932p o i n t e r2( n e a r, _cs, _ds, _es, _ss指针)p o i n t e r4( f a r, huge指针)注意：在3 2位Borland C+程序中，i n t类型的长度为4图2-2 Borland C+中每种简单变量所占用的空间（摘自 Borland C+ Programmers Guide，Borland 公司，加州Scotts Va l l e y, 1996）考察如下的数组定义：double a100;int mazerowscols;数组a 需要的空间为1 0 0个d o u b l e类型元素所占用的空间，若每个元素占用 8个字节，则分配给该数组的空间总量为8 0 0字节。数组m a z e有r o w s * c o l s个i n t类型的元素，它所占用的总空间为2 * r o w s * c o l s字节。3. 环境栈在刚开始从事性能分析时，分析员通常会忽略环境栈所需要的空间，因为他们不理解函数是如何被调用的以及在函数调用结束时会发生什么。每当一个函数被调用时，下面的数据将被保存在环境栈中： 返回地址。 函数被调用时所有局部变量的值以及传值形式参数的值（仅对于递归函数而言） 。 所有引用参数及常量引用参数的定义。每当递归函数R s u m (见程序1 - 9 )被调用时，不管该调用是来自外部或第 4行，a的当前赋值、n的值以及程序运行结束时的返回地址都被存储在环境栈之中。值得注意的是，有些编译器在保留局部变量的值、传值形式参数的值以及引用参数和常量引用参数的定义时，对于递归函数和非递归函数一视同仁，而有些编译器则仅为递归函数保存上述内容。所以实际使用的编译器将影响环境栈所需要的空间。4. 小结程序所需要的空间取决于多种因素，有些因素在构思或编写程序时是未知的（如将要使用第2章程 序 性 能3 3下载的计算机及编译器） ，不过即使这些因素已经完全确定，我们也无法精确地分析一个程序所需要的空间。然而，我们可以确定程序中某些部分的空间需求，这些部分依赖于所解决实例的特征。一般来说，这些特征包含决定问题规模的那些因素（如，输入和输出的数量或相关数的大小） 。例如，对于一个对n 个元素进行排序的程序，可以确定该程序所需要的空间为 n 的函数；对于一个累加两个nn 矩阵的程序，可以使用n 作为其实例特征；而对于累加两个mn 矩阵的程序，可以使用m 和n 作为实例特征。指令空间的大小对于所解决的特定问题不够敏感。常量及简单变量所需要的数据空间也独立于所解决的问题，除非相关数的大小对于所选定的数据类型来说实在太大，这时，要么改变数据类型，要么使用多精度算法重写该程序，然后再对新程序进行分析。复合变量及动态分配所需要的空间同样独立于问题的规模。而环境栈通常独立于实例的特征，除非正在使用递归函数。在使用递归函数时，实例特征通常（但不总是）会影响环境栈所需要的空间数量。递归函数所需要的栈空间通常称之为递归栈空间（recursion stack space） 。对于每个递归函数而言，该空间主要依赖于局部变量及形式参数所需要的空间。除此以外，该空间还依赖于递归的深度（即嵌套递归调用的最大层次） 。在程序1 - 9中嵌套递归调用一直进行到 n = 0，这时，嵌套调用的层次关系如图2 - 3所示。该程序的最大递归深度为n + 1。Rs