到底從事軟體開發的學生缺乏了甚麼？
資料結構與演算法篇
前言
在 Scrum community 有篇很熱門的貼文討論，到底軟體業需要什麼樣才能的人才，議論紛紛，很多人指出軟體產業需要有溝通力的工程師；其次是熟悉資料結構和演算法的人才；第三多的票數則投給了能接受專案不斷變動，學校教育夠紮實的能力。
身為一個還在就學的學生，當然會覺得這個東西很特別。因為未來我就業，大家看的居然是這些能力！之前我已經提過溝通的重要性了，這次我試著來解釋為甚麼資料結構與演算法很重要！
為甚麼資料結構與演算法極度重要？
甚至軟體工程師面試都直接考這些東西？
可能有些讀者看過一則新聞：
Max Howell在 OS X/iOS 開發領域是一位相當出名的軟體工程師，過去曾開發過網路電臺 Last.fm 的客戶端App、Twitter 的應用程式 TweetDeck 的開發者之一。他在 google 面試時因為反轉二元樹(是一個非常基本的資料結構)的解法不符合面試者期待因而落選。
所以那時資料結構與演算法又再度成為了熱門話題。當然身為一個資訊科學系的學生，我們最重要的工作就是處理資料，有玩過解題系統或網站的人應該會知道，我們基本上都利用三個階段來處理資料：
1. 輸入要處理的資料 2. 運算這些資料 3. 輸出我們預期的結果
這一系列處理資料的工作其實一直充斥在人們日常生活之中，例如你遇到問題，你會想很多步驟去解決問題，電腦也是，例如我們在臉書上輸入一些文字，理所當然的，我們預期這些文字會顯示在我們的個人頁上。但這個過程並不是那麼理所當然，因為背後還有網站在處理我們所輸入的資料，然後轉換成網頁該顯示的結果，也就是我們所輸入的文字。這個過程我們一般稱為「運算」。
我們希望讓這些「運算」能夠更快，所以我們不斷優化從輸入到產出之間處理步驟，就像你每天都要做很多事情，我們總會希望減少過程中不必要的麻煩來加快速度。
所以我們採取「資料結構」設計以及「演算法」設計，正是為了讓電腦能夠更快地處理完資料顯示結果，優化我們從輸入到輸出的過程。通常我們可以優化的是運算階段﹝也稱做第二階段﹞。
到底甚麼是資料結構？
資料結構對應到我們如何在電腦上呈現我們組織資訊的形式，讓電腦可以有效地使用這些經過整理的資料。假設我們要儲存一組聯絡人的資訊，我們會去想像要如何儲存：是一筆聯絡人紀錄就儲存全部的資料，包括姓名、性別、電話號碼；還是分門別類儲存，像是姓名一組、性別一組、；電話號碼一組等等。當然後面所述的方法，找這個人的全部資料會浪費時間在資料重組上面。所以回來仔細想一下，其實你會發現使用不同的資料結構會有截然不同的效能。
舉例來說，我們會希望有的資料結構可以展現資訊該有的樣子，意思是說讓先進來的資料可以先進行運算。又或者是讓資料經過整理後像一張心智圖一樣排序，如下圖
資料結構的重要性
1. 每個程式都會需要用到資料結構，因為你會需要整理輸入的資料
2. 有些特別的資料結構是組成重要演算法的基礎物件，也因為輸入的資料經過開發者的設計，在呈現上，讓使用者管理大量資料時，會變得非常簡單與有效率。
3. 有些程式語言很強調資料結構，甚至當成是軟體設計的基石，這時反而不是把演算法當作設計基礎進行開發。
到底甚麼是演算法？
有人說，演算法是工程師選擇不解釋的一種說詞。
但實際上，演算法是思考有效能地問題解決方式。
舉例來說， 1 + 2 + 3 + 4 + … + n，有些人用迴圈去做計算，只需要 O(n) 的時間（甚麼是 O 的時間 http://ppt.cc/kFULt），看起來非常地好，簡單易懂。
但是為何不用高斯公式 ((1+n)*n)/2，這個只要 O(1) 的時間就可以處理完畢了，更快，電腦不必一個一個去加總。
這樣差在哪裡？我們要先知道電腦是一個指令一個動作，如果你用迴圈來進行計算，對電腦來說我要每次提取一個數字，相加之後再存回記憶體中，要如此進行 n 次。但如果用高斯公式的話，電腦只要先讀取 1 ，與 n 相加後，再跟 n 相乘，接著除以 2 ，就出現結果了，這樣的步驟快上很多。
甚至，你還要考慮有些程式語言只支援遞迴（就是各位高中學的遞迴），沒有所謂的迴圈運算，這時候你必須用一個叫做 reduce 的作法或者使用 tail recursion 模擬迴圈去解決問題。演算法的重要性在這邊顯示出來。
演算法的重要性
為了讓各位體會演算法的重要性，我將用這兩個程式來做示範：
遞迴處理費伯納西數列：
def fibonacci_recursive(n):
if n <= 1:
return n
else:
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)利用帶有快取的資料結構來運算費伯納西數列：
def fibonacci_with_cache(n, cache={0: 0, 1: 1}):
if n not in cache:
cache[n] = fibonacci_with_cache(n-1, cache) + fibonacci_with_cache(n-2, cache)
return cache[n]詳細原理是因為我觀察到如果利用遞迴處理費伯納西數列，會一直不斷出現 return 1 的情況，因為遞迴並不會記錄運算的結果，算完就「忘記」這些資料。
所以為了解決這個情況，我就利用一個資料結構把運算結果做儲存，等到我需要用到的時候就可以直接取得資料，而不是一直重複運算一些已知的結果
我知道他們很重要，但是我還是無法體會
增加硬體不也可以加快運算速度嗎？
有個行銷語句叫做：用免費的方式獲得更好的運算效能。這句話聽起來像是非常差勁的行銷廣告一樣，但是一旦這句話應用在資料結構與演算法上面就會變得非常地契合。
只要動腦筋改改資料結構或者演算法，就不用購置硬體設備增強處理效能！
許多人一旦電腦程式運算效能變慢，就會一直購買新世代的硬體來增強效能。
他們常常認為程式本身沒有問題，一定是硬體太差跟不上時代了，所以買了很多昂貴的硬體來增強效能，殊不知其實有可能把程式運作邏輯稍作修改就可以大幅改善效能。
附註：請從巨觀角度去想問題，學校的案例都是為了學習用而縮小，請想想看當你的網站或程式從 5 人到 1000000 人同時登入使用，根據本文的想法，你覺得會出現甚麼情況，增加硬體會是一個好的解決方案嗎？
那我該怎麼開始學習這些東西？
學習資料結構與演算法幾乎是軟體工程師的命，不只是為了完成各種軟體公司的面試關卡，也是為了更有效率地解決日常的軟體開發過程中的各種問題。
所以我們要問問自己兩個問題：如何用有效率的方式解決問題，以及如何使用正確的工具解決問題。不只是看到問題，只想到用什麼合適的演算法來處理特定的問題，也要想著有沒有對應的工具跟解法來達到最佳解。
市面上已經有很多教你怎麼學好資料結構跟演算法的課程，也有不少人已經做了心得分享，這邊我也提出我一些當時訓練自己思考並應用資料結構跟演算法的一些方向：
- 上解題網站練習：平台如 UVA、eTutor、CodeWar、Leetcode，他們都提供了大量的面試可能被問到的題目等等，從面試心得分享到面試中遇到的基礎到進階的各種問題。這些練習不僅可以幫助我們理解和實踐演算法和資料結構的概念，還可以提高我們解決問題的速度和效率。
- 寫部落格分享心路歷程：這不僅僅是一種分享知識的方式，同時也是加深自己理解的過程。有醫生說過學習並且適當地寫作，我們可以更好地理解自己所學的內容，並且加深對於新知識的印象，部落格還有對外宣傳的效果，如果取得社群的各種回饋是可以獲得新的視角和建議。
- 參加討論或加入開源專案：參與社群討論或貢獻開源專案可以讓我們在實際的開發環境中應用所學。這種實踐經驗是非常寶貴的，它不僅可以幫助我們應用和鞏固知識，還可以讓我們學習如何與其他開發者互相合作。
- 尋找實習機會：直接投身於工作環境是學習和成長的絕佳方式。實習可以提供實際的工作經驗，讓我們在專業指導下應用和提高我們的技能。
就這樣嗎？
以下是我寫作時參考的資料：
延伸閱讀：
How learning data structures and algorithms make you a better developer
