(上) 混沌篇
教材選用
2004年的春天, 我開始講授數(shù)據(jù)結(jié)構(gòu)這門課程. 雖然那會已經(jīng)不是第一次上講臺, 但講這門課時感覺完全是陌生的, 后來想想原因大概在于教材吧.
上學(xué)的時候用的是嚴(yán)蔚敏老師的《數(shù)據(jù)結(jié)構(gòu)》(綠皮Pascal版), 這本書流傳甚廣而且影響巨大(后期改了C語言版同樣熱銷). 由于在語言上的偏好, 我當(dāng)時想用C++版來講授這門課程, 所以選用了殷人昆老師的《數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅcC++描述)》這本書. 事實上, 當(dāng)時C++代表了“先進”的生產(chǎn)力, 人們對它趨之若鶩. 另外, 殷老師的這本書在當(dāng)年還算比較新, 而且內(nèi)容嘗試很大膽, 不過里面有些疏漏給教學(xué)或多或少地帶來了不便(后來的第2版改進了很多).
說到這里, 不能不提Horowitz和Sahni的《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》這本書, 它給我的感覺就是講了很多內(nèi)容, 特別龐雜, 但似乎不能讓讀者明白真義所在. 在Horowitz和Sahni寫作的年代, 數(shù)據(jù)結(jié)構(gòu)的研究只能算是剛起步, 還沒有系統(tǒng)性地整理并用于教學(xué), 所以會有東一榔頭西一棒的感覺. 其實, 核心的問題是: 我們這門課程究竟應(yīng)該學(xué)哪些內(nèi)容? 但是, 在那個年代沒有辦法交代地特別清楚.
有人會問, 為什么不選外版教材呢? 一方面當(dāng)時的環(huán)境還不太普及, 例如《算法導(dǎo)論》的影印版2002年才正式引入國內(nèi), 而且引進的優(yōu)秀外版教材不是特別多.[1] 另一方面就是學(xué)生還是喜歡中文教材, 這一點至今如是. 所以, 發(fā)展本版教材是非常重要的.
開發(fā)環(huán)境
2004年那會在學(xué)校用的比較多的還是Visual C++ 6.0, 里面的坑不少, 對C++98的標(biāo)準(zhǔn)支持也不是很理想. 現(xiàn)在一晃而過, 出了很多新鮮的工具, 比如Clang. 而且現(xiàn)在連Visual Studio 2017都發(fā)布了.
不過, 說實話那個年代的STL確實不太成熟, 換gcc也好不到哪里去. 而且考慮到學(xué)生的實際情況, 還是微軟系列的相對比較方便一些. 現(xiàn)在我會要求學(xué)生在筆記本上安裝Visual Studio 2015的社區(qū)版, 如果電腦配置不行的話, 可以換一個比較低的版本例如Visual Studio 2013. 這樣可以方便地支持C++11, 不過回想當(dāng)年真是困難重重.
學(xué)習(xí)筆記
值得欣慰的是, 當(dāng)年的學(xué)生很有韌性, 非常認(rèn)真地在學(xué)習(xí)這門課程. 據(jù)說某位認(rèn)真聽課的同學(xué)把我講的話全部記錄下來了, 整整寫滿了三個大筆記本. 其實我特別好奇這位同學(xué)都記了些什么, 現(xiàn)在要是能看看, 也許能回憶起不少過去的時光.
說到這里, 我想額外多說幾句. 記筆記無論是手寫茬底、iPad/Surface Pro記錄抑或是LaTeX錄入(前提要有一定的手速, 而且要求對LaTeX比較熟練), 都是不錯的. 因為在記筆記的過程中是一種頭腦的讀入, 這可比手機拍下來要強多了. 許多人覺得拍下來就是自己掌握了, 其實很可能永遠(yuǎn)躺在手機相冊里再也不看了.
STL
非常幸運地是, 清華大學(xué)出版社當(dāng)時影印并且翻譯了Ford和Topp的那本《數(shù)據(jù)結(jié)構(gòu)——C++語言描述：應(yīng)用標(biāo)準(zhǔn)模板庫(STL)》. 這本書所指引的思路非常正確, 就是一開始從STL入手學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu), 并且充分利用已經(jīng)有的結(jié)果來搭建一個比較的程序. 然后我們再去學(xué)習(xí)新的知識, 比如STL的內(nèi)部構(gòu)造. 這樣的方案在STL不是很成熟的時候確實有很大的風(fēng)險, 比如那時候的STL沒有將散列納入標(biāo)準(zhǔn), 所以只能用Plauger實現(xiàn)的hash_map. 事實上, 那個時代的C++也不是很成熟, 為了求證一個問題, 我專門給C++ Primer的作者Lippman發(fā)了郵件, 他坦承那是編譯器尚不支持的功能.
Ford和Topp的這本書很厚, 直接用于教學(xué)不太方便. 為了讓同學(xué)們能夠充分吸取其中的思想, 我編寫了一本名為《算法與數(shù)據(jù)結(jié)構(gòu)補充教材》的小冊子, 專門講解STL中各種容器的基本使用方案. 這本小冊子大概只有60多頁, 但是足夠大家使用了. 現(xiàn)在回過頭來看, Ford和Topp的這本書里面有很多不甚專業(yè)的地方, 有些講解也不夠嚴(yán)謹(jǐn), 但它確實是一本還算不錯的書.
備課講義
從備課的角度看, 第一次在筆記本上手寫講義比較合適. 人在思考的時候用手寫筆記會比較適應(yīng), 也能夠全身心投入問題的本質(zhì)而不是去考慮錄入公式之類的問題. 但講完第一次之后我發(fā)現(xiàn)了這種模式的問題——后續(xù)的修改非常麻煩. 于是第二次上課的時候我就開始全面投向電子講義, 不過用的是Word來記錄, 這也是一個非常大的坑(主要是它太“智能”了).
電子講義的好處就是可以無限提升和改進, 這點非常方便. 但是在修改的過程中逐漸發(fā)現(xiàn)Word的各種不便, 而且公式也不是很好看, 于是我開始投向LaTeX的懷抱. 說起來很多美國大學(xué)讓學(xué)生入學(xué)的時候就使用LaTeX來提交筆記和作業(yè), 這點我現(xiàn)在非常贊同. 因為對于學(xué)術(shù)寫作來說, LaTeX是必須掌握的技能點. 由于條件所限, 我不能強制要求現(xiàn)在學(xué)生都使用它, 但希望大家特別是還在上學(xué)的同學(xué)們都去學(xué)習(xí)和掌握LaTeX. 雖然學(xué)習(xí)曲線有點陡峭, 但是你會發(fā)現(xiàn)漂亮的排版會激發(fā)你繼續(xù)前行.
我現(xiàn)在上課會用一款Typora的軟件, 完美支持MarkDown和LaTeX公式. 很多公式利用它能夠快速展現(xiàn)在屏幕上, 而且可以保留下來放到下一次課程繼續(xù)改進. 想像一下, 鍵入幾個符號就能出現(xiàn)清晰的數(shù)學(xué)公式, 比在黑板上手寫公式要方便多了(不過需要苦練LaTeX和手速). 如果有興趣的朋友, 不妨試試這款軟件, 效果無比驚艷......
故事開始
說了很多廢話, 這篇卻要結(jié)束了. 實際上, 正是《算法與數(shù)據(jù)結(jié)構(gòu)補充教材》和這些不斷改善的講義, 才揭開了《面向算法設(shè)計的數(shù)據(jù)結(jié)構(gòu)(C++語言版)》的漫漫征程......
(中) 頓悟篇
綱舉目張
很多年前流傳著一本叫《現(xiàn)代計算機常用數(shù)據(jù)結(jié)構(gòu)和算法》的黑皮書, 譯者是南京大學(xué)的潘金貴老師等人. 雖然由于時代所限, 導(dǎo)致這本書沒有版權(quán), 但起到了傳播交流的巨大貢獻. 后來大家知道了, 這就是傳說中的《算法導(dǎo)論》啊! 從譯名可以看出, 我們的認(rèn)知停留在數(shù)據(jù)結(jié)構(gòu)與算法這個層面. 很多人不明白, 這本《算法導(dǎo)論》里面為什么書名不體現(xiàn)數(shù)據(jù)結(jié)構(gòu)但又講很多數(shù)據(jù)結(jié)構(gòu)呢? 這種組織似乎非常讓人不解.
我個人認(rèn)為, 《算法導(dǎo)論》中對數(shù)據(jù)結(jié)構(gòu)中的態(tài)度非常明確, 作者的思路就是: 數(shù)據(jù)結(jié)構(gòu)要服務(wù)于算法, 否則就是屠龍之術(shù), 應(yīng)該摒棄. 例如圖算法它只給出常用的鄰接矩陣和鄰接表, 那些各種應(yīng)該退出歷史舞臺的結(jié)構(gòu)完全不講. 這樣一來, 整個思路就非常明晰了.
集合
那么如何將這些跨入到數(shù)據(jù)結(jié)構(gòu)課程呢. 關(guān)鍵點在于抽象數(shù)據(jù)類型, 而最關(guān)鍵的一點就是集合這個抽象數(shù)據(jù)類型, 它包含如下操作:
- 查找. 在集合中查找元素k.
- 插入. 在集合中插入元素k.
- 刪除. 在集合中插入元素k.
- 最小元. 返回集合的最小元素.
- 最大元. 返回集合的最大元素.
- 下一元素. 返回比k大的最小元素.
- 上一元素. 返回比k小的最大元素.
通過這些操作我們可以構(gòu)造出許多完整的程序, 而不同的程序需要不同的側(cè)重點, 例如側(cè)重于查找的集合或側(cè)重于最大元的集合. 《算法導(dǎo)論》對此表述地很明確, 專門放在數(shù)據(jù)結(jié)構(gòu)部分的引言部分, 開宗明義地闡述了作者的思想.
種類
更具體的教學(xué)內(nèi)容到底應(yīng)該是哪些呢? Robert E. Tarjan在其名作《數(shù)據(jù)結(jié)構(gòu)與網(wǎng)絡(luò)算法》(Data structures and network algorithms)中給出了非常精辟的總結(jié):
- 區(qū)間: 包括數(shù)組/向量, 其特點是以O(1)時間訪問元素. 注意區(qū)間的下標(biāo)可以雙向延伸, 也即這里可能存在負(fù)數(shù)下標(biāo).
- 列表: 包含鏈辫愉、棧和隊列. 這三種看似簡單的抽象數(shù)據(jù)類型在圖算法中的應(yīng)用可謂是精彩紛呈.
- 集合: 不一定有序關(guān)系, 以查找為主, 可用散列實現(xiàn). 《算法導(dǎo)論》上稱此為字典.
- 映射: 定義于全序集, 有最小和最大元素, 可用查找樹實現(xiàn). 此外映射還可引出優(yōu)先級隊列.
另外安利一下, Tarjan這位算法大宗師的書雖然薄薄一本, 但實在是微言大義, 值得深入閱讀.
書名之疑
另外有一本書也對我起到了比較深遠(yuǎn)的影響, 那就是Weiss的《數(shù)據(jù)結(jié)構(gòu)與算法分析》(Data Structures and Algorithm Analysis), 可能有些人對這本書的名字感到困惑, 為什么數(shù)據(jù)結(jié)構(gòu)要和算法分析掛鉤呢?
實際上, 作者的用意就是數(shù)據(jù)結(jié)構(gòu)必須以算法分析為導(dǎo)向. 我們選擇一種數(shù)據(jù)結(jié)構(gòu), 最關(guān)鍵的是看能否滿足整個程序的需求, 而其中的準(zhǔn)則就是算法分析結(jié)果. 是好是壞, 都由算法分析說了算, 這點撐起了整本書的結(jié)構(gòu). 事實上, Weiss的這一系列書有多個語言版本, 一直都是熱銷的教材. 我想, 這和作者的整體思路有很大的關(guān)系.
想了很久, 最終給自己的書定名為《面向算法設(shè)計的數(shù)據(jù)結(jié)構(gòu)》.
寫作思路
有了上述幾座燈塔的指引, 我也逐漸為自己的講義定出了方向:
基于抽象數(shù)據(jù)類型的觀點講解數(shù)據(jù)結(jié)構(gòu), 以算法分析為導(dǎo)向, 以算法效率為準(zhǔn)繩, 著墨于抽象數(shù)據(jù)類型的選擇悟狱、使用和組合, 從而實現(xiàn)提升算法性能的終極目標(biāo).
落到實處就是將STL的使用作為首位, 盡量與
C++11標(biāo)準(zhǔn)靠攏, 提倡拿來主義少造輪子, 力爭快速構(gòu)建可用程序.
在草稿逐漸積累的時候, 清華大學(xué)出版社的龍啟銘先生和我商談了這本書的出版事宜. 雖然非常迅速地完成了簽約工作, 不過由于我的拖延癥和一些事情, 遲遲未能交稿. 這時候, 啟銘兄經(jīng)常激勵和鞭策我, 讓我最終將這本書呈現(xiàn)在大家面前.
另外, 由于我的完美主義傾向, 總想把書修訂地非常完善. 后來發(fā)現(xiàn)這是一個不可能完成的任務(wù), 與其這樣還不如在一定階段推出一個版本, 今后再逐漸迭代更新. 事實證明, 這樣做非常明智.
(下) 進化篇
《面向算法設(shè)計的數(shù)據(jù)結(jié)構(gòu)(C++語言版)》自從2015年12月出版以來, 得到了很多非常有益的反饋, 這為下一版的改進提供了很好的思路. 特別是2016年我開了微博(現(xiàn)在更名為@算法時空)之后, 在與各界人士互相交流的過程中, 更是發(fā)現(xiàn)了這本書的種種不足.
libc++
目前標(biāo)準(zhǔn)庫實現(xiàn)中邏輯性和可讀性最好的當(dāng)屬LLVM的libc++, 當(dāng)然大家也都知道Clang, 具體它們的關(guān)系我也不細(xì)說了. 本書下一版將考慮講解一些libc++的實現(xiàn), 讓大家可以多接觸到這種業(yè)界頂級的源代碼.
更多容器
由于寫作時間所限, 第1版里沒有講到一大類容器, 也就是unordered系列(unordered_set, unordered_map, unordered_multiset, unordered_multimap). 這也是本書的一大遺憾, 我們在第2版將介紹這些容器. 實際上, 它們的平均表現(xiàn)很好, 但也有可能在最壞情況下極差. 讀者一定不要只看它們的優(yōu)點, 也要多甄別選用.
代碼優(yōu)化
下一版會引入更多優(yōu)化實例, 比如在遞歸中會講解qsort函數(shù), 它對于遞歸的優(yōu)化相當(dāng)好, 非常值得一讀. 更重要的是, 我們將會在書中更強調(diào)STL的使用而不是自己編寫函數(shù), 盡可能像樂高積木一樣用STL搭建出復(fù)雜的系統(tǒng), 這樣性能更好也更簡潔.
極限性能
我們將會展示更多極限情況下的性能, 而不是一些非常簡單的例子. 比如, 可以讓讀者嘗試將自己的內(nèi)存用量壓榨到極致, 看看會有什么變化. 而這些鮮活的實例正是教學(xué)所需要的, 也是學(xué)習(xí)者所感興趣的話題. 實際上, 這有點數(shù)據(jù)庫壓力測試的意思, 從這里我們也可以看到并且驚嘆于STL的抗壓能力.
算法應(yīng)用
我們考慮展示更多數(shù)據(jù)結(jié)構(gòu)在算法中的應(yīng)用, 特別是引入高效數(shù)據(jù)結(jié)構(gòu)之后算法性能發(fā)生顯著變化的實例. 只有通過這些實實在在的例子, 才能讓學(xué)習(xí)者感受到數(shù)據(jù)結(jié)構(gòu)之妙. 事實上, 寫作本書的目的也是為了配合后續(xù)進階算法課程的需要, 希望能讓這本書成為學(xué)習(xí)《算法導(dǎo)論》和《算法設(shè)計》的一個良好鋪墊, 能讓大家順利學(xué)好更深入的算法設(shè)計的技術(shù).
建議
歡迎讀過本書的朋友們在本篇文章下寫留言, 寫出你們的意見和建議. 我會在第2版中加以改進和完善.
-
不過順便八卦一下, 如果你手里有《算法導(dǎo)論》影印版的話, 可以看到封底有個“線性編程”一直沒改為正確的“線性規(guī)劃”. ?
