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