學習數據結構與算法分析如何幫助您成為更優秀的開發人員
"相較于其它方式，我一直熱衷于推崇圍繞數據設計代碼，我想這也是Git能夠如此成功的一大原因[…]在我看來，區別程序員優劣的一大標準就在于他是否認為自己設計的代碼還是數據結構更為重要。"
-- Linus Torvalds
"優秀的數據結構與簡陋的代碼組合遠比反之的組合更好。"
-- Eric S. Raymond, The Cathedral and The Bazaar
學習數據結構與算法分析會讓您成為一名出色的程序員。
數據結構與算法分析是一種解決問題的思維模式。 在您的個人知識庫中，數據結構與算法分析的相關知識儲備越多，您將越多具備應對并解決各類繁雜問題的能力。掌握了這種思維模式，您還將有能力針對新問題提出更多以前想不到的漂亮的解決方案。
您將更深入地了解，計算機如何完成各項操作。無論您是否是直接使用給定的算法，它都影響著您作出的各種技術決定。從計算機操作系統的內存分配到RDBMS的內在工作機制，以及網絡協議如何實現將數據從地球的一個角落發送至另一個角落，這些大大小小的工作的完成，都離不開基礎的數據結構與算法，理解并掌握它將會讓您更了解計算機的運作機理。
對算法廣泛深入的學習能為您儲備解決方案來應對大體系的問題。之前建模困難時遇到的問題如今通常都能融合進經典的數據結構中得到很好地解決。即使是最基礎的數據結構，只要對它進行足夠深入的鉆研，您將會發現在每天的編程任務中都能經常用到這些知識。
有了這種思維模式，在遇到磨棱兩可的問題時，您將能夠想出新奇的解決方案。即使最初并沒有打算用數據結構與算法解決相應問題的情況，當真正用它們解決這些問題時您會發現它們將非常有用。要意識到這一點，您至少要對數據結構與算法分析的基礎知識有深入直觀的認識。
理論認識就講到這里，讓我們一起看看下面幾個例子。
最短路徑問題
我們想要開發一個軟件來計算從一個國際機場出發到另一個國際機場的最短距離。假設我們受限于以下路線：
從這張畫出機場各自之間的距離以及目的地的圖中，我們如何才能找到最短距離，比方說從赫爾辛基到倫敦？Dijkstra算法是能讓我們在最短的時間得到正確答案的適用算法。
在所有可能的解法中，如果您曾經遇到過這類問題，知道可以用Dijkstra算法求解，您大可不必從零開始實現它，只需知道該算法的代碼庫能幫助您解決相關的實現問題。
如果你深入到該算法的實現中，您將深入理解一項著名的重要圖論算法。您會發現實際上該算法比較消耗資源，因此名為A*的擴展經常用于代替該算法。這個算法應用廣泛，從機器人尋路的功能實現到TCP數據包路由，以及GPS尋徑問題都能應用到這個算法。
先后排序問題
您想要在開放式在線課程平臺上(如Udemy或Khan學院)學習某課程，有些課程之間彼此依賴。例如，用戶學習牛頓力學課程前必須先修微積分課程，課程之間可以有多種依賴關系。用YAML表述舉例如下：
# Mapping from course name to requirements
#
# If you're a physcist or a mathematicisn and you're reading this, sincere
# apologies for the completely made-up dependency tree :)
courses:
arithmetic: []
algebra: [arithmetic]
trigonometry: [algebra]
calculus: [algebra, trigonometry]
geometry: [algebra]
mechanics: [calculus, trigonometry]
atomic_physics: [mechanics, calculus]
electromagnetism: [calculus, atomic_physics]
radioactivity: [algebra, atomic_physics]
astrophysics: [radioactivity, calculus]
quantumn_mechanics: [atomic_physics, radioactivity, calculus] 鑒于以上這些依賴關系，作為一名用戶，我希望系統能幫我列出必修課列表，讓我在之后可以選擇任意一門課程學習。如果我選擇了微積分（calculus）課程，我希望系統能返回以下列表：
arithmetic -> algebra -> trigonometry -> calculus 這里有兩個潛在的重要約束條件：
- 返回的必修課列表中，每門課都與下一門課存在依賴關系
- 我們不希望列表中有任何重復課程
這是解決數據間依賴關系的例子，解決該問題的排序算法稱作拓撲排序算法。它適用于解決上述我們用YAML列出的依賴關系圖的情況，以下是在圖中顯示的相關結果(其中箭頭代表需要先修的課程):
拓撲排序算法的實現就是從如上所示的圖中找到滿足各層次要求的依賴關系。因此如果我們只列出包含radioactivity和與它有依賴關系的子圖，運行tsort排序，會得到如下的順序表：
arithmetic
algebra
trigonometry
calculus
mechanics
atomic_physics
radioactivity 這符合我們上面描述的需求，用戶只需選出radioactivity，就能得到在此之前所有必修課程的有序列表。
在運用該排序算法之前，我們甚至不需要深入了解算法的實現細節。一般來說，你可能選擇的各種編程語言在其標準庫中都會有相應的算法實現。即使最壞的情況，Unix也會默認安裝tsort程序，運行man tsort 來了解該程序。
其它拓撲排序適用場合
- 類似
make的工具 可以讓您聲明任務之間的依賴關系，這里拓撲排序算法將從底層實現具有依賴關系的任務順序執行的功能。 - 具有
require指令的編程語言適用于要運行當前文件需先運行另一個文件的情況。這里拓撲排序用于識別文件運行順序以保證每個文件只加載一次，且滿足所有文件間的依賴關系要求。 - 帶有甘特圖的項目管理工具。甘特圖能直觀列出給定任務的所有依賴關系，在這些依賴關系之上能提供給用戶任務完成的預估時間。我不常用到甘特圖，但這些繪制甘特圖的工具很可能會用到拓撲排序算法。
霍夫曼編碼實現數據壓縮
霍夫曼編碼是一種用于無損數據壓縮的編碼算法。它的工作原理是先分析要壓縮的數據，再為每個字符創建一個二進制編碼。字符出現的越頻繁，編碼賦值越小。因此在一個數據集中e可能會編碼為111，而x會編碼為10010。創建了這種編碼模式，就可以串聯無定界符，也能正確地進行解碼。
在gzip中使用的DEFLATE算法就結合了霍夫曼編碼與LZ77一同用于實現數據壓縮功能。gzip應用領域很廣，特別適用于文件壓縮(以.gz為擴展名的文件)以及用于數據傳輸中的http請求與應答。
學會實現并使用霍夫曼編碼有如下益處：
- 您會理解為什么較大的壓縮文件會獲得較好的整體壓縮效果(如壓縮的越多，壓縮率也越高)。這也是SPDY協議得以推崇的原因之一：在復雜的HTTP請求/響應過程數據有更好的壓縮效果。
- 您會了解數據傳輸過程中如果想要壓縮JavaScript/CSS文件，運行壓縮軟件是完全沒有意義的。PNG文件也是類似，因為它們已經使用DEFLATE算法完成了壓縮。
- 如果您試圖強行破譯加密的信息，您可能會發現由于重復數據壓縮質量更好，密文給定位的數據壓縮率將幫助您確定相關的分組密碼工作模式。
下一步選擇學習什么是困難的
作為一名程序員應當做好持續學習的準備。為了成為一名web開發人員，您需要了解標記語言以及Ruby/Python、正則表達式、SQL、JavaScript等高級編程語言，還需要了解HTTP的工作原理，如何運行UNIX終端以及面向對象的編程藝術。您很難有效地預覽到未來的職業全景，因此選擇下一步要學習哪些知識是困難的。
我沒有快速學習的能力，因此我不得不在時間花費上非常謹慎。我希望盡可能地學習到有持久生命力的技能，即不會在幾年內就過時的技術。這意味著我也會猶豫這周是要學習JavaScript框架還是那些新的編程語言。
只要占主導地位的計算模型體系不變，我們如今使用的數據結構與算法在未來也必定會以另外的形式繼續適用。您可以放心地將時間投入到深入掌握數據結構與算法知識中，它們將會成為您作為一名程序員的職業生涯中一筆長期巨大的財富。
作者：Happy Bear 譯者：icybreaker 校對：Caroline