學習數據結構與演算法分析如何幫助您成為更優秀的開發人員

學習數據結構與演算法分析會讓您成為一名出色的程序員。

數據結構與演算法分析是一種解決問題的思維模式。 在您的個人知識庫中，數據結構與演算法分析的相關知識儲備越多，您將越多具備應對並解決各類繁雜問題的能力。掌握了這種思維模式，您還將有能力針對新問題提出更多以前想不到的漂亮的解決方案。

您將更深入地了解，計算機如何完成各項操作。無論您是否是直接使用給定的演算法，它都影響著您作出的各種技術決定。從計算機操作系統的內存分配到RDBMS的內在工作機制，以及網路協議如何實現將數據從地球的一個角落發送至另一個角落，這些大大小小的工作的完成，都離不開基礎的數據結構與演算法，理解並掌握它將會讓您更了解計算機的運作機理。

對演算法廣泛深入的學習能為您儲備解決方案來應對大體系的問題。之前建模困難時遇到的問題如今通常都能融合進經典的數據結構中得到很好地解決。即使是最基礎的數據結構，只要對它進行足夠深入的鑽研，您將會發現在每天的編程任務中都能經常用到這些知識。

有了這種思維模式，在遇到磨棱兩可的問題時，您將能夠想出新奇的解決方案。即使最初並沒有打算用數據結構與演算法解決相應問題的情況，當真正用它們解決這些問題時您會發現它們將非常有用。要意識到這一點，您至少要對數據結構與演算法分析的基礎知識有深入直觀的認識。

理論認識就講到這裡，讓我們一起看看下面幾個例子。

最短路徑問題

我們想要開發一個軟體來計算從一個國際機場出發到另一個國際機場的最短距離。假設我們受限於以下路線：

從這張畫出機場各自之間的距離以及目的地的圖中，我們如何才能找到最短距離，比方說從赫爾辛基到倫敦？Dijkstra演算法是能讓我們在最短的時間得到正確答案的適用演算法。

在所有可能的解法中，如果您曾經遇到過這類問題，知道可以用Dijkstra演算法求解，您大可不必從零開始實現它，只需知道該演算法的代碼庫能幫助您解決相關的實現問題。

如果你深入到該演算法的實現中，您將深入理解一項著名的重要圖論演算法。您會發現實際上該演算法比較消耗資源，因此名為A*的擴展經常用於代替該演算法。這個演算法應用廣泛，從機器人尋路的功能實現到TCP數據包路由，以及GPS尋徑問題都能應用到這個演算法。

先後排序問題

您想要在 開放式在線課程 （ MOOC，Massive Open Online Courses ） 平台上(如Udemy或Khan學院)學習某課程，有些課程之間彼此依賴。例如，用戶學習 牛頓力學 （ Newtonian Mechanics ） 課程前必須先修 微積分 （ Calculus ） 課程，課程之間可以有多種依賴關係。用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

這裡有兩個潛在的重要約束條件：

• 返回的必修課列表中，每門課都與下一門課存在依賴關係
• 我們不希望列表中有任何重複課程

這是解決數據間依賴關係的例子，解決該問題的排序演算法稱作 拓撲排序演算法 （ tsort，topological sort ） 。它適用於解決上述我們用YAML列出的依賴關係圖的情況，以下是在圖中顯示的相關結果(其中箭頭代表需要先修的課程):

拓撲排序演算法的實現就是從如上所示的圖中找到滿足各層次要求的依賴關係。因此如果我們只列出包含radioactivity和與它有依賴關係的子圖，運行tsort排序，會得到如下的順序表：

arithmetic
algebra
trigonometry
calculus
mechanics
atomic_physics
radioactivity

這符合我們上面描述的需求，用戶只需選出radioactivity，就能得到在此之前所有必修課程的有序列表。

在運用該排序演算法之前，我們甚至不需要深入了解演算法的實現細節。一般來說，你可能選擇的各種編程語言在其標準庫中都會有相應的演算法實現。即使最壞的情況，Unix也會默認安裝tsort程序，運行man tsort 來了解該程序。

其它拓撲排序適用場合

• 類似make的工具 可以讓您聲明任務之間的依賴關係，這裡拓撲排序演算法將從底層實現具有依賴關係的任務順序執行的功能。
• 具有require指令的編程語言適用於要運行當前文件需先運行另一個文件的情況。這裡拓撲排序用於識別文件運行順序以保證每個文件只載入一次，且滿足所有文件間的依賴關係要求。
• 帶有甘特圖的項目管理工具。甘特圖能直觀列出給定任務的所有依賴關係，在這些依賴關係之上能提供給用戶任務完成的預估時間。我不常用到甘特圖，但這些繪製甘特圖的工具很可能會用到拓撲排序演算法。

霍夫曼編碼實現數據壓縮

霍夫曼編碼 （ Huffman coding ） 是一種用於無損數據壓縮的編碼演算法。它的工作原理是先分析要壓縮的數據，再為每個字元創建一個二進位編碼。字元出現的越頻繁，編碼賦值越小。因此在一個數據集中e可能會編碼為111，而x會編碼為10010。創建了這種編碼模式，就可以串聯無定界符，也能正確地進行解碼。

在gzip中使用的DEFLATE演算法就結合了霍夫曼編碼與LZ77一同用於實現數據壓縮功能。gzip應用領域很廣，特別適用於文件壓縮(以.gz為擴展名的文件)以及用於數據傳輸中的http請求與應答。

學會實現並使用霍夫曼編碼有如下益處：

• 您會理解為什麼較大的壓縮文件會獲得較好的整體壓縮效果(如壓縮的越多，壓縮率也越高)。這也是SPDY協議得以推崇的原因之一：在複雜的HTTP請求/響應過程數據有更好的壓縮效果。
• 您會了解數據傳輸過程中如果想要壓縮JavaScript/CSS文件，運行壓縮軟體是完全沒有意義的。PNG文件也是類似，因為它們已經使用DEFLATE演算法完成了壓縮。
• 如果您試圖強行破譯加密的信息，您可能會發現由於重複數據壓縮質量更好，密文給定位的數據壓縮率將幫助您確定相關的 分組密碼工作模式 （ block cipher mode of operation ） 。

下一步選擇學習什麼是困難的

作為一名程序員應當做好持續學習的準備。為了成為一名web開發人員，您需要了解標記語言以及Ruby/Python、正則表達式、SQL、JavaScript等高級編程語言，還需要了解HTTP的工作原理，如何運行UNIX終端以及面向對象的編程藝術。您很難有效地預覽到未來的職業全景，因此選擇下一步要學習哪些知識是困難的。

我沒有快速學習的能力，因此我不得不在時間花費上非常謹慎。我希望儘可能地學習到有持久生命力的技能，即不會在幾年內就過時的技術。這意味著我也會猶豫這周是要學習JavaScript框架還是那些新的編程語言。

只要佔主導地位的計算模型體系不變，我們如今使用的數據結構與演算法在未來也必定會以另外的形式繼續適用。您可以放心地將時間投入到深入掌握數據結構與演算法知識中，它們將會成為您作為一名程序員的職業生涯中一筆長期巨大的財富。

via: http://www.happybearsoftware.com/how-learning-data-structures-and-algorithms-makes-you-a-better-developer

作者：Happy Bear 譯者：icybreaker 校對：Caroline

本文由 LCTT 原創翻譯，Linux中國 榮譽推出

本文轉載來自 Linux 中國: https://github.com/Linux-CN/archive