钱能C++程序设计教程6.ppt

3 16 2020 1 C 程序设计教程 第二版 第六章性能Chapter6Performance 清华大学出版社钱能 3 16 2020 2 提高性能的意义 性能对提高编程能力举足轻重如何提高性能 以合理使用资源为前提 尽快完成任务的能力称为效率 效率影响性能 提高效率就能提高性能学习目标 1 扩展视野 对同一问题的不同要求 模仿各种编程技巧与空间布局策略 予以应对 从而对各种不同的问题 亦能应变自如2 掌握测试性能的方法 学会测算时 空交换的代价 客观评估自身的编程能力 3 16 2020 3 第六章内容 内联函数 InlineFunctions 数据结构 DataStructures 算法 Algorithms 数值计算 NumericalComputation STL算法 STLAlgorithms 动态内存 DynamicMemory 低级编程 LowerProgramming 3 16 2020 4 1 内联函数 InlineFunctions 做法 将一些反复被执行的简单语句序列做成小函数用法 在函数声明前加上inline关键字作用 不损害可读性又能提高性能 3 16 2020 5 includeboolisDigit char 小函数intmain for charc cin c 频繁调用的函数 用昂贵的开销换取可读性 3 16 2020 6 includeintmain for charc cin c 内嵌代码 开销虽少 但可读性差 3 16 2020 7 内联方式 开销少 可读性也佳 includeinlineboolisDigit char 小函数intmain for charc cin c 内联标记放在函数声明的前面 3 16 2020 8 内联函数的使用经验 函数体适当小 且无循环或开关语句 这样就使嵌入工作容易进行 不会破坏原调用主体 如 排序函数不能内联程序中特别是在循环中反复执行该函数 这样就使嵌入的代码利用率较高 如 上例中的isDigit函数程序并不多处出现该函数调用 这样就使嵌入工作量相对较少 代码量也不会剧增 3 16 2020 9 include includeusingnamespacestd intcalc1 inta intb returna b inlineintcalc2 inta intb returna b intmain intx 1000 y 1000 z 1000 clock tt clock for inti 0 i 1000 1000 1000 i z i calc1 x i 1000 y i 1000 cout clock t CLK TCK withoutinline n t clock for inti 0 i 1000 1000 1000 i z i calc2 x i 1000 y i 1000 cout clock t CLK TCK withinline n 性能测试 初记时 末记时 非内联函数 内联函数 3 16 2020 10 结果分析 内联用与不用差很多结论 应尽量将函数改造成可内联性质 提高性能 E ch06 f0605 8 281withoutinline2 437withinline 3 16 2020 11 2 数据结构 DataStructures 揭示 将数据结构实现为数据类型是编程的高级境界 STL容器就是系统提供的现成数据结构做法 充分和合理使用STL容器 简化复杂问题 提高编程效率与程序性能 3 16 2020 12 问题 有许多序列 每个序列都等待验证是否可从顺序数列经过栈操作而得 例如 顺序数列1 2 3 4 5待验证序列3 2 1 5 4待验证序列5 3 4 2 1 3 16 2020 13 采用不同的数据结构 include include include 栈方式 include 向量方式 includeusingnamespacestd 3 16 2020 14 栈方式 intmain ifstreamin rail txt for intn line 0 in n 栈中若不存在读入的元素 则应入栈 创建栈 读入元素不在栈顶即为失败 退栈即逐个逐个过 3 16 2020 15 向量方式 intmain ifstreamin rail txt for intn line 0 in n 模仿栈操作 3 16 2020 16 结论 不同的数据结构有不同的操作和性能应学习使用不同数据结构的经验 3 16 2020 17 3 算法 Algorithms 揭示 确定了数据结构之后 所采用的算法将直接决定程序的性能 任何语言都有个性 算法的选择使用是灵巧运用语言的艺术 充分发挥语言的优势是活用算法的根本做法 培养经验 用测试的办法对算法进行选择 3 16 2020 18 问题 已知不太大的正整数n n 46 求Fibonacci数列0112358132134 的第n项的值 对于后面的四种算法 unsignedfibo1 unsignedn unsignedfibo2 unsignedn unsignedfibo3 unsignedn unsignedfibo4 unsignedn 如何选择其中之一 第0项 第1项 第2项 3 16 2020 19 算法 递归法优点 算法简单 容易编程缺点 栈空间负担过重 调用开销过大 unsignedfibo1 unsignedn if n 1 returnn returnfibo1 n 1 fibo1 n 2 n 0或1 3 16 2020 20 算法 迭代法优点 节省空间 节省时间缺点 编程相对复杂 unsignedfibo2 unsignedn intc n for inta 0 b 1 i 2 i n i c a b a b b c returnc 3 16 2020 21 算法3 向量迭代法优点 节省时间缺点 n越大 占用堆空间越多 unsignedfibo3 unsignedn vectorv n 1 0 v 1 1 for unsignedi 2 i n i v i v i 1 v i 2 returnv n 3 16 2020 22 算法4 直接计算法优点 节省时间缺点 引入了浮点计算 unsignedfibo4 unsignedn return pow 1 sqrt 5 0 2 n pow 1 sqrt 5 0 2 n sqrt 5 0 3 16 2020 23 fibo1 只在示意性编程中使用 但并不是否定一切递归法fibo2 在讲究性能的场合中使用 它省空间省时间 但在n很大的场合中 性能比不上fibo4fibo3 可以数组代替向量 提高低级编程的性能 它易编易用 还可以读取中间项的值 但在一味追求性能的场合中 比不上fibo2fibo4 在n不太大时 与fibo2相当 在n趋向很大时 其性能优势便充分体现 3 16 2020 24 揭示 在近似计算中 除了计算范围与终止计算条件外 还涉及逼近的快慢 这与算法有很大关系 选择成熟的算法具有决定性作用做法 了解各种数值计算算法的特点及使用场合 有的放矢解决实际问题 3 16 2020 25 数值计算的参数描述 template T为赖以计算的数系Tmethod method为某种算法Ta 左边界Tb 右边界constTEpsilon 终止条件T f T 求值数学函数 3 16 2020 26 矩形法 doublerectangle doublea doubleb constdoubleEps double f double doublew b a sN w f a f b 2 sO 0 for intn 1 abs sN sO Eps n 2 sO sN sN 0 for inti 0 i n i sN f a w i 0 5 n sN w n returnsN 小矩形逐个求和 前后两次小矩形和的差 3 16 2020 27 辛普生法 doublesimpson doublea doubleb constdoubleEps double f double doubleI2n 0 h b a T2n h f a f b 2 In T2n Tn for intn 1 abs I2n In Eps n n h 2 0 In I2n Tn T2n In老积分值doublesigma 0 for intk 0 k n k sigma f a k 0 5 h T2n Tn h sigma 2 I2n 4 T2n Tn 3 I2n新积分值 returnI2n 小矩形求和 辛普生处理 前后两次辛普生值的差 3 16 2020 28 性能比较 求同样的数学函数 区间和精度矩阵法比辛普生法多循环许多次 3 16 2020 29 5 标准 算法 StandardC Algorithms 揭示 标准C 提供了诸多算法 这些算法的组合构成了许多问题的解 对算法的准确了解是编程能力的一大体现做法 吃透标准 算法 灵活运用之 3 16 2020 30 容器的区间表示 vectora 10 下面表示待处理的元素vectorb a begin 1 a begin 7 0 1 2 3 4 5 6 7 8 9 首 尾 待处理的元素 3 16 2020 31 逐一读入两个 字串 比较是否含有相同元素 intmain ifstreamin string txt for strings t in s t 比较输出yes或no 3 16 2020 32 分别排序 直接加以字串比较是直截了当的思路 for strings t in s t sort s begin s end sort t begin t end cout s t yes n no n C 标准算法 3 16 2020 33 避免排序 分别统计两个字串中 的个数则性能更优 排序至少做O nlogn 数量级运算 统计只做O n 数量级运算 for strings t in s t ints1 count s begin s end 1 ints0 count s begin s end 0 intt1 count t begin t end 1 intt0 count t begin t end 0 cout s1 t1 C 标准算法 3 16 2020 34 字串中非 即 的特征 可以避免多余的统计 进一步提高性能 for strings t in s t ints1 count s begin s end 1 intt1 count t begin t end 1 cout s1 t1 C 标准算法 3 16 2020 35 6 动态内存 DynamicMemory 揭示 许多问题不知道数据量的大小 需要所运用的数据结构具有扩容能力 许多问题要求时间性能甚于空间占用 充分利用堆空间 动态内存 是解决这些问题的关键做法 理解堆空间的使用场合 学习堆空间的使用方法 3 16 2020 36 使用容器 便是自动使用堆内存 例如 从abc txt中读取诸段落 ifstreamin abc txt vectorps ps reserve 1100 可以预留for strings getline in s ps push back s 预留是减小频繁扩容造成的数据移动开销 3 16 2020 37 若每个数据的处理 都要用到已经处理的数据时 保存历史数据 则可以改善时间性能 例如 统计一亿之内的素数个数 原始版 boolisPrime intn intsqrtn sqrt n 1 0 for inti 2 i sqrtn i if n i 0 returnfalse returntrue intmain intnum 0 for inti 2 i 100000000 i if isPrime i num cout num endl 3 16 2020 38 空间换时间版 intmain bitset p newbitset p set for inti 2 itest i for intj i i jsize j i p reset j intnum 0 for inti 2 itest i num cout num endl delete p 在空间中统计 完成每个元素的标记 3 16 2020 39 7 低级编程 LowerProgramming 揭示 通过无原则的代码优化来简化程序的执行步骤 从而提高性能 它会影响可读性 并需要对程序的内存布局有深刻的了解 这一般是编程课的后继学习内容做法 尽量去掉组织程序所花费的代价 少用调用频繁的函数 通过指针间访数据 尽可能不用类 无原则数据共享 用C库不用C 库 3 16 2020 40 低级编程版 逐一读入两个 字串 比较是否含有相同元素 intcnt char a intnum 0 while a if a 1 num returnnum intmain freopen string txt r stdin chara 1025 b 1025 whlie scanf s a 0 3 16 2020 41 STL容器是为方便编程设计的 它当然也考虑了性能 但与直接操纵堆空间相比还是间接了些 例如 一亿之内的筛法求素数个数 版 intsieveSTL bitset 3 16 2020