我曾經(jīng)聽一位大師級(jí)的程序員這樣稱贊到，“我通過刪除代碼來實(shí)現(xiàn)功能的提升。”而法國著名作家兼飛行家Antoine de Saint-Exupéry的說法則更具代表性，“只有在不僅沒有任何功能可以添加，而且也沒有任何功能可以刪除的情況下，設(shè)計(jì)師才能夠認(rèn)為自己的工作已臻完美。” 某些時(shí)候，在軟件中根本就不存在最漂亮的代碼，最漂亮的函數(shù)，或者最漂亮的程序。
當(dāng)然，我們很難對(duì)不存在的事物進(jìn)行討論。本章將對(duì)經(jīng)典Quicksort（快速排序）算法的運(yùn)行時(shí)間進(jìn)行全面的分析，并試圖通過這個(gè)分析來說明上述觀點(diǎn)。在第一節(jié)中，我將首先根據(jù)我自己的觀點(diǎn)來回顧一下Quicksort，并為后面的內(nèi)容打下基礎(chǔ)。第二節(jié)的內(nèi)容將是本章的重點(diǎn)部分。我們將首先在程序中增加一個(gè)計(jì)數(shù)器，然后通過不斷地修改，從而使程序的代碼變得越來越短，但程序的功能卻會(huì)變得越來越強(qiáng)，最終的結(jié)果是只需要幾行代碼就可以使算法的運(yùn)行時(shí)間達(dá)到平均水平。在第三節(jié)將對(duì)前面的技術(shù)進(jìn)行小結(jié)，并對(duì)二分搜索樹的運(yùn)行開銷進(jìn)行簡單的分析。最后的兩節(jié)將給出學(xué)完本章得到的一些啟示，這將有助于你在今后寫出更為優(yōu)雅的程序。
3.1 我編寫過的最漂亮代碼
當(dāng)Greg Wilson最初告訴我本書的編寫計(jì)劃時(shí)，我曾自問編寫過的最漂亮的代碼是什么。這個(gè)有趣的問題在我腦海里盤旋了大半天，然后我發(fā)現(xiàn)答案其實(shí)很簡單：Quicksort算法。但遺憾的是，根據(jù)不同的表達(dá)方式，這個(gè)問題有著三種不同的答案。
當(dāng)我撰寫關(guān)于分治（divide-and-conquer）算法的論文時(shí)，我發(fā)現(xiàn)C.A.R. Hoare的Quicksort算法（“Quicksort”，Computer Journal 5）無疑是各種Quicksort算法的鼻祖。這是一種解決基本問題的漂亮算法，可以用優(yōu)雅的代碼實(shí)現(xiàn)。我很喜歡這個(gè)算法，但我總是無法弄明白算法中最內(nèi)層的循環(huán)。我曾經(jīng)花兩天的時(shí)間來調(diào)試一個(gè)使用了這個(gè)循環(huán)的復(fù)雜程序，并且?guī)啄暌詠恚?dāng)我需要完成類似的任務(wù)時(shí)，我會(huì)很小心地復(fù)制這段代碼。雖然這段代碼能夠解決我所遇到的問題，但我卻并沒有真正地理解它。
我后來從Nico Lomuto那里學(xué)到了一種優(yōu)雅的劃分（partitioning）模式，并且最終編寫出了我能夠理解，甚至能夠證明的Quicksort算法。William Strunk Jr.針對(duì)英語所提出的“良好的寫作風(fēng)格即為簡練”這條經(jīng)驗(yàn)同樣適用于代碼的編寫，因此我遵循了他的建議，“省略不必要的字詞”（來自《The Elements of Style》一書）。我最終將大約40行左右的代碼縮減為十幾行的代碼。因此，如果要回答“你曾編寫過的最漂亮代碼是什么？”這個(gè)問題，那么我的答案就是：在我編寫的《Programming Pearls, Second Edition》(Addison-Wesley)一書中給出的Quichsort算法。在示例3-1中給出了用C語言編寫的Quicksort函數(shù)。我們?cè)诮酉聛淼恼鹿?jié)中將進(jìn)一步地研究和改善這個(gè)函數(shù)。
【示例】 3-1 Quicksort函數(shù)
void quicksort(int l, 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);
}
如果函數(shù)的調(diào)用形式是quicksort(0, n-1)，那么這段代碼將對(duì)一個(gè)全局?jǐn)?shù)組x[n]進(jìn)行排序。函數(shù)的兩個(gè)參數(shù)分別是將要進(jìn)行排序的子數(shù)組的下標(biāo)：l是較低的下標(biāo)，而u是較高的下標(biāo)。函數(shù)調(diào)用swap(i,j)將會(huì)交換x[i]與x[j]這兩個(gè)元素。第一次交換操作將會(huì)按照均勻分布的方式在l和u之間隨機(jī)地選擇一個(gè)劃分元素。
在《Programming Pearls》一書中包含了對(duì)Quicksort算法的詳細(xì)推導(dǎo)以及正確性證明。在本章的剩余內(nèi)容中，我將假設(shè)讀者熟悉在《Programming Pearls》中所給出的Quicksort算法以及在大多數(shù)初級(jí)算法教科書中所給出的Quicksort算法。
如果你把問題改為“在你編寫那些廣為應(yīng)用的代碼中，哪一段代碼是最漂亮的？”我的答案還是Quicksort算法。在我和M. D. McIlroy一起編寫的一篇文章（"Engineering a sort function," Software-Practice and Experience, Vol. 23, No. 11）中指出了在原來Unix qsort函數(shù)中的一個(gè)嚴(yán)重的性能問題。隨后，我們開始用C語言編寫一個(gè)新排序函數(shù)庫，并且考慮了許多不同的算法，包括合并排序（Merge Sort）和堆排序（Heap Sort）等算法。在比較了Quicksort的幾種實(shí)現(xiàn)方案后，我們著手創(chuàng)建自己的Quicksort算法。在這篇文章中描述了我們?nèi)绾卧O(shè)計(jì)出一個(gè)比這個(gè)算法的其他實(shí)現(xiàn)要更為清晰，速度更快以及更為健壯的新函數(shù)——部分原因是由于這個(gè)函數(shù)的代碼更為短小。Gordon Bell的名言被證明是正確的：“在計(jì)算機(jī)系統(tǒng)中，那些最廉價(jià)，速度最快以及最為可靠的組件是不存在的。”現(xiàn)在，這個(gè)函數(shù)已經(jīng)被使用了10多年的時(shí)間，并且沒有出現(xiàn)任何故障。
考慮到通過縮減代碼量所得到的好處，我最后以第三種方式來問自己在本章之初提出的問題。“你沒有編寫過的最漂亮代碼是什么？”。我如何使用非常少的代碼來實(shí)現(xiàn)大量的功能？答案還是和Quicksort有關(guān)，特別是對(duì)這個(gè)算法的性能分析。我將在下一節(jié)給出詳細(xì)介紹。
3.2 事倍功半
Quicksort是一種優(yōu)雅的算法，這一點(diǎn)有助于對(duì)這個(gè)算法進(jìn)行細(xì)致的分析。大約在1980年左右，我與Tony Hoare曾經(jīng)討論過Quicksort算法的歷史。他告訴我，當(dāng)他最初開發(fā)出Quicksort時(shí)，他認(rèn)為這種算法太簡單了，不值得發(fā)表，而且直到能夠分析出這種算法的預(yù)期運(yùn)行時(shí)間之后，他才寫出了經(jīng)典的“Quicksoft”論文。
我們很容易看出，在最壞的情況下，Quicksort可能需要n2的時(shí)間來對(duì)數(shù)組元素進(jìn)行排序。而在最優(yōu)的情況下，它將選擇中值作為劃分元素，因此只需nlgn次的比較就可以完成對(duì)數(shù)組的排序。那么，對(duì)于n個(gè)不同值的隨機(jī)數(shù)組來說，這個(gè)算法平均將進(jìn)行多少次比較？
Hoare對(duì)于這個(gè)問題的分析非常漂亮，但不幸的是，其中所使用的數(shù)學(xué)知識(shí)超出了大多數(shù)程序員的理解范圍。當(dāng)我為本科生講授Quicksort算法時(shí)，許多學(xué)生即使在費(fèi)了很大的努力之后，還是無法理解其中的證明過程，這令我非常沮喪。下面，我們將從Hoare的程序開始討論，并且最后將給出一個(gè)與他的證明很接近的分析。
我們的任務(wù)是對(duì)示例3-1中的Quicksort代碼進(jìn)行修改，以分析在對(duì)元素值均不相同的數(shù)組進(jìn)行排序時(shí)平均需要進(jìn)行多少次比較。我們還將努力通過最短的代碼、最短運(yùn)行時(shí)間以及最小存儲(chǔ)空間來得到最深的理解。
為了確定平均比較的次數(shù)，我們首先對(duì)程序進(jìn)行修改以統(tǒng)計(jì)次數(shù)。因此，在內(nèi)部循環(huán)進(jìn)行比較之前，我們將增加變量comps的值（參見示例3-2）。
【示例3-2】 修改Quicksort的內(nèi)部循環(huán)以統(tǒng)計(jì)比較次數(shù)。
for (i = l+1; i <= u; i++) {
comps++;
if (x[i] < x[l])
swap(++m, i);
}
如果用一個(gè)值n來運(yùn)行程序，我們將會(huì)看到在程序的運(yùn)行過程中總共進(jìn)行了多少次比較。如果重復(fù)用n來運(yùn)行程序，并且用統(tǒng)計(jì)的方法來分析結(jié)果，我們將得到Quicksort在對(duì)n個(gè)元素進(jìn)行排序時(shí)平均使用了1.4 nlgn次的比較。
在理解程序的行為上，這是一種不錯(cuò)的方法。通過十三行的代碼和一些實(shí)驗(yàn)可以反應(yīng)出許多問題。這里，我們引用作家Blaise Pascal和T. S. Eliot的話，“如果我有更多的時(shí)間，那么我給你寫的信就會(huì)更短。”現(xiàn)在，我們有充足的時(shí)間，因此就讓我們來對(duì)代碼進(jìn)行修改，并且努力編寫出更短（同時(shí)更好）的程序。
我們要做的事情就是提高這個(gè)算法的速度，并且盡量增加統(tǒng)計(jì)的精確度以及對(duì)程序的理解。由于內(nèi)部循環(huán)總是會(huì)執(zhí)行u-l次比較，因此我們可以通過在循環(huán)外部增加一個(gè)簡單的操作來統(tǒng)計(jì)比較次數(shù)，這就可以使程序運(yùn)行得更快一些。在示例3-3的Quicksort算法中給出了這個(gè)修改。
【示例3-3】 Quicksort的內(nèi)部循環(huán)，將遞增操作移到循環(huán)的外部
comps += u-l;
for (i = l+1; i <= u; i++)
if (x[i] < x[l])
swap(++m, i);
這個(gè)程序會(huì)對(duì)一個(gè)數(shù)組進(jìn)行排序，同時(shí)統(tǒng)計(jì)比較的次數(shù)。不過，如果我們的目標(biāo)只是統(tǒng)計(jì)比較的次數(shù)，那么就不需要對(duì)數(shù)組進(jìn)行實(shí)際地排序。在示例3-4中去掉了對(duì)元素進(jìn)行排序的“實(shí)際操作”，而只是保留了程序中各種函數(shù)調(diào)用的“框架”。
【示例3-4】將Quicksort算法的框架縮減為只進(jìn)行統(tǒng)計(jì)
void quickcount(int l, int u)
{ int m;
if (l >= u) return;
m = randint(l, u);
comps += u-l;
quickcount(l, m-1);
quickcount(m+1, u);
}
這個(gè)程序能夠?qū)崿F(xiàn)我們的需求，因?yàn)?span>Quichsort在選擇劃分元素時(shí)采用的是“隨機(jī)”方式，并且我們假設(shè)所有的元素都是不相等的。現(xiàn)在，這個(gè)新程序的運(yùn)行時(shí)間與n成正比，并且相對(duì)于示例3-3需要的存儲(chǔ)空間與n成正比來說，現(xiàn)在所需的存儲(chǔ)空間縮減為遞歸堆棧的大小，即存儲(chǔ)空間的平均大小與lgn成正比。
雖然在實(shí)際的程序中，數(shù)組的下標(biāo)（l和u）是非常重要的，但在這個(gè)框架版本中并不重要。因此，我們可以用一個(gè)表示子數(shù)組大小的整數(shù)(n)來替代這兩個(gè)下標(biāo)（參見示例3-5）
【示例3-5】 在Quicksort代碼框架中使用一個(gè)表示子數(shù)組大小的參數(shù)
void qc(int n)
{ int m;
if (n <= 1) return;
m = randint(1, n);
comps += n-1;
qc(m-1);
qc(n-m);
}
現(xiàn)在，我們可以很自然地把這個(gè)過程整理為一個(gè)統(tǒng)計(jì)比較次數(shù)的函數(shù)，這個(gè)函數(shù)將返回在隨機(jī)Quicksort算法中的比較次數(shù)。在示例3-6中給出了這個(gè)函數(shù)。
【示例3-6】 將Quicksort框架實(shí)現(xiàn)為一個(gè)函數(shù)
int cc(int n)
{ int m;
if (n <= 1) return 0;
m = randint(1, n);
return n-1 + cc(m-1) + cc(n-m);
}
在示例3-4、示例3-5和示例3-6中解決的都是相同的基本問題，并且所需的都是相同的運(yùn)行時(shí)間和存儲(chǔ)空間。在后面的每個(gè)示例都對(duì)這些函數(shù)的形式進(jìn)行了改進(jìn)，從而比這些函數(shù)更為清晰和簡潔。
在定義發(fā)明家的矛盾（inventor's paradox）(How To Solve It, Princeton University Press)時(shí)，George Póllya指出“計(jì)劃越宏大，成功的可能性就越大。”現(xiàn)在，我們就來研究在分析Quicksort時(shí)的矛盾。到目前為止，我們遇到的問題是，“當(dāng)Quicksort對(duì)大小為n的數(shù)組進(jìn)行一次排序時(shí)，需要進(jìn)行多少次比較？”我們現(xiàn)在將對(duì)這個(gè)問題進(jìn)行擴(kuò)展，“對(duì)于大小為n的隨機(jī)數(shù)組來說，Quichsort算法平均需要進(jìn)行多少次的比較？”我們通過對(duì)示例3-6進(jìn)行擴(kuò)展以引出示例3-7。
【示例3-7】 偽碼：Quicksort的平均比較次數(shù)
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
如果在輸入的數(shù)組中最多只有一個(gè)元素，那么Quichsort將不會(huì)進(jìn)行比較，如示例3-6中所示。對(duì)于更大的n，這段代碼將考慮每個(gè)劃分值m（從第一個(gè)元素到最后一個(gè)，每個(gè)都是等可能的）并且確定在這個(gè)元素的位置上進(jìn)行劃分的運(yùn)行開銷。然后，這段代碼將統(tǒng)計(jì)這些開銷的總和（這樣就遞歸地解決了一個(gè)大小為m-1的問題和一個(gè)大小為n-m的問題），然后將總和除以n得到平均值并返回這個(gè)結(jié)果。
如果我們能夠計(jì)算這個(gè)數(shù)值，那么將使我們實(shí)驗(yàn)的功能更加強(qiáng)大。我們現(xiàn)在無需對(duì)一個(gè)n值運(yùn)行多次來估計(jì)平均值，而只需一個(gè)簡單的實(shí)驗(yàn)便可以得到真實(shí)的平均值。不幸的是，實(shí)現(xiàn)這個(gè)功能是要付出代價(jià)的：這個(gè)程序的運(yùn)行時(shí)間正比于3n（如果是自行參考（self-referential）的，那么用本章中給出的技術(shù)來分析運(yùn)行時(shí)間將是一個(gè)很有趣的練習(xí)）。
示例3-7中的代碼需要一定的時(shí)間開銷，因?yàn)樗貜?fù)計(jì)算了中間結(jié)果。當(dāng)在程序中出現(xiàn)這種情況時(shí)，我們通常會(huì)使用動(dòng)態(tài)編程來存儲(chǔ)中間結(jié)果，從而避免重復(fù)計(jì)算。因此，我們將定義一個(gè)表t[N+1]，其中在t[n]中存儲(chǔ)c[n]，并且按照升序來計(jì)算它的值。我們將用N來表示n的最大值，也就是進(jìn)行排序的數(shù)組的大小。在示例3-8中給出了修改后的代碼。
【示例3-8】 在Quicksort中使用動(dòng)態(tài)編程來計(jì)算
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
這個(gè)程序只對(duì)示例3-7進(jìn)行了細(xì)微的修改，即用t[n]來替換c(n)。它的運(yùn)行時(shí)間將正比于N2，并且所需的存儲(chǔ)空間正比于N。這個(gè)程序的優(yōu)點(diǎn)之一就是：在程序執(zhí)行結(jié)束時(shí)，數(shù)組t中將包含數(shù)組中從元素0到元素N的真實(shí)平均值（而不是樣本均值的估計(jì)）。我們可以對(duì)這些值進(jìn)行分析，從而生成在Quichsort算法中統(tǒng)計(jì)比較次數(shù)的計(jì)算公式。
我們現(xiàn)在來對(duì)程序做進(jìn)一步的簡化。第一步就是把n-1移到循環(huán)的外面，如示例3-9所示。
【示例3-9】 在Quicksort中把代碼移到循環(huán)外面來計(jì)算
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
現(xiàn)在將利用對(duì)稱性來對(duì)循環(huán)做進(jìn)一步的調(diào)整。例如，當(dāng)n為4時(shí)，內(nèi)部循環(huán)計(jì)算總和為：
t[0]+t[3] + t[1]+t[2] + t[2]+t[1] + t[3]+t[0]
在上面這些組對(duì)中，第一個(gè)元素增加而第二個(gè)元素減少。因此，我們可以把總和改寫為：
2 * (t[0] + t[1] + t[2] + t[3])
我們可以利用這種對(duì)稱性來得到示例3-10中的Quicksort。
【示例3-10】 在Quichsort中利用了對(duì)稱性來計(jì)算
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
然而，在這段代碼的運(yùn)行時(shí)間中同樣存在著浪費(fèi)，因?yàn)樗貜?fù)地計(jì)算了相同的總和。此時(shí)，我們不是把前面所有的元素加在一起，而是在循環(huán)外部初始化總和并且加上下一個(gè)元素，如示例3-11所示。
【示例3-11】 在Quicksort中刪除了內(nèi)部循環(huán)來計(jì)算
sum = 0; t[0] = 0
for (n = 1; n <= N; n++)
sum += 2*t[n-1]
t[n] = n-1 + sum/n
這個(gè)小程序確實(shí)很有用。程序的運(yùn)行時(shí)間與N成正比，對(duì)于每個(gè)從1到N的整數(shù)，程序?qū)⑸梢粡?span>Quicksort的估計(jì)運(yùn)行時(shí)間表。
我們可以很容易地把示例3-11用表格來實(shí)現(xiàn)，其中的值可以立即用于進(jìn)一步的分析。在3-1給出了最初的結(jié)果行。
表3-1 示例3-11中實(shí)現(xiàn)的表格輸出
N Sum t[n]
0 0 0
1 0 0
2 0 1
3 2 2.667
4 7.333 4.833
5 17 7.4
6 31.8 10.3
7 52.4 13.486
8 79.371 16.921
這張表中的第一行數(shù)字是用代碼中的三個(gè)常量來進(jìn)行初始化的。下一行（輸出的第三行）的數(shù)值是通過以下公式來計(jì)算的：
A3 = A2+1 B3 = B2 + 2*C2 C3 = A3-1 + B3/A3
把這些（相應(yīng)的）公式記錄下來就使得這張表格變得完整了。這張表格是“我曾經(jīng)編寫的最漂亮代碼”的很好的證據(jù)，即使用少量的代碼完成大量的工作。
但是，如果我們不需要所有的值，那么情況將會(huì)是什么樣？如果我們更希望通過這種來方式分析一部分?jǐn)?shù)值（例如，在20到232之間所有2的指數(shù)值）呢？雖然在示例3-11中構(gòu)建了完整的表格t，但它只需要使用表格中的最新值。因此，我們可以用變量t的定長空間來替代table t[]的線性空間，如示例3-12所示。
【示例3-12】 Quicksoft 計(jì)算——最終版本
sum = 0; t = 0
for (n = 1; n <= N; n++)
sum += 2*t
t = n-1 + sum/n
然后，我們可以插入一行代碼來測試n的適應(yīng)性，并且在必要時(shí)輸出這些結(jié)果。
這個(gè)程序是我們漫長學(xué)習(xí)旅途的終點(diǎn)。通過本章所采用的方式，我們可以證明Alan Perlis的經(jīng)驗(yàn)是正確的：“簡單性并不是在復(fù)雜性之前，而是在復(fù)雜性之后” ("Epigrams on Programming," Sigplan Notices, Vol. 17, Issue 9)。
3.3 觀點(diǎn)
在表3-2中總結(jié)了本章中對(duì)Quicksort進(jìn)行分析的程序。
表 3-2 對(duì)Quicksort比較次數(shù)的統(tǒng)計(jì)算法的評(píng)價(jià)
| 示例編號(hào) | 代碼行數(shù) | 答案類型 | 答案數(shù)量 | 運(yùn)行時(shí)間 | 空間 |
| 2 | 13 | Sample | 1 | n l g n | N |
| 3 | 13 | " | " | " | " |
| 4 | 8 | " | " | n | lgn |
| 5 | 8 | " | " | " | " |
| 6 | 6 | " | " | " | " |
| 7 | 6 | Exact | " | 3N | N |
| 8 | 6 | " | N | N2 | N |
| 9 | 6 | " | " | " | " |
| 10 | 6 | " | " | " | " |
| 11 | 4 | " | " | N | " |
| 12 | 4 | Exact | N | N | 1 |
在我們對(duì)代碼的每次修改中，每個(gè)步驟都是很直接的；不過，從示例3-6中樣本值到示例3-7中準(zhǔn)確值的過渡過程可能是最微妙的。隨著這種方式進(jìn)行下去，代碼變得更快和更有用，而代碼量同樣得到了縮減。在19世紀(jì)中期，Robert Browning指出“少即是多（less is more）”，而這張表格正是一個(gè)證明這種極少主義哲學(xué)（minimalist philosophy）的實(shí)例。
我們已經(jīng)看到了三種截然不同的類型的程序。示例3-2和示例3-3是能夠?qū)嶋H使用的Quicksort，可以用來在對(duì)真實(shí)數(shù)組進(jìn)行排序時(shí)統(tǒng)計(jì)比較次數(shù)。示例3-4到示例3-6都實(shí)現(xiàn)了Quicksort的一種簡單模型：它們模擬算法的運(yùn)行，而實(shí)際上卻沒有做任何排序工作。從示例3-7到示例3-12則實(shí)現(xiàn)了一種更為復(fù)雜的模型：它們計(jì)算了比較次數(shù)的真實(shí)平均值而沒有跟蹤任何單次的運(yùn)行。
我們?cè)谙旅婵偨Y(jié)了實(shí)現(xiàn)每個(gè)程序所使用的技術(shù)：
* 示例3-2，示例3-4，3-7:對(duì)問題的定義進(jìn)行根本的修改。
* 示例3-5，示例3-6，3-12：對(duì)函數(shù)的定義進(jìn)行輕微的修改
* 示例3-8：實(shí)現(xiàn)動(dòng)態(tài)編程的新數(shù)據(jù)結(jié)構(gòu)
這些技術(shù)都是非常典型的。我們?cè)诤喕绦驎r(shí)經(jīng)常要發(fā)出這樣的疑問，“我們真正要解決的問題是什么？”或者是，“有沒有更好的函數(shù)來解決這個(gè)問題？”
當(dāng)我把這個(gè)分析過程講授給本科生時(shí)，這個(gè)程序最終被縮減成零行代碼，化為一陣數(shù)學(xué)的輕煙消失了。我們可以把示例3-7重新解釋為以下的循環(huán)關(guān)系：
這正是Hoare所采用的方法，并且后來由D.E.Knuth在他經(jīng)典的《The Art of Computer Programming》（Addison-Wesley）一書的第三卷：排序與查找中給出的方法中給出了描述。通過重新表達(dá)編程思想的技巧和在示例3-10中使用的對(duì)稱性，使我們可以把遞歸部分簡化為：
Knuth刪除了求和符號(hào)，從而引出了示例3-11，這可以被重新表達(dá)為一個(gè)在兩個(gè)未知量之間有著兩種循環(huán)關(guān)系的系統(tǒng)：
Knuth使用了“求和因子”的數(shù)學(xué)方法來實(shí)現(xiàn)這種解決方案：
其中 表示第n個(gè)調(diào)和數(shù)（harmonic number），即1 + 1/2 + 1/3 + … 1/n。這樣，我們就從對(duì)程序不斷進(jìn)行修改以得到實(shí)驗(yàn)數(shù)據(jù)順利地過渡到了對(duì)程序行為進(jìn)行完全的數(shù)學(xué)分析。
在得到這個(gè)公式之后，我們就可以結(jié)束我們的討論。我們已經(jīng)遵循了Einstein的著名建議：“盡量使每件事情變得簡單，并且直到不可能再簡單為止。”
附加分析
Goethe的著名格言是：“建筑是靜止的音樂”。按照這種說法，我可以說“數(shù)據(jù)結(jié)構(gòu)是靜止的算法。”如果我們固定了Quichsort算法，那么就將得到了一個(gè)二分搜索樹的數(shù)據(jù)結(jié)構(gòu)。在Knuth發(fā)表的文章中給出了這個(gè)結(jié)構(gòu)并且采用類似于在Quichsort中的循環(huán)關(guān)系來分析它的運(yùn)行時(shí)間。
如果要分析把一個(gè)元素插入到二分搜索樹中的平均開銷，那么我們可以以這段代碼作為起點(diǎn)，并且對(duì)這段代碼進(jìn)行擴(kuò)展來統(tǒng)計(jì)比較次數(shù)，然后在我們收集的數(shù)據(jù)上進(jìn)行實(shí)驗(yàn)。接下來，我們可以仿照前面章節(jié)中的方式來簡化代碼。一個(gè)更為簡單的解決方案就是定義一個(gè)新的Quichsort，在這個(gè)算法中使用理想的劃分算法把有著相同關(guān)聯(lián)順序的元素劃分到兩邊。Quichsort和二分搜索樹是同構(gòu)的，如圖3-1所示。
圖3-1 實(shí)現(xiàn)理想劃分的Quicksort以及相應(yīng)的二分搜索樹
左邊的方框給出了正在進(jìn)行中的理想劃分的Quicksort，右邊的圖則給出了相應(yīng)的從相同輸入中構(gòu)建起來的二分搜索樹。這兩個(gè)過程不僅需要進(jìn)行相同次數(shù)的比較，而且還將生成相同的比較集合。通過在前面對(duì)于在一組不同元素上進(jìn)行Quicksort實(shí)驗(yàn)的平均性能分析，我們就可以得到將不同的元素隨機(jī)插入到二分搜索樹中的平均比較次數(shù)。
3.4 本章的中心思想是什么？
表面上看來，我“所寫的”內(nèi)容就是從示例3-2到示例3-12的程序。我最初是漫不經(jīng)心地編寫這些程序，然后將這些程序?qū)懺诮o本科生講課的黑板上，并且最終寫到本章中。我有條不紊地進(jìn)行著這些程序的修改，并且花了大量的時(shí)間來分析這些程序，從而確信它們都是正確的。然而，除了在示例3-11中實(shí)現(xiàn)的表格外，我從來沒有把任何一個(gè)示例作為計(jì)算機(jī)程序運(yùn)行過。
我在貝爾實(shí)驗(yàn)室呆了將近二十年，我從許多教師（尤其是Brian Kernighan，他所編寫的編程內(nèi)容作為本書的第1章）那里學(xué)到了：要“編寫”一個(gè)在大眾面前展示的程序，所涉及到的東西比鍵入這個(gè)程序要多得多。有人用代碼實(shí)現(xiàn)了這個(gè)程序，最初運(yùn)行在一些測試示例中，然后構(gòu)建了完整的系統(tǒng)框架、驅(qū)動(dòng)程序以及一個(gè)案例庫來支撐這段代碼。理想的情況是，人們可以手動(dòng)地把編譯后的代碼包含到文本中，不加入任何的人為干涉。基于這種想法，我編寫了示例3-1（以及在《Programming Pearls》中的所有代碼）。
為了維護(hù)面子，我希望永遠(yuǎn)都不要實(shí)現(xiàn)從示例3-2到示例3-12的代碼，從而使我保持誠實(shí)的名聲。然而，在計(jì)算機(jī)編程中的近四十年的實(shí)踐使我對(duì)這個(gè)任務(wù)的困難性有著深深的敬畏（好吧，更準(zhǔn)確地說，是對(duì)于錯(cuò)誤的害怕）。我妥協(xié)了，把示例3-11用表格方式實(shí)現(xiàn)出來，并且無意中得到了一個(gè)完備的解答。當(dāng)這兩個(gè)東西完美地匹配在一起時(shí)，你可以想象一下我當(dāng)時(shí)的喜悅吧！因此，我向世界提供了這些漂亮的并且未曾實(shí)現(xiàn)的程序，雖然在這些程序中可能會(huì)有一些還未發(fā)現(xiàn)的錯(cuò)誤，但我對(duì)這些程序的正確性還是有一定信心的。我希望一些細(xì)微的錯(cuò)誤不會(huì)掩蓋我在這些程序中所展示的那些漂亮思想。
當(dāng)我為給出這些沒有被實(shí)現(xiàn)過的程序感到不安時(shí)，Alan Perlis的話安慰了我，他說“軟件是不是不像任何一個(gè)事物，它就是意味著被拋棄：軟件的所有意義就是把它看作為一個(gè)肥皂泡？”
3.5 結(jié)論
漂亮的含義有著許多來源。本章通過簡化、優(yōu)雅以及精簡來刻畫了漂亮的含義。下面這些名言表達(dá)的是同樣的意思：
* 通過刪除代碼來實(shí)現(xiàn)功能的提升。
* 只有在不僅沒有任何功能可以添加，而且也沒有任何功能可以刪除的情況下，設(shè)計(jì)師才能夠認(rèn)為自己的工作已臻完美。
* 有時(shí)候，在軟件中根本就不存在最漂亮的代碼，最漂亮的函數(shù)，或者最漂亮的程序。
* 良好的寫作風(fēng)格即為簡練。省略不必要的字詞。 (Strunk and White)
* 在計(jì)算機(jī)系統(tǒng)中，那些最廉價(jià)、速度最快以及最為可靠的組件是不存在的（Bell）
* 努力做到事倍功半。
* 如果我有更多的時(shí)間，那么我給你寫的信就會(huì)越短（Pascal）
* 發(fā)明家的矛盾：計(jì)劃越宏大，成功的可能性就越大。（Pólya）
* 簡單性并不是在復(fù)雜性之前，而是在復(fù)雜性之后（Perlis）
* 少即是多。（Browning）
* 盡量使每件事情變得簡單，并且直到不可能再簡單為止（Einstein）
* 軟件有時(shí)候應(yīng)該被視作為一個(gè)肥皂泡（Perlis）
* 在簡單中尋找漂亮。
本章的內(nèi)容到此結(jié)束。讀者可以復(fù)習(xí)所學(xué)到的內(nèi)容并進(jìn)行模擬實(shí)驗(yàn)。
對(duì)于那些想要得到更具體信息的人們，我在下面給出了一些觀點(diǎn)，這些觀點(diǎn)分為三類
程序分析
深入理解程序行為的方式之一就是修改這個(gè)程序，然后在具有代表性的數(shù)據(jù)上運(yùn)行這個(gè)程序，就像示例3-2那樣。不過，我們通常會(huì)更關(guān)心程序的某個(gè)方面而不是程序的整體。例如，我們只是考慮Quichsort所使用的平均比較次數(shù)，而忽略了其他的方面。Sedgewick ("The analysis of Quicksort programs," Acta Informatica, Vol. 7)研究了Quichsort的其他特性，例如算法所需的存儲(chǔ)空間以及各種Quicksort運(yùn)行時(shí)間的其他方面。我們可以關(guān)注這些關(guān)鍵問題，而暫時(shí)）忽略了程序其他不太重要的方面。在我的一篇文章"A Case Study in Applied Algorithm Design" (IEEE Computer, Vol. 17, No. 2)中指出了我曾經(jīng)遇到過的一個(gè)問題：對(duì)在單元空間中找出貨郎行走路線的strip啟發(fā)式算法的性能進(jìn)行評(píng)價(jià)。我估計(jì)完成這個(gè)任務(wù)所要的程序大概在100行代碼左右。在經(jīng)歷了一系列類似于本章前面看到的分析步驟之后，我只使用了十幾行代碼的模擬算法就實(shí)現(xiàn)了更為精確的效果（在我寫完了這個(gè)模擬算法后，我發(fā)現(xiàn)Beardwood 等人["The Shortest Path Through Many Points," Proc. Cambridge Philosophical Soc., Vol. 55]已經(jīng)更完整地表述了我的模擬算法，因此已經(jīng)在二十幾年前就從數(shù)學(xué)上解決了這個(gè)問題）。
小段代碼
我相信計(jì)算機(jī)編程是一項(xiàng)實(shí)踐性的技術(shù)，并且我也同意這個(gè)觀點(diǎn)：“任何技術(shù)都必須通過模仿和實(shí)踐來掌握。” 因此，想要編寫漂亮代碼的程序員應(yīng)該閱讀一些漂亮的程序以及在編寫程序時(shí)模仿所學(xué)到的技術(shù)。我發(fā)現(xiàn)在實(shí)踐時(shí)有個(gè)非常有用的東西就是小段代碼，也就是一二十行的代碼。編寫《Programming Pearls》這本書是一件艱苦的工作，但同時(shí)也有著極大的樂趣。我實(shí)現(xiàn)了每一小段代碼，并且親自把每段代碼都分解為基本的知識(shí)。我希望其他人在閱讀這些代碼時(shí)與我在編寫這些代碼時(shí)有著同樣的享受過程。
軟件系統(tǒng)
為了有針對(duì)性，我極其詳盡地描述了一個(gè)小型任務(wù)。我相信其中的這些準(zhǔn)則不僅存在于小型程序中，它們同樣也適用于大型的程序以及計(jì)算機(jī)系統(tǒng)。Parnas（"Designing software for ease of extension and contraction," IEEE T. Software Engineering, Vol. 5, No. 2）給出了把一個(gè)系統(tǒng)拆分為基本構(gòu)件的技術(shù)。為了得用快速的應(yīng)用性，不要忘了Tom Duff的名言：“在盡可能的情況下，利用現(xiàn)有的代碼。”
3.6 致謝
非常感謝Dan Bentley, Brian Kernighan, Andy Oram和David Weiss卓有見識(shí)的評(píng)語。