編程珠璣

前言

本書作者Jon Bentley是美國著名的程序員和計算機(jī)科學(xué)家，他于20世紀(jì)70年代前后在很有影響力的《ACM通訊》（Communications of the ACM）上以專欄的形式連續(xù)發(fā)表了一系列短文，成功地總結(jié)和提煉了自己在長期的計算機(jī)程序設(shè)計實(shí)踐中積累下來的寶貴經(jīng)驗(yàn)。這些短文充滿了真知灼見，而且文筆生動、可讀性強(qiáng)，對于提高職業(yè)程序員的專業(yè)技能很有幫助，因此該專欄大受讀者歡迎，成為當(dāng)時該學(xué)術(shù)期刊的王牌欄目之一?？梢韵胂螽?dāng)時的情形頗似早年金庸先生在《明報》上連載其武俠小說的盛況。后來在ACM的鼓勵下，作者經(jīng)過仔細(xì)修訂和補(bǔ)充整理，對各篇文章的先后次序做了精心編排，分別在1986年和1988年結(jié)集出版了Programming Pearls（《編程珠璣》）和More Programming Pearls（《編程珠璣Ⅱ》）這兩本書，二者均成為該領(lǐng)域的名著?！毒幊讨榄^（第2版）》在2000年問世，書中的例子都改用C語言書寫，并多處提到如何用C++和Java中的類來實(shí)現(xiàn)?！毒幊讨榄^Ⅱ》雖未再版，例子多以Awk語言寫成，但其語法與C相近，容易看懂。作者博覽群書，旁征博引，無論是計算機(jī)科學(xué)的專業(yè)名著，如《計算機(jī)程序設(shè)計藝術(shù)》，還是普通的科普名著，如《啊哈！靈機(jī)一動》，都在作者筆下信手拈來、娓娓道出，更不用說隨處可見的作者自己的真知灼見了。如果說《計算機(jī)程序設(shè)計藝術(shù)》這樣的巨著代表了程序員們使用的“坦克和大炮”一類的重型武器，這兩本書則在某種程度上類似于魯迅先生所說的“匕首與投槍”一類的輕型武器，更能滿足職業(yè)程序員的日常需要?；蛘哒f前者是武俠小說中提高內(nèi)力修為的根本秘籍，后者是點(diǎn)撥臨陣招數(shù)的速成寶典，二者同樣都是克敵制勝的法寶，缺一不可。在無止境地追求精湛技藝這一點(diǎn)上，程序員、數(shù)學(xué)家和武俠們其實(shí)是相通的。在美國，這兩本書不僅被用作大學(xué)低年級數(shù)據(jù)結(jié)構(gòu)與算法課程的教材，還用作高年級算法課程的輔助教材。例如，美國著名大學(xué)麻省理工學(xué)院的電氣工程與計算機(jī)科學(xué)開放式核心課程算法導(dǎo)論就將這兩本書列為推薦讀物。這兩本書覆蓋了大學(xué)算法課程和數(shù)據(jù)結(jié)構(gòu)課程的大部分內(nèi)容，但是與普通教材的側(cè)重點(diǎn)又不一樣，不強(qiáng)調(diào)單純從數(shù)學(xué)上來進(jìn)行分析的技巧，而是強(qiáng)調(diào)結(jié)合實(shí)際問題來進(jìn)行分析、應(yīng)用和實(shí)現(xiàn)的技巧，因此可作為大學(xué)計算機(jī)專業(yè)的算法、數(shù)據(jù)結(jié)構(gòu)、軟件工程等課程的教師參考用書和優(yōu)秀課外讀物。書中有許多真實(shí)的歷史案例和許多極好的練習(xí)題以及部分練習(xí)題的提示與解答，非常適合自學(xué)。正如作者所建議的那樣，閱讀這兩本書時，讀者需要備有紙和筆，最好還有一臺計算機(jī)在手邊，邊讀邊想、邊想邊做，這樣才能將閱讀這兩本書的收益最大化。

內(nèi)容概要

本書是計算機(jī)科學(xué)方面的經(jīng)典名著。書的內(nèi)容圍繞程序設(shè)計人員面對的一系列實(shí)際問題展開。作者Jon Bentley 以其獨(dú)有的洞察力和創(chuàng)造力，引導(dǎo)讀者理解這些問題并學(xué)會解決方法，而這些正是程序員實(shí)際編程生涯中至關(guān)重要的。本書的特色是通過一些精心設(shè)計的有趣而又頗具指導(dǎo)意義的程序，對實(shí)用程序設(shè)計技巧及基本設(shè)計原則進(jìn)行了透徹而睿智的描述，為復(fù)雜的編程問題提供了清晰而完備的解決思路。本書對各個層次的程序員都具有很高的閱讀價值。

作者簡介

Jon Bentley，世界著名計算機(jī)科學(xué)家，被譽(yù)為影響算法發(fā)展的十位大師之一。他先后任職于卡內(nèi)基—梅隆大學(xué)(1976—1982)、貝爾實(shí)驗(yàn)室(1982—2001)和Avaya實(shí)驗(yàn)室(2001年至今)。在卡內(nèi)基—梅隆大學(xué)擔(dān)任教授期間，他培養(yǎng)了包括Tcl語言設(shè)計者John Ousterhout、Java語言設(shè)計者James Gosling、《算法導(dǎo)論》作者之一Charles Leiserson在內(nèi)的許多計算機(jī)科學(xué)大家。2004年榮獲Dr．Dobb's程序設(shè)計卓越獎。錢麗艷，北京大學(xué)信息科學(xué)技術(shù)學(xué)院基礎(chǔ)實(shí)驗(yàn)教學(xué)研究所軟件實(shí)驗(yàn)室主任、工程師，畢業(yè)于國防科技大學(xué)。

書籍目錄

第一部分　基礎(chǔ)　第1章　開篇　　　1.1　一次友好的對話　　　1.2　準(zhǔn)確的問題描述　　　1.3　程序設(shè)計　　　1.4　實(shí)現(xiàn)概要　　　1.5　原理　　　1.6　習(xí)題　　　1.7　深入閱讀　　第2章　啊哈！算法　　　2.1　三個問題　　　2.2　無處不在的二分搜索　　　2.3　基本操作的威力　　　2.4　排序　　　2.5　原理　　　2.6　習(xí)題　　　2.7　深入閱讀　　　2.8　變位詞程序的實(shí)現(xiàn)（邊欄）　　第3章　數(shù)據(jù)決定程序結(jié)構(gòu)　　　3.1　一個調(diào)查程序　　　3.2　格式信函編程　　　3.3　一組示例　　　3.4　結(jié)構(gòu)化數(shù)據(jù)　　　3.5　用于特殊數(shù)據(jù)的強(qiáng)大工具　　　3.6　原理　　　3.7　習(xí)題　　　3.8　深入閱讀　　第4章　編寫正確的程序　　　4.1　二分搜索的挑戰(zhàn)　　4.2　編寫程序　　　4.3　理解程序　　　4.4　原理　　　4.5　程序驗(yàn)證的角色　　　4.6　習(xí)題　　　4.7　深入閱讀　　第5章　編程小事　　　5.1　從偽代碼到C程序　　　5.2　測試工具　　　5.3　斷言的藝術(shù)　　　5.4　自動測試　　　5.5　計時　　　5.6　完整的程序　　5.7　原理　　　5.8　習(xí)題　　　5.9　深入閱讀　　　5.10　調(diào)試（邊欄）第二部分　性能　第6章　程序性能分析　　　6.1　實(shí)例研究　　　6.2　設(shè)計層面　　　6.3　原理　　　6.4　習(xí)題　　　6.5　深入閱讀　　第7章　粗略估算　　　7.1　基本技巧　　　7.2　性能估計　　　7.3　安全系數(shù)　　　7.4　Little定律　　　7.5　原理　　　7.6　習(xí)題　　　7.7　深入閱讀　　　7.8　日常生活中的速算（邊欄）　　第8章　算法設(shè)計技術(shù)　　　8.1　問題及簡單算法　　　8.2　兩個平方算法　　　8.3　分治算法　　　8.4　掃描算法　　　8.5　實(shí)際運(yùn)行時間　　　8.6　原理　　　8.7　習(xí)題　　8.8　深入閱讀　　第9章　代碼調(diào)優(yōu)　　　9.1　典型的故事　　　9.2　急救方案集錦　　　9.3　大手術(shù)——二分搜索　　　9.4　原理　　　9.5　習(xí)題　　　9.6　深入閱讀　　第10章　節(jié)省空間　　　10.1　關(guān)鍵在于簡單　　　10.2　示例問題　　　10.3　數(shù)據(jù)空間技術(shù)　　　10.4　代碼空間技術(shù)　　　10.5　原理　　　10.6　習(xí)題　　　10.7　深入閱讀　　　10.8　巨大的節(jié)?。ㄟ厵冢〉谌糠帧?yīng)用　第11章　排序　　　11.1　插入排序　　　11.2　一種簡單的快速排序　　　11.3　更好的幾種快速排序　　　11.4　原理　　　11.5　習(xí)題　　　11.6　深入閱讀　　第12章　取樣問題　　12.1　問題　　　12.2　一種解決方案　　　12.3　設(shè)計空間　　　12.4　原理　　　12.5　習(xí)題　　　12.6　深入閱讀　　第13章　搜索　　　13.1　接口　　　13.2　線性結(jié)構(gòu)　　　13.3　二分搜索樹　　　13.4　用于整數(shù)的結(jié)構(gòu)　　　13.5　原理　　　13.6　習(xí)題　　　13.7　深入閱讀　　　13.8　一個實(shí)際搜索問題（邊欄）　　第14章　堆　　　14.1　數(shù)據(jù)結(jié)構(gòu)　　　14.2　兩個關(guān)鍵函數(shù)　　　14.3　優(yōu)先級隊(duì)列　　　14.4　一種排序算法　　　14.5　原理　　　14.6　習(xí)題　　　14.7　深入閱讀　　第15章　字符串　　　15.1　單詞　　　15.2　短語　　　15.3　生成文本　　　15.4　原理　　　15.5　習(xí)題　　　15.6　深入閱讀　第1版跋　第2版跋　附錄A　算法分類　附錄B　估算測試　附錄C　時空開銷模型　附錄D　代碼調(diào)優(yōu)法則　附錄E　用于搜索的C++類　部分習(xí)題提示　部分習(xí)題答案　索引

章節(jié)摘錄

插圖：第一部分　基礎(chǔ)第1章　開篇1.2　準(zhǔn)確的問題描述對程序員來說，這些需求加起來就是：“如何給磁盤文件排序？”在試圖解決這個問題之前，先將已知條件組織成一種更客觀、更易用的形式。輸入：一個最多包含n個正整數(shù)的文件，每個數(shù)都小于n，其中n=107。如果在輸入文件中有任何整數(shù)重復(fù)出現(xiàn)就是致命錯誤。沒有其他數(shù)據(jù)與該整數(shù)相關(guān)聯(lián)。輸出：按升序排列的輸入整數(shù)的列表。約束：最多有（大約）1MB的內(nèi)存空間可用，有充足的磁盤存儲空間可用。運(yùn)行時間最多幾分鐘，運(yùn)行時間為10秒就不需要進(jìn)一步優(yōu)化了。請花上一分鐘思考一下該問題的規(guī)范說明?，F(xiàn)在你打算給程序員什么樣的建議呢？1.3　程序設(shè)計顯而易見的方法是以一般的基于磁盤的歸并排序程序?yàn)槠瘘c(diǎn)，但是要對其進(jìn)行調(diào)整，因?yàn)槲覀兪菍φ麛?shù)進(jìn)行排序。這樣就可以將原來的200行程序減少為幾十行，同時也使得程序運(yùn)行得更快，但是完成程序并使之運(yùn)行可能仍然需要幾天的時間。另一種解決方案更多地利用了該排序問題的特殊性。如果每個號碼都使用7個字節(jié)來存儲，那么在可用的1MB存儲空間里大約可以存143 000個號碼。如果每個號碼都使用32位整數(shù)來表示的話，在1MB存儲空間里就可以存儲250000個號碼。因此，可以使用遍歷輸入文件40趟的程序來完成排序。在第一趟遍歷中，將0至249999之間的任何整數(shù)都讀入內(nèi)存，并對這（最多）250000個整數(shù)進(jìn)行排序，然后寫到輸出文件中。第二趟遍歷排序250000至499999之間的整數(shù)，依此類推，到第40趟遍歷的時候?qū)?750000至9999999之問的整數(shù)進(jìn)行排序。對內(nèi)存中的排序來說，快速排序會相當(dāng)高效，而且僅僅需要20行代碼。于是，整個程序就可以通過一兩頁紙的代碼實(shí)現(xiàn)。該程序擁有所期望的特性——不必考慮使用中間磁盤文件；不幸的是，為此所付出的代價是要讀取輸入文件40次。1.5　原理那個程序員打電話把他的問題告訴我，然后我們花了大約一刻鐘時問明確了問題所在，并找到了位圖解決方案。他花了幾個小時來實(shí)現(xiàn)這個幾十行代碼的程序。該程序遠(yuǎn)遠(yuǎn)優(yōu)于我們在電話剛開始時所擔(dān)心的需要花費(fèi)一周時間編寫的幾百行代碼的那個程序。而且程序執(zhí)行得很快：磁盤上的歸并排序可能需要許多分鐘的時間，該程序所需的時間只比讀取輸入和寫入輸出所需的時間多一點(diǎn)點(diǎn)——大約10秒鐘。答案3包含了對完成該任務(wù)的幾種不同程序的計時細(xì)節(jié)。從這些事實(shí)中可以總結(jié)出該實(shí)例研究所得到的第一個結(jié)論：對小問題的仔細(xì)分析有時可以得到明顯的實(shí)際益處。在該實(shí)例中，幾分鐘的仔細(xì)研究可以大幅削減代碼的長度、程序員時間和程序運(yùn)行時間。Chuck Yeager將軍（第一個超音速飛行的人）贊揚(yáng)一架飛機(jī)的機(jī)械系統(tǒng)時用的詞是“結(jié)構(gòu)簡單、部件很少、易于維護(hù)、非常堅(jiān)固”，該程序擁有同樣的屬性。然而，當(dāng)規(guī)范說明的某些因素發(fā)生改變時，該程序的特殊結(jié)構(gòu)將很難修改。除了需要精巧的編程以外，該實(shí)例闡明了如下一般原理。正確的問題。明確問題，這場戰(zhàn)役就成功了90％——我很慶幸程序員沒有滿足于我給出的第一個程序。一旦正確理解了問題，習(xí)題10、習(xí)題11和習(xí)題12的答案都會很優(yōu)雅。在查看提示和答案以前，請努力思考這些問題。位圖數(shù)據(jù)結(jié)構(gòu)。該數(shù)據(jù)結(jié)構(gòu)描述了一個有限定義域內(nèi)的稠密集合，其中的每一個元素最多出現(xiàn)一次并且沒有其他任何數(shù)據(jù)與該元素相關(guān)聯(lián)。即使這些條件沒有完全滿足（例如，存在重復(fù)元素或額外的數(shù)據(jù)），也可以用有限定義域內(nèi)的作為一個表項(xiàng)更復(fù)雜的表格的索引，見習(xí)題6和習(xí)題8。多趟算法。這些算法多趟讀入其輸入數(shù)據(jù)，每次完成一步。在1.3節(jié)已經(jīng)見到了一個40趟算法，習(xí)題5鼓勵讀者去完成一個兩趟算法。時間一空間折中與雙贏。編程文獻(xiàn)和理論中充斥著時間一空間的折中：通過使用更多的時間，可以減少程序所需的空間。例如，答案5中的兩趟算法讓程序運(yùn)行時間加倍從而使空間減半。但我的經(jīng)驗(yàn)常常是這樣的：減少程序的空間需求也會減少其運(yùn)行時間?？臻g上高效的位圖結(jié)構(gòu)顯著地減少了排序的運(yùn)行時問?？臻g需求的減少之所以會導(dǎo)致運(yùn)行時間的減少，有兩個原因：需要處理的數(shù)據(jù)變少了，意味著處理這些數(shù)據(jù)所需的時間也變少了；同時將這些數(shù)據(jù)保存在內(nèi)存中而不是磁盤上，進(jìn)一步避免了磁盤訪問的時間。當(dāng)然了，只有在原始的設(shè)計遠(yuǎn)非最佳方案時，才有可能時空雙贏。簡單的設(shè)計。Antoine de Saint—Exupery是法國作家兼飛機(jī)設(shè)計師，他曾經(jīng)說過：“設(shè)計者確定其設(shè)計已經(jīng)達(dá)到了完美的標(biāo)準(zhǔn)不是不能再增加任何東西，而是不能再減少任何東西。”更多的程序員應(yīng)該使用該標(biāo)準(zhǔn)來檢驗(yàn)自己完成的程序。簡單的程序通常比具有相同功能的復(fù)雜程序更可靠、更安全、更健壯、更高效，而且易于實(shí)現(xiàn)和維護(hù)。

后記

本書作者Jon Bentley是美國著名的程序員和計算機(jī)科學(xué)家，他于20世紀(jì)70年代前后在很有影響力的《ACM通訊》（Communications of the ACM）上以專欄的形式連續(xù)發(fā)表了一系列短文，成功地總結(jié)和提煉了自己在長期的計算機(jī)程序設(shè)計實(shí)踐中積累下來的寶貴經(jīng)驗(yàn)。這些短文充滿了真知灼見，而且文筆生動、可讀性強(qiáng)，對于提高職業(yè)程序員的專業(yè)技能很有幫助，因此該專欄大受讀者歡迎，成為當(dāng)時該學(xué)術(shù)期刊的王牌欄目之一?？梢韵胂螽?dāng)時的情形頗似早年金庸先生在《明報》上連載其武俠小說的盛況。后來在ACM的鼓勵下，作者經(jīng)過仔細(xì)修訂和補(bǔ)充整理，對各篇文章的先后次序做了精心編排，分別在1986年和1988年結(jié)集出版了Programming Pearls（《編程珠璣》）和More Programming Pearls（《編程珠璣Ⅱ》）這兩本書，二者均成為該領(lǐng)域的名著?！毒幊讨榄^（第2版）》在2000年問世，書中的例子都改用C語言書寫，并多處提到如何用C++和Java中的類來實(shí)現(xiàn)?！毒幊讨榄^Ⅱ》雖未再版，例子多以Awk語言寫成，但其語法與C相近，容易看懂。作者博覽群書，旁征博引，無論是計算機(jī)科學(xué)的專業(yè)名著，如《計算機(jī)程序設(shè)計藝術(shù)》，還是普通的科普名著，如《啊哈！靈機(jī)一動》，都在作者筆下信手拈來、娓娓道出，更不用說隨處可見的作者自己的真知灼見了。如果說《計算機(jī)程序設(shè)計藝術(shù)》這樣的巨著代表了程序員們使用的“坦克和大炮”一類的重型武器，這兩本書則在某種程度上類似于魯迅先生所說的“匕首與投槍”一類的輕型武器，更能滿足職業(yè)程序員的日常需要?；蛘哒f前者是武俠小說中提高內(nèi)力修為的根本秘籍，后者是點(diǎn)撥臨陣招數(shù)的速成寶典，二者同樣都是克敵制勝的法寶，缺一不可。在無止境地追求精湛技藝這一點(diǎn)上，程序員、數(shù)學(xué)家和武俠們其實(shí)是相通的。在美國，這兩本書不僅被用作大學(xué)低年級數(shù)據(jù)結(jié)構(gòu)與算法課程的教材，還用作高年級算法課程的輔助教材。例如，美國著名大學(xué)麻省理工學(xué)院的電氣工程與計算機(jī)科學(xué)開放式核心課程算法導(dǎo)論就將這兩本書列為推薦讀物。這兩本書覆蓋了大學(xué)算法課程和數(shù)據(jù)結(jié)構(gòu)課程的大部分內(nèi)容，但是與普通教材的側(cè)重點(diǎn)又不一樣，不強(qiáng)調(diào)單純從數(shù)學(xué)上來進(jìn)行分析的技巧，而是強(qiáng)調(diào)結(jié)合實(shí)際問題來進(jìn)行分析、應(yīng)用和實(shí)現(xiàn)的技巧，因此可作為大學(xué)計算機(jī)專業(yè)的算法、數(shù)據(jù)結(jié)構(gòu)、軟件工程等課程的教師參考用書和優(yōu)秀課外讀物。書中有許多真實(shí)的歷史案例和許多極好的練習(xí)題以及部分練習(xí)題的提示與解答，非常適合自學(xué)。正如作者所建議的那樣，閱讀這兩本書時，讀者需要備有紙和筆，最好還有一臺計算機(jī)在手邊，邊讀邊想、邊想邊做，這樣才能將閱讀這兩本書的收益最大化。

編輯推薦

　　多年以來，當(dāng)程序員們推選出最心愛的計算機(jī)圖書時，《編程珠璣》總是位于前列。正如自然界里珍珠出自細(xì)沙對牡蠣的磨礪。計算機(jī)科學(xué)大師Jon Bentley以其獨(dú)有的洞察力和創(chuàng)造力，從磨礪程序員的實(shí)際問題中凝結(jié)出一篇篇不朽的編程“珠璣”，成為世界計算機(jī)界名刊《ACM通訊》歷史上最受歡迎的專欄，最終結(jié)集為兩部不朽的計算機(jī)科學(xué)經(jīng)典名著，影響和激勵著一代又一代程序員和計算機(jī)科學(xué)工作者。本書為第一卷，主要討論計算機(jī)科學(xué)中最本質(zhì)的問題：如何正確選擇和高效地實(shí)現(xiàn)算法。 　　在書中，作者選取許多具有典型意義的復(fù)雜編程和算法問題，生動描繪了歷史上眾大師們在探索解決方案中發(fā)生的軼事、走過的彎路和不斷精益求精的歷程，引導(dǎo)讀者像真正的程序員和軟件工程師那樣富于創(chuàng)新性地思考，并透徹闡述和總結(jié)了許多獨(dú)特而精妙的設(shè)計原則、思考和解決問題的方法以及實(shí)用程序設(shè)計技巧。解決方案的代碼均以C／C++語言編寫，不僅有趣，而且有很大的實(shí)戰(zhàn)示范意義。每章后所附習(xí)題極具挑戰(zhàn)性和啟發(fā)性，書末給出了簡潔的解答。

名人推薦

“《編程珠璣》第1版是對我職業(yè)生涯早期影響最大的書之一，其中的許多真知灼見多年之后仍然使我受益匪淺。Jon在第2版中對素材進(jìn)行了大量更新，許多新內(nèi)容讓我耳目一新。” 　　——Steve McConnell，軟件工程大師，IEEE Software前主編?！洞a大全》作者“對每一位遇到的程序員，我都會毫不遲疑地建議他閱讀并不斷重讀這部經(jīng)典之作?！?　　——Slashdot

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    編程珠璣 PDF格式下載

---