第3章我編寫過的最漂亮的代碼

1、第3章 我編寫過的最漂亮的代碼Jon Bentley我曾經(jīng)聽一位大師級的程序員這樣稱贊到，“我通過刪除代碼來實(shí)現(xiàn)功能的提升?！倍▏骷壹骘w行家Antoine de Saint-Exupéry的說法則更具代表性，“只有在不僅沒有任何功能可以添加，而且也沒有任何功能可以刪除的情況下，設(shè)計師才能夠認(rèn)為自己的工作已臻完美?！?某些時候，在軟件中根本就不存在最漂亮的代碼，最漂亮的函數(shù)，或者最漂亮的程序。 當(dāng)然，我們很難對不存在的事物進(jìn)行討論。本章將對經(jīng)典Quicksort（快速排序）算法的運(yùn)行時間進(jìn)行全面的分析，并試圖通過這個分析來說明上述觀點(diǎn)。在第一節(jié)中，我將首先根據(jù)我自己的觀點(diǎn)來回顧

2、一下Quicksort，并為后面的內(nèi)容打下基礎(chǔ)。第二節(jié)的內(nèi)容將是本章的重點(diǎn)部分。我們將首先在程序中增加一個計數(shù)器，然后通過不斷地修改，從而使程序的代碼變得越來越短，但程序的功能卻會變得越來越強(qiáng)，最終的結(jié)果是只需要幾行代碼就可以使算法的運(yùn)行時間達(dá)到平均水平。在第三節(jié)將對前面的技術(shù)進(jìn)行小結(jié)，并對二分搜索樹的運(yùn)行開銷進(jìn)行簡單的分析。最后的兩節(jié)將給出學(xué)完本章得到的一些啟示，這將有助于你在今后寫出更為優(yōu)雅的程序。3.1 我編寫過的最漂亮代碼 當(dāng)Greg Wilson最初告訴我本書的編寫計劃時，我曾自問編寫過的最漂亮的代碼是什么。這個有趣的問題在我腦海里盤旋了大半天，然后我發(fā)現(xiàn)答案其實(shí)很簡單：Quicks

3、ort算法。但遺憾的是，根據(jù)不同的表達(dá)方式，這個問題有著三種不同的答案。 當(dāng)我撰寫關(guān)于分治（divide-and-conquer）算法的論文時，我發(fā)現(xiàn)C.A.R. Hoare的Quicksort算法（“Quicksort”，Computer Journal 5）無疑是各種Quicksort算法的鼻祖。這是一種解決基本問題的漂亮算法，可以用優(yōu)雅的代碼實(shí)現(xiàn)。我很喜歡這個算法，但我總是無法弄明白算法中最內(nèi)層的循環(huán)。我曾經(jīng)花兩天的時間來調(diào)試一個使用了這個循環(huán)的復(fù)雜程序，并且?guī)啄暌詠恚?dāng)我需要完成類似的任務(wù)時，我會很小心地復(fù)制這段代碼。雖然這段代碼能夠解決我所遇到的問題，但我卻并沒有真正地理解它。 我后

4、來從Nico Lomuto那里學(xué)到了一種優(yōu)雅的劃分（partitioning）模式，并且最終編寫出了我能夠理解，甚至能夠證明的Quicksort算法。William Strunk Jr.針對英語所提出的“良好的寫作風(fēng)格即為簡練”這條經(jīng)驗(yàn)同樣適用于代碼的編寫，因此我遵循了他的建議，“省略不必要的字詞”（來自The Elements of Style一書）。我最終將大約40行左右的代碼縮減為十幾行的代碼。因此，如果要回答“你曾編寫過的最漂亮代碼是什么？”這個問題，那么我的答案就是：在我編寫的Programming Pearls, Second Edition(Addison-Wesley)一書中給

5、出的Quichsort算法。在示例3-1中給出了用C語言編寫的Quicksort函數(shù)。我們在接下來的章節(jié)中將進(jìn)一步地研究和改善這個函數(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 (xi < xl) swap(+m, i); swap(l, m); quicksort(l, m-1); quicksort(m+1, u); 如果函數(shù)的調(diào)用形式是qu

6、icksort(0, n-1)，那么這段代碼將對一個全局?jǐn)?shù)組xn進(jìn)行排序。函數(shù)的兩個參數(shù)分別是將要進(jìn)行排序的子數(shù)組的下標(biāo)：l是較低的下標(biāo)，而u是較高的下標(biāo)。函數(shù)調(diào)用swap(i,j)將會交換xi與xj這兩個元素。第一次交換操作將會按照均勻分布的方式在l和u之間隨機(jī)地選擇一個劃分元素。 在Programming Pearls一書中包含了對Quicksort算法的詳細(xì)推導(dǎo)以及正確性證明。在本章的剩余內(nèi)容中，我將假設(shè)讀者熟悉在Programming Pearls中所給出的Quicksort算法以及在大多數(shù)初級算法教科書中所給出的Quicksort算法。如果你把問題改為“在你編寫那些廣為應(yīng)用的代碼中，

7、哪一段代碼是最漂亮的？”我的答案還是Quicksort算法。在我和M. D. McIlroy一起編寫的一篇文章（"Engineering a sort function," Software-Practice and Experience, Vol. 23, No. 11）中指出了在原來Unix qsort函數(shù)中的一個嚴(yán)重的性能問題。隨后，我們開始用C語言編寫一個新排序函數(shù)庫，并且考慮了許多不同的算法，包括合并排序（Merge Sort）和堆排序（Heap Sort）等算法。在比較了Quicksort的幾種實(shí)現(xiàn)方案后，我們著手創(chuàng)建自己的Quicksort算法。在這篇文章中描

8、述了我們?nèi)绾卧O(shè)計出一個比這個算法的其他實(shí)現(xiàn)要更為清晰，速度更快以及更為健壯的新函數(shù)部分原因是由于這個函數(shù)的代碼更為短小。Gordon Bell的名言被證明是正確的：“在計算機(jī)系統(tǒng)中，那些最廉價，速度最快以及最為可靠的組件是不存在的?！爆F(xiàn)在，這個函數(shù)已經(jīng)被使用了10多年的時間，并且沒有出現(xiàn)任何故障。 考慮到通過縮減代碼量所得到的好處，我最后以第三種方式來問自己在本章之初提出的問題?！澳銢]有編寫過的最漂亮代碼是什么？”。我如何使用非常少的代碼來實(shí)現(xiàn)大量的功能？答案還是和Quicksort有關(guān)，特別是對這個算法的性能分析。我將在下一節(jié)給出詳細(xì)介紹。3.2 事倍功半 Quicksort是一種優(yōu)雅的算法

9、，這一點(diǎn)有助于對這個算法進(jìn)行細(xì)致的分析。大約在1980年左右，我與Tony Hoare曾經(jīng)討論過Quicksort算法的歷史。他告訴我，當(dāng)他最初開發(fā)出Quicksort時，他認(rèn)為這種算法太簡單了，不值得發(fā)表，而且直到能夠分析出這種算法的預(yù)期運(yùn)行時間之后，他才寫出了經(jīng)典的“Quicksoft”論文。我們很容易看出，在最壞的情況下，Quicksort可能需要n2的時間來對數(shù)組元素進(jìn)行排序。而在最優(yōu)的情況下，它將選擇中值作為劃分元素，因此只需nlgn次的比較就可以完成對數(shù)組的排序。那么，對于n個不同值的隨機(jī)數(shù)組來說，這個算法平均將進(jìn)行多少次比較？Hoare對于這個問題的分析非常漂亮，但不幸的是，其中

10、所使用的數(shù)學(xué)知識超出了大多數(shù)程序員的理解范圍。當(dāng)我為本科生講授Quicksort算法時，許多學(xué)生即使在費(fèi)了很大的努力之后，還是無法理解其中的證明過程，這令我非常沮喪。下面，我們將從Hoare的程序開始討論，并且最后將給出一個與他的證明很接近的分析。我們的任務(wù)是對示例3-1中的Quicksort代碼進(jìn)行修改，以分析在對元素值均不相同的數(shù)組進(jìn)行排序時平均需要進(jìn)行多少次比較。我們還將努力通過最短的代碼、最短運(yùn)行時間以及最小存儲空間來得到最深的理解。為了確定平均比較的次數(shù)，我們首先對程序進(jìn)行修改以統(tǒng)計次數(shù)。因此，在內(nèi)部循環(huán)進(jìn)行比較之前，我們將增加變量comps的值（參見示例3-2）?！臼纠?-2】 修

11、改Quicksort的內(nèi)部循環(huán)以統(tǒng)計比較次數(shù)。 for (i = l+1; i <= u; i+) comps+; if (xi < xl) swap(+m, i); 如果用一個值n來運(yùn)行程序，我們將會看到在程序的運(yùn)行過程中總共進(jìn)行了多少次比較。如果重復(fù)用n來運(yùn)行程序，并且用統(tǒng)計的方法來分析結(jié)果，我們將得到Quicksort在對n個元素進(jìn)行排序時平均使用了1.4 nlgn次的比較。在理解程序的行為上，這是一種不錯的方法。通過十三行的代碼和一些實(shí)驗(yàn)可以反應(yīng)出許多問題。這里，我們引用作家Blaise Pascal和T. S. Eliot的話，“如果我有更多的時間，那么我給你寫的信就會更

12、短?！爆F(xiàn)在，我們有充足的時間，因此就讓我們來對代碼進(jìn)行修改，并且努力編寫出更短（同時更好）的程序。 我們要做的事情就是提高這個算法的速度，并且盡量增加統(tǒng)計的精確度以及對程序的理解。由于內(nèi)部循環(huán)總是會執(zhí)行u-l次比較，因此我們可以通過在循環(huán)外部增加一個簡單的操作來統(tǒng)計比較次數(shù)，這就可以使程序運(yùn)行得更快一些。在示例3-3的Quicksort算法中給出了這個修改?！臼纠?-3】 Quicksort的內(nèi)部循環(huán)，將遞增操作移到循環(huán)的外部comps += u-l;for (i = l+1; i <= u; i+) if (xi < xl) swap(+m, i); 這個程序會對一個數(shù)組進(jìn)行排序

13、，同時統(tǒng)計比較的次數(shù)。不過，如果我們的目標(biāo)只是統(tǒng)計比較的次數(shù)，那么就不需要對數(shù)組進(jìn)行實(shí)際地排序。在示例3-4中去掉了對元素進(jìn)行排序的“實(shí)際操作”，而只是保留了程序中各種函數(shù)調(diào)用的“框架”?！臼纠?-4】將Quicksort算法的框架縮減為只進(jìn)行統(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); 這個程序能夠?qū)崿F(xiàn)我們的需求，因?yàn)镼uichsort在選擇劃分元素時采用的是“隨機(jī)”方式

14、，并且我們假設(shè)所有的元素都是不相等的。現(xiàn)在，這個新程序的運(yùn)行時間與n成正比，并且相對于示例3-3需要的存儲空間與n成正比來說，現(xiàn)在所需的存儲空間縮減為遞歸堆棧的大小，即存儲空間的平均大小與lgn成正比。 雖然在實(shí)際的程序中，數(shù)組的下標(biāo)（l和u）是非常重要的，但在這個框架版本中并不重要。因此，我們可以用一個表示子數(shù)組大小的整數(shù)(n)來替代這兩個下標(biāo)（參見示例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

15、(m-1); qc(n-m); 現(xiàn)在，我們可以很自然地把這個過程整理為一個統(tǒng)計比較次數(shù)的函數(shù)，這個函數(shù)將返回在隨機(jī)Quicksort算法中的比較次數(shù)。在示例3-6中給出了這個函數(shù)?！臼纠?-6】 將Quicksort框架實(shí)現(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中解決的都是相同的基本問題，并且所需的都是相同的運(yùn)行時間和存儲空間。在后面的每個示例都對這些函數(shù)的形式進(jìn)行了改進(jìn)，從而比這些函數(shù)更為清晰和

16、簡潔。 在定義發(fā)明家的矛盾（inventor's paradox）(How To Solve It, Princeton University Press)時，George Póllya指出“計劃越宏大，成功的可能性就越大?！爆F(xiàn)在，我們就來研究在分析Quicksort時的矛盾。到目前為止，我們遇到的問題是，“當(dāng)Quicksort對大小為n的數(shù)組進(jìn)行一次排序時，需要進(jìn)行多少次比較？”我們現(xiàn)在將對這個問題進(jìn)行擴(kuò)展，“對于大小為n的隨機(jī)數(shù)組來說，Quichsort算法平均需要進(jìn)行多少次的比較？”我們通過對示例3-6進(jìn)行擴(kuò)展以引出示例3-7?！臼纠?-7】 偽碼：Quicksort的

17、平均比較次數(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將不會進(jìn)行比較，如示例3-6中所示。對于更大的n，這段代碼將考慮每個劃分值m（從第一個元素到最后一個，每個都是等可能的）并且確定在這個元素的位置上進(jìn)行劃分的運(yùn)行開銷。然后，這段代碼將統(tǒng)計這些開銷的總和（這樣就遞歸地解決了一個大小為m-1的問題和一個大小為n-m的問題），然后將總和除以n得到平均值并

18、返回這個結(jié)果。 如果我們能夠計算這個數(shù)值，那么將使我們實(shí)驗(yàn)的功能更加強(qiáng)大。我們現(xiàn)在無需對一個n值運(yùn)行多次來估計平均值，而只需一個簡單的實(shí)驗(yàn)便可以得到真實(shí)的平均值。不幸的是，實(shí)現(xiàn)這個功能是要付出代價的：這個程序的運(yùn)行時間正比于3n（如果是自行參考（self-referential）的，那么用本章中給出的技術(shù)來分析運(yùn)行時間將是一個很有趣的練習(xí)）。示例3-7中的代碼需要一定的時間開銷，因?yàn)樗貜?fù)計算了中間結(jié)果。當(dāng)在程序中出現(xiàn)這種情況時，我們通常會使用動態(tài)編程來存儲中間結(jié)果，從而避免重復(fù)計算。因此，我們將定義一個表tN+1，其中在tn中存儲cn，并且按照升序來計算它的值。我們將用N來表示n的最大值，也

19、就是進(jìn)行排序的數(shù)組的大小。在示例3-8中給出了修改后的代碼。【示例3-8】 在Quicksort中使用動態(tài)編程來計算t0 = 0for (n = 1; n <= N; n+) sum = 0 for (i = 1; i <= n; i+) sum += n-1 + ti-1 + tn-i tn = sum/n 這個程序只對示例3-7進(jìn)行了細(xì)微的修改，即用tn來替換c(n)。它的運(yùn)行時間將正比于N2，并且所需的存儲空間正比于N。這個程序的優(yōu)點(diǎn)之一就是：在程序執(zhí)行結(jié)束時，數(shù)組t中將包含數(shù)組中從元素0到元素N的真實(shí)平均值（而不是樣本均值的估計）。我們可以對這些值進(jìn)行分析，從而生成在Qui

20、chsort算法中統(tǒng)計比較次數(shù)的計算公式。我們現(xiàn)在來對程序做進(jìn)一步的簡化。第一步就是把n-1移到循環(huán)的外面，如示例3-9所示。【示例3-9】 在Quicksort中把代碼移到循環(huán)外面來計算t0 = 0for (n = 1; n <= N; n+) sum = 0 for (i = 1; i <= n; i+) sum += ti-1 + tn-i tn = n-1 + sum/n現(xiàn)在將利用對稱性來對循環(huán)做進(jìn)一步的調(diào)整。例如，當(dāng)n為4時，內(nèi)部循環(huán)計算總和為：t0+t3 + t1+t2 + t2+t1 + t3+t0在上面這些組對中，第一個元素增加而第二個元素減少。因此，我們可以把總和

21、改寫為：2 * (t0 + t1 + t2 + t3)我們可以利用這種對稱性來得到示例3-10中的Quicksort?！臼纠?-10】 在Quichsort中利用了對稱性來計算t0 = 0for (n = 1; n <= N; n+) sum = 0 for (i = 0; i < n; i+) sum += 2 * ti tn = n-1 + sum/n然而，在這段代碼的運(yùn)行時間中同樣存在著浪費(fèi)，因?yàn)樗貜?fù)地計算了相同的總和。此時，我們不是把前面所有的元素加在一起，而是在循環(huán)外部初始化總和并且加上下一個元素，如示例3-11所示?！臼纠?-11】 在Quicksort中刪除了內(nèi)部循

22、環(huán)來計算sum = 0; t0 = 0for (n = 1; n <= N; n+) sum += 2*tn-1 tn = n-1 + sum/n 這個小程序確實(shí)很有用。程序的運(yùn)行時間與N成正比，對于每個從1到N的整數(shù)，程序?qū)⑸梢粡圦uicksort的估計運(yùn)行時間表。 我們可以很容易地把示例3-11用表格來實(shí)現(xiàn)，其中的值可以立即用于進(jìn)一步的分析。在3-1給出了最初的結(jié)果行。表3-1 示例3-11中實(shí)現(xiàn)的表格輸出NSumtn000100201322.66747.3334.8335177.4631.810.3752.413.486879.37116.921這張表中的第一行數(shù)字是用代碼中的三

23、個常量來進(jìn)行初始化的。下一行（輸出的第三行）的數(shù)值是通過以下公式來計算的：A3 = A2+1 B3 = B2 + 2*C2 C3 = A3-1 + B3/A3 把這些（相應(yīng)的）公式記錄下來就使得這張表格變得完整了。這張表格是“我曾經(jīng)編寫的最漂亮代碼”的很好的證據(jù)，即使用少量的代碼完成大量的工作。 但是，如果我們不需要所有的值，那么情況將會是什么樣？如果我們更希望通過這種來方式分析一部分?jǐn)?shù)值（例如，在20到232之間所有2的指數(shù)值）呢？雖然在示例3-11中構(gòu)建了完整的表格t，但它只需要使用表格中的最新值。因此，我們可以用變量t的定長空間來替代table t的線性空間，如示例3-12所示?！臼纠?

24、-12】 Quicksoft 計算最終版本 sum = 0; t = 0for (n = 1; n <= N; n+) sum += 2*t t = n-1 + sum/n 然后，我們可以插入一行代碼來測試n的適應(yīng)性，并且在必要時輸出這些結(jié)果。這個程序是我們漫長學(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é)了本章中對Quicks

25、ort進(jìn)行分析的程序。表 3-2 對Quicksort比較次數(shù)的統(tǒng)計算法的評價 示例編號 代碼行數(shù) 答案類型 答案數(shù)量 運(yùn)行時間 空間 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 " &qu

26、ot; " " 11 4 " " N " 12 4 Exact N N 1 在我們對代碼的每次修改中，每個步驟都是很直接的；不過，從示例3-6中樣本值到示例3-7中準(zhǔn)確值的過渡過程可能是最微妙的。隨著這種方式進(jìn)行下去，代碼變得更快和更有用，而代碼量同樣得到了縮減。在19世紀(jì)中期，Robert Browning指出“少即是多（less is more）”，而這張表格正是一個證明這種極少主義哲學(xué)（minimalist philosophy）的實(shí)例。我們已經(jīng)看到了三種截然不同的類型的程序。示例3-2和示例3-3是能夠?qū)嶋H使用的Quicksort，可以

27、用來在對真實(shí)數(shù)組進(jìn)行排序時統(tǒng)計比較次數(shù)。示例3-4到示例3-6都實(shí)現(xiàn)了Quicksort的一種簡單模型：它們模擬算法的運(yùn)行，而實(shí)際上卻沒有做任何排序工作。從示例3-7到示例3-12則實(shí)現(xiàn)了一種更為復(fù)雜的模型：它們計算了比較次數(shù)的真實(shí)平均值而沒有跟蹤任何單次的運(yùn)行。我們在下面總結(jié)了實(shí)現(xiàn)每個程序所使用的技術(shù)：*示例3-2，示例3-4，3-7:對問題的定義進(jìn)行根本的修改。* 示例3-5，示例3-6，3-12：對函數(shù)的定義進(jìn)行輕微的修改* 示例3-8：實(shí)現(xiàn)動態(tài)編程的新數(shù)據(jù)結(jié)構(gòu)這些技術(shù)都是非常典型的。我們在簡化程序時經(jīng)常要發(fā)出這樣的疑問，“我們真正要解決的問題是什么？”或者是，“有沒有更好的函數(shù)來解決這

28、個問題？”當(dāng)我把這個分析過程講授給本科生時，這個程序最終被縮減成零行代碼，化為一陣數(shù)學(xué)的輕煙消失了。我們可以把示例3-7重新解釋為以下的循環(huán)關(guān)系： 這正是Hoare所采用的方法，并且后來由D.E.Knuth在他經(jīng)典的The Art of Computer Programming（Addison-Wesley）一書的第三卷：排序與查找中給出的方法中給出了描述。通過重新表達(dá)編程思想的技巧和在示例3-10中使用的對稱性，使我們可以把遞歸部分簡化為：Knuth刪除了求和符號，從而引出了示例3-11，這可以被重新表達(dá)為一個在兩個未知量之間有著兩種循環(huán)關(guān)系的系統(tǒng)： Knuth使用了“求和因子”的數(shù)學(xué)方法來

29、實(shí)現(xiàn)這種解決方案： 其中表示第n個調(diào)和數(shù)（harmonic number），即1 + 1/2 + 1/3 + 1/n。這樣，我們就從對程序不斷進(jìn)行修改以得到實(shí)驗(yàn)數(shù)據(jù)順利地過渡到了對程序行為進(jìn)行完全的數(shù)學(xué)分析。 在得到這個公式之后，我們就可以結(jié)束我們的討論。我們已經(jīng)遵循了Einstein的著名建議：“盡量使每件事情變得簡單，并且直到不可能再簡單為止?！备郊臃治?Goethe的著名格言是：“建筑是靜止的音樂”。按照這種說法，我可以說“數(shù)據(jù)結(jié)構(gòu)是靜止的算法?！比绻覀児潭薗uichsort算法，那么就將得到了一個二分搜索樹的數(shù)據(jù)結(jié)構(gòu)。在Knuth發(fā)表的文章中給出了這個結(jié)構(gòu)并且采用類似于在Quich

30、sort中的循環(huán)關(guān)系來分析它的運(yùn)行時間。如果要分析把一個元素插入到二分搜索樹中的平均開銷，那么我們可以以這段代碼作為起點(diǎn)，并且對這段代碼進(jìn)行擴(kuò)展來統(tǒng)計比較次數(shù)，然后在我們收集的數(shù)據(jù)上進(jìn)行實(shí)驗(yàn)。接下來，我們可以仿照前面章節(jié)中的方式來簡化代碼。一個更為簡單的解決方案就是定義一個新的Quichsort，在這個算法中使用理想的劃分算法把有著相同關(guān)聯(lián)順序的元素劃分到兩邊。Quichsort和二分搜索樹是同構(gòu)的，如圖3-1所示。圖3-1 實(shí)現(xiàn)理想劃分的Quicksort以及相應(yīng)的二分搜索樹左邊的方框給出了正在進(jìn)行中的理想劃分的Quicksort，右邊的圖則給出了相應(yīng)的從相同輸入中構(gòu)建起來的二分搜索樹。這兩

31、個過程不僅需要進(jìn)行相同次數(shù)的比較，而且還將生成相同的比較集合。通過在前面對于在一組不同元素上進(jìn)行Quicksort實(shí)驗(yàn)的平均性能分析，我們就可以得到將不同的元素隨機(jī)插入到二分搜索樹中的平均比較次數(shù)。3.4 本章的中心思想是什么？表面上看來，我“所寫的”內(nèi)容就是從示例3-2到示例3-12的程序。我最初是漫不經(jīng)心地編寫這些程序，然后將這些程序?qū)懺诮o本科生講課的黑板上，并且最終寫到本章中。我有條不紊地進(jìn)行著這些程序的修改，并且花了大量的時間來分析這些程序，從而確信它們都是正確的。然而，除了在示例3-11中實(shí)現(xiàn)的表格外，我從來沒有把任何一個示例作為計算機(jī)程序運(yùn)行過。 我在貝爾實(shí)驗(yàn)室呆了將近二十年，我從

32、許多教師（尤其是Brian Kernighan，他所編寫的編程內(nèi)容作為本書的第1章）那里學(xué)到了：要“編寫”一個在大眾面前展示的程序，所涉及到的東西比鍵入這個程序要多得多。有人用代碼實(shí)現(xiàn)了這個程序，最初運(yùn)行在一些測試示例中，然后構(gòu)建了完整的系統(tǒng)框架、驅(qū)動程序以及一個案例庫來支撐這段代碼。理想的情況是，人們可以手動地把編譯后的代碼包含到文本中，不加入任何的人為干涉?；谶@種想法，我編寫了示例3-1（以及在Programming Pearls中的所有代碼）。為了維護(hù)面子，我希望永遠(yuǎn)都不要實(shí)現(xiàn)從示例3-2到示例3-12的代碼，從而使我保持誠實(shí)的名聲。然而，在計算機(jī)編程中的近四十年的實(shí)踐使我對這個任務(wù)的

33、困難性有著深深的敬畏（好吧，更準(zhǔn)確地說，是對于錯誤的害怕）。我妥協(xié)了，把示例3-11用表格方式實(shí)現(xiàn)出來，并且無意中得到了一個完備的解答。當(dāng)這兩個東西完美地匹配在一起時，你可以想象一下我當(dāng)時的喜悅吧！因此，我向世界提供了這些漂亮的并且未曾實(shí)現(xiàn)的程序，雖然在這些程序中可能會有一些還未發(fā)現(xiàn)的錯誤，但我對這些程序的正確性還是有一定信心的。我希望一些細(xì)微的錯誤不會掩蓋我在這些程序中所展示的那些漂亮思想。 當(dāng)我為給出這些沒有被實(shí)現(xiàn)過的程序感到不安時，Alan Perlis的話安慰了我，他說“軟件是不是不像任何一個事物，它就是意味著被拋棄：軟件的所有意義就是把它看作為一個肥皂泡？”3.5 結(jié)論 漂亮的含義有

34、著許多來源。本章通過簡化、優(yōu)雅以及精簡來刻畫了漂亮的含義。下面這些名言表達(dá)的是同樣的意思：*通過刪除代碼來實(shí)現(xiàn)功能的提升。*只有在不僅沒有任何功能可以添加，而且也沒有任何功能可以刪除的情況下，設(shè)計師才能夠認(rèn)為自己的工作已臻完美。*有時候，在軟件中根本就不存在最漂亮的代碼，最漂亮的函數(shù)，或者最漂亮的程序。*良好的寫作風(fēng)格即為簡練。省略不必要的字詞。 (Strunk and White)*在計算機(jī)系統(tǒng)中，那些最廉價、速度最快以及最為可靠的組件是不存在的（Bell）*努力做到事倍功半。*如果我有更多的時間，那么我給你寫的信就會越短（Pascal）*發(fā)明家的矛盾：計劃越宏大，成功的可能性就越大。（Pólya）*簡單性并不是在復(fù)雜性之前，而是在復(fù)雜性之后（Perlis）*少即是多。（Browning）*盡量使每件事情變得簡單，并且直到不可能再簡單為止（Einstein）*軟件有時候應(yīng)該被視作為一個肥皂泡（Perlis）*在簡單中尋找漂亮。本章的內(nèi)容到此結(jié)束。讀者可以復(fù)習(xí)所學(xué)到的內(nèi)容并進(jìn)行模擬實(shí)驗(yàn)。對于那些想要得到更具體信息的人們，我在下面給出了一些觀點(diǎn)，這些觀點(diǎn)分為三類程序分析 深入理解程序行為的方式之一就是修改這個程序，然后在具有代表性的數(shù)據(jù)上運(yùn)行這個程序，就像示例3-2那樣。不過，我們通常會更關(guān)心程序的某個方