《编程珠玑》第 9 章──代码调优

「代码调优」首先确定程序中开销较大的部分,然后进行少量的修改,以提高其运行速度。

急救方案集锦

整数取模

原先的取模方法是:

1
k = (j + rotdist) % n;

由于模运算开销较大,所以改成如下方法:

1
2
3
4
k = j + rotdist;
while(k >= n){
k -= n;
}

函数、宏和内联代码

第 8 章的最大值函数:

1
2
3
float max(float a, float b){
return a > b ? a : b;
}

使用宏替换 max 函数:

1
#define max(a, b)((a)>(b)?(a):(b));

顺序搜索

最简单直接的顺序搜索,就是从前往后搜索。

1
2
3
4
5
6
int ssearch1(4){
for i = [0, n)
if x[i] == t
return i
return -1
}

然后将内循环中的两种检测(是否到了尾部;是不是所需元素)改成一种检测。

1
2
3
4
5
6
7
8
9
10
11
12
13
int ssearch2(t){
hold = x[n];
x[n] = t;
for(i = 0; ; i++){
if x[i] == t
break
}
x[n] = hold;
if i == n
return -1
else
return i
}

这种方法的前提是已经为 x[n] 分配了内存空间。下面的方法将循环展开成 8 次来删除自增。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int ssearch3(t){
x[n] = t;
for(i = 0; ; i += 8){
if (x[i] == t){break}
if (x[i+1] == t){i += 1; break}
if (x[i+2] == t){i += 2; break}
if (x[i+3] == t){i += 3; break}
if (x[i+4] == t){i += 4; break}
if (x[i+5] == t){i += 5; break}
if (x[i+6] == t){i += 6; break}
if (x[i+7] == t){i += 7; break}
}
if i == n
return -1
else
return i
}

将循环展开则有助于避免管道阻塞、减少分支、增加指令级的并行性。

计算球面距离

不使用经纬度来表示点,而是使用 x、y 和 z 坐标表示球面上点的位置。这样的话,距离某点的距离就是三个纬度上差值的平方和。

大手术——二分搜索

下面将对之前的二分搜索进行四次手术,致力于获得一个简单、正确且可维护的程序。

1
2
3
4
5
6
7
8
9
l = 0; u = n -1;
loop
if l > u
p = -1; break;
m = (l + u)/2
case:
x[m] < t: l = m + 1;
x[m] == t: p = m; break;
x[m] > t: u = m -1;

第 1 次手术

如果待搜索的数字出现多次,那么返回结果可能是任意其中一个的位置。并且有时必须比较两次。

1
2
3
4
5
6
7
8
9
10
l = -1; u = n;
while l+1 != u
m = (l + u)/2
if x[m] < t
l = m
else
u = m
p = u
if p >=n || x[p] != t
p = -1

这里是用的左开右闭的判断。

第 2 次手术

不使用 lu 来表示上下限值,而是使用下限 l 以及增量 i 来表示,使得 l + i = u。确保 i 总是 2 的幂。因为数组的大小 n 等于 1000。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
i = 512
l = -1
if x[511] < t
l = 1000 - 512
while i != 1
nexti = i/2
if x[l + nexti] < t
l = l + nexti
i = nexti
else
i = nexti
p = l + 1
if p > 1000 || x[p] != t
p = -1

第 3 次手术

简化第二个 if 语句,删除了变量 nexti,并从循环内的 if 语句中删除了对 nexti 的赋值。

1
2
3
4
5
6
7
8
9
10
11
i = 512
l = -1
if x[511] < t
l = 1000 - 512
while i!=1
i = i/2
if x[l+i] < t
l = l + 1
p = l + 1
if p > 1000 || x[p] != t
p = -1

l 保持不变时,那么 i 不断变小,也就是依次计算 p 的各个位,并且从高位开始计算。

第 4 次手术

展开整个循环,消除循环控制和 i 被 2 除的开销。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
l = -1
if (x[511] < t) l = 1000 - 512
if (x[l + 256] < t) l += 256
if (x[l + 128] < t) l += 128
if (x[l + 64] < t) l += 64
if (x[l + 32] < t) l += 32
if (x[l + 16] < t) l += 16
if (x[l + 8] < t) l += 8
if (x[l + 4] < t) l += 4
if (x[l + 2] < t) l += 2
if (x[l + 1] < t) l += 1
p = l + 1
if p > 1000 || x[p] != t
p = -1

习题

2. 请尝试在你的系统上对其进行性能监视。除非你有一个非常高效的 malloc 函数,否则程序的绝大部分时间可能都会消耗在 malloc 上。请尝试一下通过实现诸如 Van Wyk 那样的结点缓存来减少程序的运行时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdlib>

#define NODESIZE 8
#define NODEGROUP 1000

int nodeleft = 0;
char *freenode;

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

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

1
2
3
4
5
6
7
float arrmax(int n){
if (n == 1){
return x[0];
}else{
return max(x[n-1], arrmax(n-1));
}
}

若 max 为函数,它就可以在几毫秒之内找出具有 n = 10000 个元素的向量中的最大元素。若 max 为如下所示的 C 宏:

1
#define max(a, b)((a)>(b)?(a):(b))

则该算法花 6 秒钟的时间才能找出 n=27 个元素中的最大值,花 12 秒种的时间才能找出 n=28 个元素中的最大值。试给出一个可以反映该糟糕结果的输入,并从数学上分析其运行时间。

「宏」不适合递归调用,「宏」那种按名称调用的语法导致对自身的递归调用超过两次。

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

数组中本来存在待搜索的数,但是二分搜索会找不到。

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

1
if c >= '0' && c <= '9'

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

  1. 第一种方法:统计 1 的位数,然后相加即可。为了统计 1 的个数,又有几种方法。

    • 顺序判断,时间复杂度是 O(n)
    • b &= (b - 1),这样做的话,每次就把 b 的最右的 1 消除了。所以时间复杂度是 O(k),其中 k 是 1 的个数。
    • 建表,然后查询表格即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    int count(unsigned int n) {
    int result = 0;
    while (n > 0) {
    n &= n - 1;
    ++result;
    }
    return result;
    }

    int count2(unsigned int n) {
    unsigned int table[16] = {
    0, 1, 1, 2,
    1, 2, 2, 3,
    1, 2, 2, 3,
    2, 3, 3, 4
    };
    int result = 0;
    while (n > 0) {
    result += table[n & 0xf];
    n >>= 4;
    }
    return result;
    }
  2. 第二种方法:和建表类似,只是先按照输入单元来统计个数,比如先得到 00000001 有几个,00000010 有几个,然后乘上相对应的 1 的个数即可。

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

1
2
3
4
5
6
7
i = 0
while i < n
max = x[i]
x[n] = max
i++
while x[i] < max
i++

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

把所有 5 的倍数的度数都计算好,放入数组中。

12. 人们在调优程序时有时会从数学的角度考虑而不是从代码的角度考虑。为了计算下面的多项式:

y=anxn+an1xn1++a1x1+a0y = a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x^1 + a_0

如下的代码使用了 2n 次乘法。请给出一个更快的函数。

1
2
3
4
5
y = a[0]
xi = 1
for i = [1, n]
xi = x * xi
y = y + a[i] * xi
1
2
3
y = a[n]
for (i = n-1; i>=0; i--)
y = x*y + a[i]