5
王曉華是一位熱衷于算法研究的程序員，也是《算法的樂趣》一書的作者。他目前在中興通訊上海研發(fā)中心從事光纖接入網(wǎng)通訊設(shè)備開發(fā)，擔(dān)任EPON（以太網(wǎng)無源光網(wǎng)絡(luò)）業(yè)務(wù)軟件開發(fā)經(jīng)理，參與開發(fā)的PON設(shè)備在全球部署過億線，為數(shù)億家庭提供寬帶接入服務(wù)。
對于算法，王曉華更愿意稱自己是在“玩”，“玩算法”最大的樂趣就是用程序解決生活中的問題。當(dāng)年為了方便使用Visual Studio 6.0開發(fā)軟件，他特意編寫了一個(gè)tabbar插件，并隨后開源了這個(gè)軟件。為了文檔安全，他開發(fā)了一個(gè)基于layerFSD技術(shù)的透明文件加密系統(tǒng)，在朋友圈內(nèi)廣為流傳。后來他在使用Source Insight軟件的時(shí)候，又以外掛的形式為Source Insight開發(fā)了TabSiPlus插件，受到了很多程序員朋友的歡迎。
關(guān)于算法該怎么“玩”，王曉華自有多年的經(jīng)驗(yàn)分享：
為了玩游戲而開始的算法之旅
從上大學(xué)時(shí)候開始，我迷上了算法。那時(shí)候，像我這樣的懶人覺得拼音輸入法太繁瑣，于是就去學(xué)“表形碼”（當(dāng)然，因?yàn)楸康脑颍F(xiàn)在還在用拼音輸入法）。資深一點(diǎn)的游戲玩家都還記得，那個(gè)時(shí)候?yàn)榱送嬷形腄OS游戲，很多人都裝了UCDOS中文環(huán)境，UCDOS沒有表形碼，但是支持通過碼表文件增加自定義輸入法。我研究了Windows上的表形碼碼表文件（老師給的，適用于Windows 3.x版本）和UCDOS碼表文件的格式，發(fā)現(xiàn)二者有一定的相似性：都是文本文件，有固定的格式，每一行由一組編碼和一個(gè)字或詞組成一個(gè)編碼對。二者的區(qū)別僅僅在于一個(gè)文件是編碼在前，對應(yīng)的字或詞在后面，另一個(gè)剛好相反，字或詞在前，對應(yīng)的編碼在后面。碼表文件有十幾萬行，手工修改是不可能了，剛好當(dāng)時(shí)在上C語言課，就決定寫個(gè)程序來做這個(gè)事情。
神奇的表形碼
第一次運(yùn)行我寫的程序，十幾秒鐘都沒有結(jié)束。因?yàn)槲抑皩懙腃語言作業(yè)，從來沒有哪個(gè)程序運(yùn)行時(shí)間超過1秒鐘的，所以我覺得這個(gè)程序掛了，于是我就“Ctrl+Break”了。但是分析代碼又覺得沒有問題，看了遺留在磁盤上的碼表文件，發(fā)現(xiàn)轉(zhuǎn)換了幾千行，并且內(nèi)容是對的。于是再次運(yùn)行程序，等了2－3分鐘，程序結(jié)束了。我急不可待地將得到的碼表文件導(dǎo)入U(xiǎn)CDOS，發(fā)現(xiàn)可以用，當(dāng)時(shí)就感覺非常有成就感。這是我第一次為解決一個(gè)實(shí)際的問題編寫算法，盡管當(dāng)時(shí)還沒有算法、軟件的概念，但是隱隱約約就覺得這東西有用，不是只用于完成作業(yè)，還可以解決實(shí)際的問題。后來我接觸到了更多的有用算法以及各種算法競賽，一直到現(xiàn)在，寫個(gè)程序解決問題幾乎成了一種習(xí)慣。
學(xué)習(xí)算法難在哪里？
許多算法是有難度的，理論很復(fù)雜，不容易理解和掌握，這是客觀存在的現(xiàn)實(shí)。但是我們可以通過提高自身分析問題和解決問題的能力來相對地降低學(xué)習(xí)難度。從基礎(chǔ)來講，要深入理解數(shù)據(jù)結(jié)構(gòu)，至少要非常熟練地掌握一種排序算法，各種線性表的插入、刪除算法，樹的遍歷和插入、刪除算法，圖的遍歷算法等等。然后要多學(xué)習(xí)，掌握一些常見問題的解決模式，比如窮舉算法如何應(yīng)用，動(dòng)態(tài)規(guī)劃算法如何應(yīng)用等等。最后要勤思考，對應(yīng)已經(jīng)掌握并解決的算法，要想想為什么用這種方法解決，有沒有其他方法，類似的問題怎么辦，提高舉一反三的能力。
想學(xué)好計(jì)算機(jī)算法，數(shù)學(xué)問題是無法回避的。數(shù)學(xué)的重要性不在于算法中用了哪些公式或數(shù)學(xué)原理，其重要性在于一種思維方式的培養(yǎng)。當(dāng)我們遇到一個(gè)新的問題的時(shí)候，通常有兩種解決問題的方式，一種方式是創(chuàng)造一種新的方法來解決這個(gè)問題，另一種方式是將新問題分解、轉(zhuǎn)化成已知問題，然后用已知的方法解決這個(gè)問題。這兩種方式都很需要抽象思維能力，現(xiàn)實(shí)生活中很少有機(jī)會鍛煉抽象思維能力，而學(xué)習(xí)數(shù)學(xué)是一種很好地培養(yǎng)這種能力的方法。但是并不是說要學(xué)好算法就必需成為數(shù)學(xué)大咖，而是通過學(xué)習(xí)數(shù)學(xué)促進(jìn)抽象思維能力的提高。
算法設(shè)計(jì)又難在何處？
參加算法競賽其實(shí)是一件很痛苦的事情，要經(jīng)過大量的訓(xùn)練，很多人會選擇背一些算法或整理一些算法模板，到時(shí)候可以直接套用。在理解算法的基礎(chǔ)上熟記一些經(jīng)典的算法實(shí)現(xiàn)其實(shí)也是一件無可厚非的事情，我上學(xué)的時(shí)候也參加過一些比賽，通常在比賽之前也會突擊訓(xùn)練一兩個(gè)月，背很多東西，基本上也是事后一個(gè)月就全忘了。
比賽的題目一般都有特定的套路，但是現(xiàn)實(shí)生活中的算法往往就事而論，有可能只有你遇到過，沒有現(xiàn)成的經(jīng)驗(yàn)，需要自己從無到有來解決問題。我認(rèn)為算法設(shè)計(jì)有三個(gè)方面需要強(qiáng)調(diào)：模型的建立、演化算法和輸入、輸出的轉(zhuǎn)換。這三個(gè)方面中模型的建立是關(guān)鍵，很多情況下，模型建好了，演化算法和輸入、輸出的轉(zhuǎn)換就水到渠成。
建立模型的基礎(chǔ)是數(shù)據(jù)結(jié)構(gòu)。當(dāng)一個(gè)問題的數(shù)據(jù)存在先進(jìn)先出的特性時(shí)，你要想到隊(duì)列。當(dāng)一個(gè)問題的數(shù)據(jù)需要頻繁查找操作時(shí)，你要想到有序表、hash、map。當(dāng)一個(gè)問題的數(shù)據(jù)需要頻繁的插入、刪除操作時(shí)，你要想到鏈表。當(dāng)一個(gè)問題中的數(shù)據(jù)包含父子關(guān)系時(shí)，你要想到樹。當(dāng)一個(gè)問題中的數(shù)據(jù)中既有節(jié)點(diǎn)又有路徑什么的，你要想到圖。這些都和使用數(shù)據(jù)結(jié)構(gòu)的經(jīng)驗(yàn)有關(guān)，只要多練習(xí)就能掌握。
建立模型還需要抽象的邏輯思維能力。簡單地說，就是運(yùn)用抽象的邏輯思維，抓住問題的主要因素，忽略次要因素，建立問題的框架。
算法設(shè)計(jì)之難體現(xiàn)在思維方式的轉(zhuǎn)換和模型的建立。前面說過，這需要有抽象思維能力，缺乏這種能力，連問題都很難想明白，更不用說設(shè)計(jì)解決問題的算法了。幸運(yùn)的是這種能力是可以培養(yǎng)的，學(xué)好數(shù)學(xué)，多研究一些算法，積累些經(jīng)驗(yàn)，都是很好的提高抽象思維能力的方法。
算法學(xué)習(xí)的干貨推薦
在我學(xué)習(xí)算法的過程中，興趣是最大的推動(dòng)力。興趣來自于我覺得這東西能解決問題，對自己有用。我在策劃《算法的樂趣》這本書的時(shí)候，我依然沿用了這種思想。我選取、介紹的例子都是大家生活中沒有在意，但是卻處處都會遇到的算法，通過這些例子讓大家覺得算法是有用的，并通過這個(gè)來吸引大家關(guān)注算法，學(xué)習(xí)算法，從而達(dá)到提高能力的作用。
算法學(xué)習(xí)是一條并不簡單的路，就我的經(jīng)驗(yàn)而言，在計(jì)算機(jī)上學(xué)習(xí)算法首先需要熟悉編程語言和數(shù)據(jù)結(jié)構(gòu)，關(guān)于編程語言和數(shù)據(jù)結(jié)構(gòu)有很多經(jīng)典的書籍，我就不多介紹了。就算法而言，我看過的書有Cormen的《算法導(dǎo)論》、Knuth的《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》、Weiss的《數(shù)據(jù)結(jié)構(gòu)與算法分析》、Levitin的《算法設(shè)計(jì)與分析基礎(chǔ)》、Kleigberg的《算法設(shè)計(jì)》等等。想?yún)⒓铀惴ǜ傎惖耐瑢W(xué)可以參考劉汝佳等人編寫的《算法藝術(shù)與信息學(xué)競賽》，以及《ACM國際大學(xué)生程序設(shè)計(jì)競賽題解》。因?yàn)闀r(shí)間過去太久了，已經(jīng)不記得看這些書的順序了，只記得最早看的是《算法導(dǎo)論》，關(guān)于順序?qū)嵲跊]有什么經(jīng)驗(yàn)可談。
至于如何讀這些算法的經(jīng)典書籍，我倒是有一些經(jīng)驗(yàn)和大家分享：
不管哪一本書，都不要泛泛地看一遍就覺得看懂了，而是要把書中的每一個(gè)例子算法都用程序?qū)懗鰜?，這樣才能留下深刻的印象。如果遇到看不懂的地方，不要停下來，跳過去看其他算法，過幾天在回頭來看，如果還看不懂就再過幾天再回頭來看。千萬不要在一個(gè)地方停下來，否則你很可能就此失去興趣，恐怕永遠(yuǎn)也看不完這本書了。
此外，還有一些學(xué)習(xí)算法的網(wǎng)站值得推薦：
游戲開發(fā)相關(guān)的算法介紹：
http://theory.stanford.edu/~amitp/GameProgramming
俄羅斯方塊游戲的算法網(wǎng)站：
http://gforge.inria.fr/projects/mdptetris
http://colinfahey.com/tetris/tetris.html
leetcode，最近很火的算法網(wǎng)站：
Topcoder，也很經(jīng)典，每周都有競賽，有獎(jiǎng)金的：
http://community.topcoder.com/tc
還有很多大學(xué)也有自己的競賽題庫，比如北大、杭電和華中科技大學(xué)等等。
編程算法、推薦算法、數(shù)據(jù)挖掘涉及的算法的區(qū)別和聯(lián)系？
編程算法應(yīng)該只是算法的一種表達(dá)形式，我們還可以用表格或流程圖來表達(dá)算法。數(shù)據(jù)挖掘領(lǐng)域涉及的算法和其他領(lǐng)域的算法并無本質(zhì)的區(qū)別，只是問題域不同。數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)常用的方法，比如決策樹、貝葉斯學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、遺傳算法等等，在其他領(lǐng)域也都是有應(yīng)用的。神經(jīng)網(wǎng)絡(luò)、遺傳算法作為啟發(fā)性搜索算法在人工智能和最優(yōu)化求解領(lǐng)域也得到了廣泛應(yīng)用。貝葉斯學(xué)習(xí)在一些電子郵件應(yīng)用程序中也有應(yīng)用，主要用于垃圾郵件的識別。在人工智能領(lǐng)域或各種專家系統(tǒng)中，決策樹算法也是常用算法。各種算法之間的聯(lián)系還是很普遍的，在不同的領(lǐng)域扮演著不同的角色，本質(zhì)上沒有區(qū)別。
在日常生活中，我們有機(jī)會見到越來越多的推薦算法，我曾經(jīng)想買一個(gè)佳能鏡頭，于是用了一下百度，想了解幾種鏡頭的評價(jià)，結(jié)果一連幾天，只要登錄京東或淘寶，首頁都會給我推薦與數(shù)碼相機(jī)有關(guān)的配件或鏡頭信息。因?yàn)楣ぷ黝I(lǐng)域的原因，我對推薦算法沒有深入的研究，我認(rèn)為這種算法應(yīng)該主要是建立在大數(shù)據(jù)上的數(shù)據(jù)分類、篩選和過濾。不過就我對算法的理解來說，目前的推薦算法還是有改進(jìn)余地的，比如要能區(qū)分同一臺計(jì)算機(jī)的不同使用者，不要在我用電腦的時(shí)候向我推薦女式內(nèi)衣和化妝品，那是我老婆關(guān)注的東西。（笑）
生活中處處有算法
應(yīng)該說，在我的工作和生活中也是處處都有算法。說到網(wǎng)絡(luò)協(xié)議，TCP協(xié)議中的“滑動(dòng)窗口算法”也是很經(jīng)典的算法。路由器和交換機(jī)中為了避免出現(xiàn)端口環(huán)路，都會使用最小生成樹算法。在接入網(wǎng)設(shè)備中，通常語音報(bào)文的優(yōu)先級高于視頻報(bào)文，視頻報(bào)文的優(yōu)先級又高于一般的數(shù)據(jù)報(bào)文，當(dāng)一大波各種報(bào)文來臨時(shí)，設(shè)備如何處理？這個(gè)算法也很經(jīng)典，就是用多個(gè)隊(duì)列加上一個(gè)調(diào)度算法，簡單說就是六個(gè)字：分分類，排排隊(duì)。
隨著寬帶的普及，現(xiàn)在幾乎家家都有路由器，很多人都會在路由器上給各個(gè)端口配置帶寬，這就會用到帶寬分配算法，令牌算法和Max-Min Fairness帶寬分配算法都是經(jīng)典的帶寬分配算法。網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)報(bào)文出了錯(cuò)碼怎么辦？那就要糾錯(cuò)，Reed-Solomon編碼和解碼算法就是這樣的經(jīng)典糾錯(cuò)算法，除此之外，Reed-Solomon編碼和解碼算法還用于光盤、磁盤的數(shù)據(jù)糾錯(cuò)。
說實(shí)話，我曾經(jīng)“玩”過的算法，絕大多數(shù)都沒有機(jī)會直接應(yīng)用到工作當(dāng)中，但是“玩”算法對我的影響是顯而易見的，它提高了我的動(dòng)手能力，以及遇到問題時(shí)分析并解決問題能力，這就是收獲，也是任何一個(gè)軟件企業(yè)對程序員最基本的要求。
雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
