《代码之美》（三）－－我从未编写过的最漂亮的代码

Jon Bentley

有位大师说过：“我通过删除代码来实现功能的提升。”另一种更具代表性的说法是“只有在不仅没有任何功能可以添加，而且没有任何功能可以删除的情况下，设计师才能够认为自己的工作已臻完美。”

Jon在本章介绍了如何一步步精化一个分析“快速排序法”性能的小程序。

快速排序法由Tony Hoare发明，下面是它的一个典型的实现：

void quicksort(int i, int u)
{
    int i, m;
    if (l >= u) return;
    swap(l, randint(l, u));
    m = l;
    for (i = l+1; i <=u; i++)
        if (x[i] < x[l])
            swap(++m, i);
    swap(l, m);
    quicksort(l, m-1);
    quicksort(m+1, u);
}

（博主：如有需要可参考博客 算法导论）

 

“比较次数”可以作为用于衡量一个算法的性能。Jon通过在上面代码中的内循环加入一个计数器comps来得到总的比较次数：

for (i = l+1; i <= u; i++)  {
    comps++;
    if (x[i] < x[l])
        swap(++m, i);
}

可以发现这个计数器的递增操作可以移到循环的外部：

comps += u-l;
for (i = l+1; i <= u; i++)
    if (x[i] < x[l])
        swap(++m, i);

由于我们只关注于比较次数，所以把真正的排序部分从代码中移除：

void quickcount(int l, int u)
{
    int m;
    if (l >= u) return;
    m = randint(l, u);
    comps += u-1;
    quickcount(l, m-1);
    quickcount(m+1, u);
}

注意到，在真实的排序过程中，数组的下标是很重要的，但对于统计比较次数来说，下标并不是如此重要，所以可以改进代码：

void qc(int n)
{
    int m;
    if (n <= 1) return;
    m = randint(1, n);
    comps += n-1;
    qc(m-1);
    qc(n-m);
}

继续精化上面的代码，移除comps：

void cc(int n)
{
    int m;
    if (n <= 1) return;
    m = randint(1, n);
    return n-1 + cc(m-1) + cc(n-m);
}

上面得到的函数已经非常清晰简洁，但是它依赖于随机数来分析某一种特定的情况。我们希望有一个更全面分析，就是对快速排序法中，所有情况中的比较次数的一个平均值。为此，我们改写统计函数：

float c(int n)
{
    if (n <= 1) return 0;
    sum = 0;
    for (m = 1; m <= n; m++)
        sum += n-1 + c(m-1) + c(n-m);
    return sum/n;
}

上面函数的运行时间为O(3^n)（3的n次方），而且其中有大量的重复运算：比如c(n-2)在c(n-1)和c(n)中都被重新计算了，所以我们可以使用一个数组来存放这些中间结果：

t[0] = 0;
for (n = 1; n <= N; n++) {
    sum = 0;
    for (i = 1; i <= n; i++)
        sum += n-1 + t[i-1] + t[n-i];
    t[n] = sum/n;
}

这样运行时间就变为O(N^2)，而存储究间为O(N)。我们可以进一步简化，把上面的n-1移到循环外：

t[0] = 0;
for (n = 1; n <= N; n++) {
    sum = 0;
    for (i = 1; i <= n; i++)
        sum += t[i-1] + t[n-i];
    t[n] = n-1 + sum/n;
}

又可以发现t[i-1]和t[n-i]是对称的：当n=4时，内循环的总和为t[0]+t[3] + t[1]+t[2] + t[2]+t[1] + t[3]+t[0] = 2 * (t[0]+t[1]+t[2]+t[3])。利用这种对称性，我们改写上面的代码：

t[0] = 0;
for (n = 1; n <= N; n++) {
    sum = 0;
    for (i = 0; i < n; i++)
        sum += 2 * t[i];
    t[n] = n-1 + sum/n;
}

上面的代码的内循环时重复计算着相同的总和值，所以我们删掉内循环：

sum = 0; t[0] = 0;
for (n = 1; n <= N; n++) {
    sum += 2*t[n-1];
    t[n] = n-1 + sum/n;
}

这样运行时间为O(N)，而空间仍为O(N)。如果我们并不想记录所有的中间结果，那么我们可以删除数组，得到最终版本：

sum = 0; t = 0;
for (n = 1; n <= N; n++) {
    sum += 2*t;
    t = n-1 + sum/n;
}

如此简短的代码，竟做了如此多的事情，这是Jon眼中的漂亮的代码。但事情还没有结束，我们要解决的问题，如果用数学公式来表达，则如下：
C_0 = 0
C_n = (n-1) + (1/n) * ∑<1≤i≤n> (C_(i-1) + C_(n-i))

根据对称性可得：
C_n = n-1 + (2/n) * ∑<0≤i≤n-1> C_i

删除上面的求和符号：
C_0 = 0    S_0 = 0    S_n = S_(n-1) + 2*C_(n-1)    C_n = n-1 + S_n / n

使用“求和因子（summing factor）”解得：
C_n = (n+1) * (2*H_(n+1) - 2) - 2*n ≈ 1.386*n*lg(n) （其中H_n表示第n个调和数（harmonic number），即1+1/2+1/3+...1/n）|
（上面的公式由D.E.Knuth在其经典作《The Art of Computer Programming》第三卷描述。）

至此，计算机程序最后简化成了一个数学公式，这便是Jon所谓的“从未写出的最好代码”。

：世界著名计算机科学家，被誉为实践探索先锋，影响算法发展的十位大师之一。代表作有ProgrammingPearls(《编程珠玑》)等。