之前在微博 @算法時(shí)空 做了一次電臺，花了一個(gè)多小時(shí)談了一下Sedgewick和Wayne所著的暢銷書《算法》第4版(影印版和中譯版均由人民郵電出版社出版)，特別是按照這本書的目錄給出了導(dǎo)讀。覺得有必要把文字整理出來，希望對閱讀此書的朋友有所幫助。
歷史
《算法》第4版這本書其實(shí)不太像傳統(tǒng)的算法書，但是它很暢銷！實(shí)際上，這不僅因?yàn)樗薪咏氖甑膫鞒校啻涡抻啿粩噙M(jìn)化方才如此，而是作者的最新教學(xué)理念的展現(xiàn)。
算法分析大師Sedgewick一開始寫這個(gè)系列的書，心中就有宏偉的念頭，要傳承Knuth的衣缽，因?yàn)镾edgewick作為Knuth的學(xué)生，他覺得當(dāng)仁不讓，所以雄心勃勃。其實(shí)Sedgewick剛開始開始寫《算法》的時(shí)候，也就是《算法》第1版，內(nèi)容相對比較簡單。隨著時(shí)間流逝，第2版和第3版不斷進(jìn)化，而此時(shí)這套書的難度到達(dá)了巔峰。
實(shí)際上《算法》第3版出過很多語言版本，比如C++, C, Java版(國內(nèi)高教出版社影印過)。最開始是C, C++然后是Java，其實(shí)Sedgewick想把Knuth難度極高的《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》三卷書濃縮成《算法》的上卷(或稱Part 1-4)，并用不同語言來實(shí)現(xiàn)，從而形成更適合教學(xué)的優(yōu)秀教科書。這本上卷名為《算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)、排序和查找》，其內(nèi)容非常接近《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》的第1卷(基本算法)和第3卷(排序與查找)，去掉了第2卷(因?yàn)橐话愦蠹叶疾豢吹?卷，里面講的是隨機(jī)數(shù)生成等內(nèi)容)?！端惴ā返南戮?或稱Part 5)，從《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》往下開始寫，專講圖算法，雖然比上卷薄，但內(nèi)容依然很豐富。
變革
Sedgewick花了這么多年將這套《算法》做到了很高的層次，為什么寫到第4版的時(shí)候，思路有了一個(gè)如此大的轉(zhuǎn)變呢？實(shí)際上他在前言里說到，第4版的難度相當(dāng)于第1版或者第2版的樣子，回復(fù)到一個(gè)基礎(chǔ)簡單的水平，也是Addison-Wesley出版社的Peter Gordon建議他要back to the basics。
《算法》第4版的核心寫作思想就是降低算法學(xué)習(xí)的難度，這是一種大勢所趨，實(shí)際上寫到了巔峰沒幾個(gè)人能看懂。就拿Knuth的三卷《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》來說吧，很多人看到數(shù)學(xué)知識太繁雜，算法分析長篇大論，而且Knuth有點(diǎn)強(qiáng)迫癥(不過他創(chuàng)造的TeX排版確實(shí)太好了)，書里用MMIX，讀者還得學(xué)這個(gè)。實(shí)際上，《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》這樣一個(gè)高大上的體系讓Knuth奉獻(xiàn)了一生，特別是里面的算法分析，數(shù)學(xué)推導(dǎo)特別多。但是，Knuth的得意門生Sedgewick在這樣的時(shí)代卻寫了一本難度比較低的算法書，實(shí)際上是有很多無奈的。
Google的Peter Norvig說Knuth的三卷《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》可以墊高顯示器，由于盒裝可以從里面抽出一本隨時(shí)翻閱。但更多的人拿這個(gè)墊顯示器估計(jì)不會拿出來看了。
前幾年的Sedgewick的個(gè)人網(wǎng)站還有《算法》第3版后續(xù)部分也就是組合算法部分的寫作計(jì)劃，和老師Knuth的思路完全一樣。這兩年這部分寫作計(jì)劃似乎取消了，可能寫出來太耗時(shí)，曲高和寡沒人看。最終Sedgewick決定讓算法成為新時(shí)代大家都能接受的東西，切實(shí)能夠提高程序員水平，而不是高深的理論和繁難的技術(shù)。老實(shí)說，很多人根本用不到那么多算法，所以《算法》第4版看似思路清奇但合情合理。
《算法》居然沒有講動態(tài)規(guī)劃，你說這叫算法書嗎？當(dāng)然可以叫算法書，它其實(shí)就不太注重動態(tài)規(guī)劃這些內(nèi)容，其實(shí)普通人也用不太上。
另外，復(fù)雜的數(shù)學(xué)語言《算法》第4版里都沒有，而Sedgewick本人算法分析功底相當(dāng)深厚。我相信他這樣的大師，肯定能了解普通人接受起來有困難，所以就放下了自己擅長的理論分析。所以，經(jīng)過四十年風(fēng)風(fēng)雨雨，最后變成了《算法》第4版，精選了普通程序員確實(shí)能用的內(nèi)容，確實(shí)不易。
這本書對我的教學(xué)觀有很大的影響，也激發(fā)了我開設(shè)“算法時(shí)空”知識星球。以前我講算法的時(shí)候，沒事喜歡推導(dǎo)一下大O記號之類，動不動寫個(gè)公式求個(gè)極限，給出比較高深的證明，可能是受到《算法導(dǎo)論》這種書的影響。但我現(xiàn)在好像越講越簡單了，力圖讓大家多少有點(diǎn)收獲吧。
Sedgewick在寫這本書的時(shí)候，得到了第二作者Wayne的大力協(xié)助。Wayne是個(gè)藝術(shù)天賦很高的人，不太醉心于科研而特別喜歡講課，他博士師從康奈爾大學(xué)的Tardos，畢業(yè)之后就一直積極開展教學(xué)工作，另外還給Kleinberg和Tardos的《算法設(shè)計(jì)》做了課件(官方指定版)，可能Wayne的課件做得太好了吧。所以《算法》第4版排版特別清新，而且是雙色印刷，Wayne絕對功不可沒。另外，國內(nèi)影印版印刷質(zhì)量很不錯(cuò)，我感覺紙張比原版還要厚實(shí)，可能原版有點(diǎn)薄還有反光，不知道紙張到底如何選取的。
Kevin Wayne is the Phillip Y. Goldman Senior Lecturer in Computer Science at Princeton University, where he has taught since 1998, earning several teaching awards.
下面來看看《算法》第4版的構(gòu)成，從目錄講起。
第1章 基礎(chǔ)知識
1.1 編程模型，主要討論Java基礎(chǔ)知識和二分查找。因?yàn)檫@本書前期有Java程序設(shè)計(jì)的課程，所以1.1篇幅很短。主要是Java程序員太多了，所以Sedgewick沒有在《算法》第4版用C++這樣的語言。順便提一下，現(xiàn)代C++如果只用簡單的語法部分也不是特別難，而且性能非常優(yōu)秀。
1.2 數(shù)據(jù)抽象，也就是所謂抽象數(shù)據(jù)類型(ADT)。其實(shí)抽象數(shù)據(jù)類型在數(shù)據(jù)結(jié)構(gòu)課程里都學(xué)過，但很多人對它的理解不深刻，處理算法問題應(yīng)該在抽象數(shù)據(jù)類型的層次上來做。比如你拿到了集合這樣的抽象數(shù)據(jù)類型，所有數(shù)據(jù)在里面，而集合是個(gè)黑盒我們不用操心，只需要調(diào)用集合的接口來使用即可。其實(shí)數(shù)據(jù)結(jié)構(gòu)教學(xué)的趨勢早已如此，不過國內(nèi)的教學(xué)還沒有完全與之一致。有了抽象數(shù)據(jù)類型之后，所有的處理都在抽象數(shù)據(jù)類型上展開，我們不需要會實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)，只要能用抽象數(shù)據(jù)類型并且知道其原理和性能即可，也就是接口與實(shí)現(xiàn)分離。
1.3 這節(jié)是與傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)講解完全不一樣的地方，以前大家都會講很多數(shù)據(jù)結(jié)構(gòu)，而實(shí)際中真正有用的卻不是那么多?！端惴ā返?版就精選了包、隊(duì)列和棧。包就是不用操心其中元素次序的抽象數(shù)據(jù)類型，放進(jìn)去當(dāng)儲藏室就可以了，內(nèi)部實(shí)現(xiàn)其實(shí)是鏈表但不提供刪除。隊(duì)列和棧很常用，我們就不多說了，另外如何高效實(shí)現(xiàn)隊(duì)列我們其實(shí)也不用操心。所以，《算法》第4版一開始就抽象和提煉了三個(gè)抽象數(shù)據(jù)類型(注意不是數(shù)據(jù)結(jié)構(gòu))，有了抽象數(shù)據(jù)類型的基礎(chǔ)就可以無腦使用，但是要知道隊(duì)列是FIFO而棧是LIFO的特性。這一節(jié)相當(dāng)贊，一開始學(xué)習(xí)不會讓讀者涉獵太多的數(shù)據(jù)結(jié)構(gòu)，學(xué)習(xí)難度大大降低。
說實(shí)話《算法》第4版的寫作思路和當(dāng)前的現(xiàn)實(shí)有關(guān)，很多人不愿意去學(xué)習(xí)那些復(fù)雜繁瑣的東西，這是大趨勢。怎么辦呢？可以簡化內(nèi)容去講一些最有用的東西，把精力投入其它事情上去，初學(xué)數(shù)據(jù)結(jié)構(gòu)要掌握的從原來的復(fù)雜多樣到現(xiàn)在的簡單明了，就講三個(gè)！
1.4 算法分析。這節(jié)篇幅非常短，不到30頁。你可以想象這樣一位算法分析大師在寫本節(jié)的時(shí)候，是什么樣的心情。明明有很多想寫出來的公式，很多想告訴學(xué)生的高深內(nèi)容，但Sedgewick一個(gè)都不寫。他完全沒有寫從理論到理論的模型，也就是《算法導(dǎo)論》還有Aho等人的《算法設(shè)計(jì)與分析》那種體系，這些書首先考慮三種情況(最壞、最好和平均)，以大O記號描述，并主要以最壞情況來討論，Sedgewick在《算法》第4版里特別隱忍，這是不太容易的。大部分在算法分析上有所造詣的人可能都忍不住想講解這些內(nèi)容，但是Sedgewick就忍住了。他怎么做的呢？偏重于科普，讓讀者了解物理直覺。只要知道大概什么樣的算法更快、什么更慢，這就可以了。Sedgewick用了一種做實(shí)驗(yàn)的方法，觀察算法的運(yùn)行快慢并建立模型?？梢钥吹健端惴ā返?版里只提到量級(實(shí)際上接近于Theta記號)，連大O記號都不用，只用簡單語言簡化描述，并用圖示刻畫函數(shù)的增長，另外用加倍實(shí)驗(yàn)直觀展示了增長量級。一言以蔽之，讓讀者知道只需要了解這么多就可以了。這種想法看起來很奇怪，但其實(shí)很有道理，因?yàn)槠綍r(shí)能用到的大O記號就那么幾種，知道它們就可以了，不用太過于深入理論知識，頂多再了解一些極限的求解即可。我覺得，對于算法分析大師來說寫這節(jié)真的很痛苦。不過Sedgewick把基本思想寫進(jìn)去了，而且用簡單語言描述。《算法》第3版還是寫了很多算法分析的基礎(chǔ)知識，還有遞推式的內(nèi)容，但《算法》第4版全都去掉了。盡量用通俗的語言讓更多人了解算法分析。
一般算法書上都會對各種不同量級的實(shí)測時(shí)間給出直觀的例子。對于較大的問題規(guī)模：線性算法比較快，線性對數(shù)算法也不錯(cuò)，平方算法慢多了，指數(shù)算法永遠(yuǎn)沒法完成。
1.5 有了前面數(shù)據(jù)結(jié)構(gòu)的內(nèi)容和算法分析的基礎(chǔ)，接下來馬上講實(shí)際案例可以讓人體會理論的力量。這節(jié)討論了合并—查找算法，也就是如何快速實(shí)現(xiàn)等價(jià)類，所用的數(shù)據(jù)結(jié)構(gòu)看起來是樹，但實(shí)際只需要父親結(jié)點(diǎn)數(shù)組就可以描述?？梢钥闯觯昧藘?yōu)秀的算法可以極大地提升性能。其實(shí)合并—查找的思路和想法都很樸素簡單，但算法分析特別困難，也就是那種看似很簡單其實(shí)不然的典型實(shí)例。Sedgewick用這個(gè)很好的實(shí)例來說明，好的算法是怎樣能提升性能的。實(shí)際上, 《算法》第3版就是如此安排, 而《算法設(shè)計(jì)》這本書也仿效這個(gè)在一開始講合并—查找的設(shè)計(jì)，說明這個(gè)案例確實(shí)特別經(jīng)典，而且適合初學(xué)者入門。
第2章 排序
第2章和第3章著重討論排序和查找，一眼就能看出來用的是Knuth《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》第3卷的體系，而這也是Sedgewick精心研究的內(nèi)容。
一開始講了幾個(gè)簡單的排序算法，也就是插入排序和選擇排序這些平方時(shí)間的排序，我覺得這幾種算法練練手就可以了。另外《算法》第4版給出了排序算法的可視化，現(xiàn)在數(shù)據(jù)結(jié)構(gòu)和算法的可視化也是相當(dāng)重要的(推薦VisuAlgo：https://visualgo.net/)，數(shù)據(jù)到底如何變化用直觀方式就可以學(xué)明白。
前一段時(shí)間有人在微博上問我Shell排序的一個(gè)細(xì)節(jié)問題。說實(shí)話，這些排序算法現(xiàn)在看得很少，能不講就不講，這些東西平時(shí)也不用，性能也一般。其實(shí)也失去了講解的意義，沒事看看就好了。
基礎(chǔ)的排序我們就不談太多，接下來我們就看看線性對數(shù)時(shí)間量級的排序算法。
2.2 歸并排序，實(shí)現(xiàn)方式有兩種：自頂向下的遞歸實(shí)現(xiàn)和自底向上的實(shí)現(xiàn)。歸并排序看起來沒什么太大的用處(因?yàn)樗皇翘貏e快)，但在外存排序里非常有用，而且它基本上是少數(shù)幾個(gè)外存排序里最主流和最實(shí)用的一種了，其他排序算法基本都用不上。我所翻譯的《算法設(shè)計(jì)指南》里面有個(gè)War Story講了一點(diǎn)外存排序的思想。最后談了一下排序問題的復(fù)雜度，也就是排序算法的線性對數(shù)下界，講到這里相信大家會有一點(diǎn)對排序問題的本質(zhì)理解了。
2.3 快速排序，快速排序大家都要講，而《算法》第4版講了改進(jìn)。有時(shí)間的話，建議大家可以看看不同版本的標(biāo)準(zhǔn)庫實(shí)現(xiàn)(特別是clang)，看看這些庫究竟是怎么實(shí)現(xiàn)的。實(shí)際上，自己實(shí)現(xiàn)的快速排序算法性能一般不太好，特別是在處理遞歸調(diào)用比較多的時(shí)候(可以試試10億個(gè)浮點(diǎn)數(shù))，尾遞歸太多容易棧溢出。
看了標(biāo)準(zhǔn)庫的實(shí)現(xiàn)之后，就會明白什么是理論與工程的完美結(jié)合，而快速排序是一個(gè)特別好的例子。例如這個(gè)
qsort的實(shí)現(xiàn)：https://opensource.apple.com//source/xnu/xnu-1456.1.26/bsd/kern/qsort.c
2.4 優(yōu)先級隊(duì)列和堆堆排序。實(shí)際上優(yōu)先級隊(duì)列是非常有用的抽象數(shù)據(jù)類型，有一篇小論文說到荒島上你會帶什么唯一的抽象數(shù)據(jù)類型，答案就是優(yōu)先級隊(duì)列。
論文名：If you were lost on a desert island, what one ADT would you like to have with you? 優(yōu)先級隊(duì)列可以實(shí)現(xiàn)棧，也可以實(shí)現(xiàn)隊(duì)列，只需要用時(shí)間為優(yōu)先級即可。
優(yōu)先級隊(duì)列的變化還是相當(dāng)多的，可以深入了解這方面的知識，例如可以參考Handbook of Data Structures and Applications。有了優(yōu)先級隊(duì)列之后，接著講堆排序，這里不再多說，給一個(gè)堆排序的實(shí)現(xiàn)(https://opensource.apple.com/source/Libc/Libc-167/stdlib.subproj/heapsort.c.auto.html)。
2.5 這節(jié)的關(guān)鍵是該使用哪種排序算法，什么時(shí)候用什么排序，這個(gè)問題很重要。
排序講到這里就結(jié)束了，最有用的就是三種：歸并排序、快速排序和堆排序，講得很簡化。其實(shí)我覺得可以更極端一點(diǎn)，基礎(chǔ)的排序只需要知道這兩點(diǎn)即可：插入排序在小數(shù)據(jù)情況很快；選擇排序可以過渡到堆排序。其他平方時(shí)間的排序都可以不講了，反正用處也不是很大。
實(shí)際上，學(xué)堆排序更大的用處是為了讓你了解和掌握優(yōu)先級隊(duì)列這種抽象數(shù)據(jù)類型。快速排序是為了讓你了解隨機(jī)化算法。歸并排序是外存算法，盡可能少做內(nèi)外存交換(但不可能完全用內(nèi)存處理)。
也就是說，我們從排序這章要學(xué)一些算法思維和工程思想。
第3章 查找
排序和查找為何如此重要，Knuth在《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》第3卷提到大多數(shù)主機(jī)的時(shí)間都在進(jìn)行排序和查找，而查找對于我們來說更為常見。查找部分的內(nèi)容首先從符號表開始，所謂符號表就是一個(gè)"鍵—值"的集合，而查找就是用鍵去查值。
3.2和3.3 第一種思路是最壞時(shí)間所有操作都能在對數(shù)時(shí)間內(nèi)完成的樹查找結(jié)構(gòu)，一般要完成插入、刪除和查找，它們都在可以對數(shù)時(shí)間內(nèi)完成。先用二叉查找樹，但是它在最壞情況下達(dá)不到對數(shù)時(shí)間而退化成鏈表，基本原因是不平衡也就是樹太高了。為了平衡用了兩種方法就是2-3樹和紅黑樹，有的書上會講AVL樹但《算法》第4版放在習(xí)題里了。
我個(gè)人認(rèn)為，紅黑樹其實(shí)也不用掌握，一般人知道有這么一種結(jié)構(gòu)可以高效實(shí)現(xiàn)集合就可以了，效率就是對數(shù)時(shí)間，而且是最壞情況的保證。
3.4 不過對數(shù)時(shí)間雖然比較快，而且最壞情況有保證，但真去查找起來有時(shí)候不如散列。如何調(diào)整散列是一個(gè)比較技術(shù)性的內(nèi)容。很多人有這樣的誤解，散列的查找在期望時(shí)間是常數(shù)時(shí)間，那全部都用散列就好了。很多語言比如Python都提供了字典，而且是常數(shù)時(shí)間，用起來很方便，好像很厲害。但最壞情況下會退化成線性時(shí)間，但是一定要有所選擇，特別是最壞情況有要求。當(dāng)然，還有更多高級技術(shù)，可以改進(jìn)散列。
一定不能一提到散列就馬上認(rèn)為是常數(shù)時(shí)間特別好，要有選擇地使用。而且《算法》第4版也講了如何選擇散列還是樹結(jié)構(gòu)。沒有免費(fèi)午餐(No Free Lunch)！
看起來查找部分內(nèi)容不多，其實(shí)我們大家平時(shí)用的也就是這些抽象數(shù)據(jù)類型，比如C++里也就是set(紅黑樹實(shí)現(xiàn))和unorder_set(散列實(shí)現(xiàn))而已，其他語言也都有類似這樣的抽象數(shù)據(jù)類型，所以用其他語言也可以看《算法》第4版，不影響對算法實(shí)質(zhì)的掌握。
第4章 圖
前面講完直接跳到圖算法，圖算法在《算法》第4版的篇幅也不是很多，其實(shí)很多人在實(shí)際工作中也用不到特別深入的圖算法，真正要用的時(shí)候又可能一籌莫展。于是就有這樣的難題：到底圖算法要學(xué)到什么層次，教材又該如何選擇教學(xué)內(nèi)容呢？
4.1 無向圖，這里講道了深度優(yōu)先搜索和廣度優(yōu)先搜索，里面講的最多是迷宮。迷宮到底用DFS還是BFS呢？讀者不妨考慮一下。下來是連通分量。這些都是圖論里的簡單內(nèi)容，但是能提升讀者的圖算法思想。隨后講了有向圖、可達(dá)性和強(qiáng)連通分量，特別重要的就是強(qiáng)連通分量(SCC)算法，而這是《算法》第4版里比較難的內(nèi)容了(因?yàn)闆]講網(wǎng)絡(luò)流，其實(shí)一般人也不要學(xué)網(wǎng)絡(luò)流了，學(xué)一些基本圖算法就夠了)。
物理學(xué)家黃昆說道：學(xué)習(xí)知識不是越多越好、越深越好，而是應(yīng)當(dāng)和自己駕馭知識的能力相匹配。這句話放在算法學(xué)習(xí)特別是圖算法的學(xué)習(xí)是相當(dāng)合適的。
4.3 最小生成樹，主要是Prim算法和Kruskal算法。特別是Kruskal算法又用到了合并—查找，這里可以看到數(shù)據(jù)結(jié)構(gòu)的優(yōu)化在圖算法中能起到很重要的作用，提速特別明顯。要注意，有些算法思想不一定今天能用到，但你的思路改進(jìn)了，思想開闊了，將來就有可能用到，最差也可以感受一下算法之美。
選擇一本算法書的基準(zhǔn)是看看圖的表示方法，如果不能正確使用鄰接表描述圖算法，那么說明作者的圖算法沒有入門。很多教材用鄰接矩陣描述，而主流的算法設(shè)計(jì)以及分析都應(yīng)該建立在鄰接表上。
4.4 最短路徑。這里不多說最短路徑的內(nèi)容了，舉個(gè)例子，平時(shí)我們叫車用最短路徑，如果是時(shí)長的話可以考慮最短時(shí)長路徑的求解。
第5章 字符串
對很多程序員更有用的其實(shí)是字符串的處理，一般算法書講得少，覺得似乎不是特別高端，不如動態(tài)規(guī)劃炫酷，但《算法》第4版著重講解了這部分內(nèi)容。
5.1 一開始講的可以認(rèn)為是針對多鍵(multiple keys)或者多個(gè)數(shù)據(jù)域的排序。對于字符串來說，低位優(yōu)先(LSD)可以更快地對等長的字符串來排序，而不會去用快速排序這些普適算法，這樣處理字符串更快，而字符串的取值空間有限特性很重要。而不等長的可以采用高位優(yōu)先(MSD)，后面進(jìn)一步改進(jìn)成字符串的三路快速排序，深入探討了字符串排序。
Bentley和Sedgewick的論文Fast Algorithms for Sorting and Searching Strings可以深入研究(http://www.cs.princeton.edu/~rs/strings/paper.pdf)，闡述了Multikey Quicksort的原理并分析了性能。另外，Sedgewick的講義Advanced Topics in Sorting(https://www.cs.princeton.edu/~rs/AlgsDS07/05AdvTopicsSorting.pdf)有關(guān)于排序的一些高級主題。
5.2 trie，也就是單詞查找樹。搜索框就是簡單的trie，比如想輸入abstract，那么依次輸入a-b-s-t，先從樹上走a這個(gè)分支，再走b隨后走s繼續(xù)走t分支，最后剩下的以abst為前綴的單詞也沒剩幾個(gè)了，很容易找到abstract這個(gè)單詞，注意這種實(shí)現(xiàn)需要26叉樹(可用ternary search trie改進(jìn)之)。trie非常有用，還有后綴樹和后綴數(shù)組等內(nèi)容也可以作為選學(xué)材料。
5.3 字符串的查找，所謂模式匹配，Sedgewick強(qiáng)調(diào)的是后面的一系列算法(當(dāng)然不能繞過他老師的KMP算法)，例如Boyer-Moore算法和Rabin-Karp算法，這兩種更有用而且更快。KMP強(qiáng)烈依賴于自我的模式，要自身重復(fù)，但很多字符串不具備這些特性，而Boyer-Moore或Rabin-Karp更適合于一般的字符串查找。
5.4 講完上述內(nèi)容就開始討論正則表達(dá)式。又一次說明了字符串這章對實(shí)際程序員更有用，一般算法教材講的圖算法還有動態(tài)規(guī)劃對于普通程序員來說，要想用好其實(shí)很難，而字符串卻經(jīng)常能感受到。
5.5 本章結(jié)尾講到了數(shù)據(jù)壓縮，這部分是非常好的算法應(yīng)用場景。像CMU的"真實(shí)世界的算法"這門課程里講了很多數(shù)據(jù)壓縮的算法(還有糾錯(cuò)編碼和線性規(guī)劃)，也就是實(shí)際算法可以看到很多字符串的處理，又比如Huffman編碼用到了優(yōu)先級隊(duì)列，處理數(shù)據(jù)可以用到trie還有散列，形形色色算法的應(yīng)用讓你親身體驗(yàn)算法之大用。其實(shí)，數(shù)據(jù)壓縮不是太難，自己如果可以很快實(shí)現(xiàn)壓縮軟件會有一定成就感。我講信息論課程的時(shí)候會讓學(xué)生做一般文本文件的數(shù)據(jù)壓縮，看看壓縮和解壓的效率與常用軟件如Winzip或者7zip有什么性能差異，這樣能極大地提升學(xué)習(xí)興趣。此外，文本壓縮還有一些字典系列的編碼(7zip的體系)，還會有更多算法與數(shù)據(jù)結(jié)構(gòu)的應(yīng)用，特別是散列還有滑動窗的設(shè)置，如果能實(shí)現(xiàn)基本的LZ77和LZ78，那么算法了解和應(yīng)用又能上一個(gè)臺階。我也借鑒《算法》第4版的一些特點(diǎn)，讓學(xué)生實(shí)現(xiàn)DNA序列的壓縮，這樣會有趣味性，也更有針對性。
CMU的15-853: Algorithms in the Real World這門課程(http://www.cs.cmu.edu/~guyb/realworld.html)非常值得一看，非常適合進(jìn)階學(xué)習(xí)。
第6章 實(shí)境
《算法》第4版前五章的內(nèi)容很精煉，和其他算法書都不一樣，也許稱之為《數(shù)據(jù)結(jié)構(gòu)與算法》更合適一點(diǎn)，因?yàn)橹v數(shù)據(jù)結(jié)構(gòu)的內(nèi)容較多。
第6章就是講真實(shí)的問題，并由此引出前面的算法和指導(dǎo)讀者應(yīng)該學(xué)習(xí)什么樣的內(nèi)容。在真實(shí)問題的背景下把前面的內(nèi)容拿出來再講，其實(shí)效果非常好。
典型例子是離散事件仿真(DES)，例如公交車的調(diào)度仿真要考慮某個(gè)線路何時(shí)發(fā)車。發(fā)車相當(dāng)于一個(gè)"事件"，有很多車會發(fā)車但時(shí)間不同，我們不是按照固定時(shí)間間隔(例如分鐘)向前逐個(gè)處理和方針，而是處理"事件"并將其放入優(yōu)先級隊(duì)列，只需按照事件發(fā)生時(shí)間先后取出并處理，最早出現(xiàn)的事件肯定最先出隊(duì)，這樣能夠極大提升算法仿真速度。不能按時(shí)間間隔去逐個(gè)處理，這樣特別慢，比如當(dāng)前時(shí)間為6:30而如果下一個(gè)事件7:10出現(xiàn)，那么時(shí)間點(diǎn)直接推進(jìn)到7:10即可。
語言選用
《算法》這個(gè)系列的書最開始用C語言，可能是想讓他老師Knuth的書更簡單容易讀，另外那個(gè)年代C還是比較流行的。后來大家用C++，Sedgewick也推出了相關(guān)版本，并且也推進(jìn)到Java版本。但第4版不標(biāo)注語言版本直接用Java，也說明Java的熱度，實(shí)際上沒有提到什么語言也說明不想寫別的語言版本了。
不過，現(xiàn)在用Python也很多而且也更接近于機(jī)器學(xué)習(xí)和數(shù)據(jù)處理，這個(gè)其實(shí)很合理，一門語言學(xué)好了能做很多事情，所以都去學(xué)Python。而Sedgewick緊跟時(shí)代，又出了專門講Python的教材，我本來覺得第5版很可能就是Python版(假設(shè)有第5版)。因?yàn)榍捌诘?code>Python基礎(chǔ)的書已經(jīng)有了，程序設(shè)計(jì)的知識講過了，后面直接用Python講算法課而且還可以做機(jī)器學(xué)習(xí)，這也是MIT多年講《算法導(dǎo)論》的首選語言，大勢所趨嘛，而且實(shí)現(xiàn)起來方便。最關(guān)鍵的是，很多人不愿意用復(fù)雜的語言解決問題，現(xiàn)在的人越來越懶:-)而且重度依賴于機(jī)器，沒事不用C和C++寫程序。
為了求證這個(gè)Python版本的猜測，我郵件求證了Wayne，他說暫無
Python版本的寫作計(jì)劃，其原因是用Python寫的代碼遠(yuǎn)遠(yuǎn)慢于Python自身提供的庫函數(shù)，這樣起不到展示算法和數(shù)據(jù)結(jié)構(gòu)效率的目的。
排版
實(shí)際上排版是《算法》第4版的一大特色，第3版用LaTeX排版，而第4版居然用InDesign排版，但是雙色印刷相當(dāng)精美細(xì)致。主要是公式很少，所以用了InDesign。
我郵件咨詢過Wayne，這么復(fù)雜的圖能用LaTeX排出來么？他的回復(fù)讓我很詫異，居然是用InDesign排版，另外這些精美的插圖矢量圖是拿AI畫的，所以融合起來用Adobe一家的產(chǎn)品更好，保持一致。實(shí)際上從成書效果來看，排版確實(shí)美輪美奐，非常滿意。
當(dāng)然也是因?yàn)椤端惴ā返?版的公式少，實(shí)際上這本書基本不講公式，能不用就不用，這點(diǎn)節(jié)約了大家的腦力。因?yàn)閿?shù)學(xué)確實(shí)會給很多人帶來困擾，實(shí)際上數(shù)學(xué)讓人會有特別深的恐懼感。算法再加數(shù)學(xué)更讓人害怕了，所以《算法》第4版用到了算法運(yùn)行實(shí)況(到底如何運(yùn)行，一步步告訴大家)和可視化的方法。
《算法》第4版和前3版有將近40年的傳承，而第二作者Wayne為這一版本付出了相當(dāng)大的心血，這點(diǎn)很難得(絕大多數(shù)高校教師因?yàn)橐隹蒲兴宰霾坏竭@點(diǎn)，而且也沒有這么多精力來精心編撰教材)，而Wayne投入了很多精力放在這本書上。不過，從繪圖和排版軟件的選擇上來說，還是比較符合這本書的目的，主要能更好服務(wù)于普通讀者，一看就不是特別難，而且又是彩色印刷，所以很能吸引眼球。
Q & A
- 先修課程是什么？有一點(diǎn)離散數(shù)學(xué)知識就可以了，《算法導(dǎo)論》后面的附錄基本也就夠了，可以放心學(xué)《算法》第4版。
- 要學(xué)什么數(shù)學(xué)？學(xué)別的算法書，離散數(shù)學(xué)是要學(xué)的，高等數(shù)學(xué)也是要學(xué)的，概率論也是不能丟的，線性代數(shù)也得非常好才行，矩陣如果不會好多東西用不成。但《算法》第4版里基本沒有什么矩陣，哈哈。當(dāng)然，多學(xué)一點(diǎn)離散數(shù)學(xué)更好，但是要看個(gè)人能力而定。既然不能學(xué)復(fù)雜的內(nèi)容，那就吸收點(diǎn)有用的東西讓程序提升吧，一定要養(yǎng)成很好的品味，有好壞的算法之分，這點(diǎn)很重要。
- 多久能看完？不要指望很快看完。
- 應(yīng)該買中文版還是英文版？英文教材和課程其實(shí)學(xué)起來還是有點(diǎn)難度，所以大家根據(jù)自己需要和能力范圍選擇購買中文版或英文版。
- 寫程序的態(tài)度應(yīng)該如何？盡量少寫低效的算法，甚至于低效的程序，要盡量提高程序的性能。
《算法》第4版，幫助你在平常而又不平凡的程序設(shè)計(jì)里找到更多樂趣！
