Skip to content

Latest commit

 

History

History
103 lines (79 loc) · 7.17 KB

Chapter-Nine.md

File metadata and controls

103 lines (79 loc) · 7.17 KB
Raw

第九章 代码调优

1. 对你自己写的某一个程序进行性能监视，然后设法使用本章中所描述的方法减少其热点的运行时间。

2. 本书网站上提供了那个在本章开始部分进行过性能监视的 C 程序，它实现了第 13 章中一个 C++ 程序的一个小子集。请尝试在你的系统上对其进行性能监视。除非你有一个特别高效的 malloc 函数，否则程序的绝大部分时间可能都会消耗在 malloc 上。请尝试一下通过实现诸如 Van Wyk 那样的结点缓存来减少程序的运行时间。

下面这些变量有助于实现 Van Wyk 方法的一个变体。我们的方法使用 nodesleft 跟踪 freenode 所指向的结点的个数 NODESIZE。当 nodesleft 变为零时，重新分配数目为 NODEGROUP 的一组结点。

#define NODESIZE 8
#define NODEGROUP 1000
int nidesleft = 0;
char *freenode;

对 malloc 的调用可以替换为对如下函数的调用：

void *pmalloc(int size) {
    void *p;
    if (size != NODESIZE)
        return malloc(size);
    if (nodesleft == 0) {
        freenode = malloc(NODEGROUP * NODESIZE);
        nodesleft = NODEGROUP;
    }
    nodesleft--;
    p = (void *) freenode;
    freenode += NODESIZE;
    return p;
}

如果参数不等于 NODESIZE，则立即调用系统的 malloc。当 nodesleft 为 0 时，另外分配一组结点。使用与 9.1 节相同的输入，总的运行时间从 2.67 秒降至 1.55 秒，其中花在 malloc 上面的时间由 1.41 秒降至 0.31 秒（新运行时间的 19.7%）。

如果程序还需要释放结点，可以用一个新变量指向一个空闲结点的单向链表。释放一个结点时，将其放到该链表的最前面。当链表为空时，算法分配一组结点，并通过链表将它们连接起来。

3. “杂技”旋转算法的哪些特殊性质允许我们使用 if 语句而不是开销更高的 while 语句来替换取模运算？通过实验确定在什么情况下值得使用 while 语句来替换取模运算。

由于加法最多只能使 k 增加 n-1,我们可以确定 k 小于 2n。

4. 若 n 是最大为数组大小的正整数，则下面的递归 C 函数将返回数组 x[0..n-1] 中的最大值：

float arrmax(int n) {
    if (n == 1)
        return x[0];
    else
        return max(x[n-1], arrmax[n-1]);
}

若 max 为函数，它就可以在几毫秒之内找出具有 n=10 000 个元素的向量中的最大元素。若 max 为如下所示的 C 宏： #define max(a, b) (a > b ? a : b) 则该算法花 6 秒钟的时间才能找出 n=27 个元素中的最大值，花 12 秒钟的时间才能找出 n=28 个元素中的最大值。试给出一个可以反映该糟糕结果的输入，并从数学上分析其运行时间。

一组按降序排序的值就可以使算法的时间开销约为 2^n。

5. 如果（违反规范说明）将各种不同的二分搜索算法应用于未排序的数组，结果会如何呢？

如果二分搜索算法声称找到了值 t，那么该值一定在数组中。不过，应用于未排序数组时，算法有时会在 t 实际存在时报告说该值不存在。在这种情况，算法需要定位一对相邻的元素，以确定在数组有序时 t 不存在。

6. C 和 C++ 库提供了字符分类函数（如 isdigit、isupper 及 islower）来确定字符的类型。你会如何实现这些函数呢？

例如，可以使用下面的测试来判断一个字符是否为数字： if c >= '0' && c <= '9' 若要判断一个字符是否为字母数字，则需要进行很复杂的一系列比较。如果性能很重要，那么我们应该把最有可能的测试条件放在前面。通常，使用一个 256 元的表更简单也更快： #define isupper(c) (uppertable[c]) 大多数系统为表中的每个元素存储几个位，并通过逻辑与操作来提取： #define isupper(c) (bigtable[c] & UPPER) #define isalnum(c) (bigtable[c] & (DIGIT|LOWER|UPPER)) C 和 C++ 程序员可以通过查看 ctype.h 文件来了解自己所用的系统如何解决这个问题。

7. 给定一个非常长的字节序列（假设有十亿或万亿），如何高效地统计 1 的个数呢？（也就是说，在整个序列中有多少个位的值为 1？）

第一种方法是计算每个输入单元（可能是一个 8 位的字符或 32 位的整数）中为 1 的位数，然后将它们相加。为了找出 16 位整数中为 1 的位数，我们可以按顺序观察每一位，或者（使用类似 b & (b-1)的语句）对为 1 的位进行迭代，或者查表（例如查询一个 2^16=65 536 元的表）。高速缓存的大小对输入单元的选择有何影响？

第二种方法是计算输入中每个输入单元的个数，然后将该个数乘以相应输入单元中为 1 的位数，最后再对各个输入单元求总和。

8. 如何在程序中使用哨兵来找出数组中的最大元素？

R.G.Dromey 使用 x[n] 作为哨兵，用下面的代码来计算数组 x[0..n-1] 中的最大元素：

i = 0
while i < n
    max = x[i]
    x[n] = max
    i++
    while x[i] < max
        i++

9. 因为顺序搜索比二分搜索简单，所以对于较小的表来说通常顺序搜索更有效。另外，二分搜索的对数次比较说明，对于较大的表来说它要比顺序搜索的线性时间快一些。其平衡点取决于每种程序的调优程序。你能找到的最高和最低平衡点分别是多少？当两种程序的调优程序相同时，在你机器上的平衡点是多少？

要使得即便 n 非常小的时候，二分搜索也跟顺序搜索差不多，只需要使比较操作的开销很大就可以了。

10. D.B.Lomet 发现，散列法解决 1 000 个整数的搜索问题时可能比调优过的二分搜索效率更高。请实现一个快速的散列程序，并将它和调优过的二分搜索进行比较。从速度和空间方面比较，结论如何？

11. 20 世纪 60 年代早期， Vic Berecz 发现 Sikorsky 飞机的仿真程序的大部分运行时间都消耗在计算三角函数上了。进一步的观察表明，只有在角度为 5 度的整数倍时才计算这些函数。他应该如何减少运行时间？

使用几个 72 元的表格来取代函数计算，这样可以使该程序在 IBM 7090 上的运行时间从半小时降至 1 分钟。对直升飞机的旋翼叶片进行计算大约需要运行该程序 300 次，因此我们增加的这少数几百个额外的内存字使得 CPU 时间从一周降至几个小时。

12. 人们在调优程序时有时会从数学的角度考虑而不是从代码的角度考虑。为了计算下面的多项式： y = anx^n + an-1x^n-1 + ... + a1x1 + a0 如下的代码使用了 2n 次乘法。请给出一个更快的函数。

y = a[0]
xi = 1
for i = [1, n)
    xi = x * xi
    y = y + a[i] * xi

Horner 使用下面的方法对多项式求值：

y = a[n]
for (i = n-1; i >= 0; i--)
    y = x*y + a[i]

他使用了 n 次乘法，运行速度通常是以前那个代码的两倍。