資料結構與演算法(Data Structures & Algorithms)是軟體工程師處理資料的兩把核心武器:資料結構決定資訊在電腦中如何組織,演算法決定問題如何被有效率地解決。這篇文章從「軟體業需要什麼人才」的討論出發,用費伯納西數列的實例說明為什麼「動腦筋改演算法」勝過「花錢加硬體」,以及該怎麼開始學習。
前言
在 Scrum community 有篇很熱門的貼文討論,到底軟體業需要什麼樣才能的人才,議論紛紛,很多人指出軟體產業需要有溝通力的工程師;其次是熟悉資料結構和演算法的人才;第三多的票數則投給了能接受專案不斷變動,學校教育夠紮實的能力。
為甚麼資料結構與演算法極度重要?
身為一個資訊科學系的學生,我們最重要的工作就是處理資料,我們基本上都利用三個階段來處理資料:1. 輸入要處理的資料 2. 運算這些資料 3. 輸出我們預期的結果。
我們希望讓這些「運算」能夠更快,所以我們不斷最佳化從輸入到產出之間的處理步驟。所以我們採取「資料結構」設計以及「演算法」設計,正是為了讓電腦能夠更快地處理完資料顯示結果。
到底甚麼是資料結構?
資料結構對應到我們如何在電腦上呈現我們組織資訊的形式,讓電腦可以有效地使用這些經過整理的資料。使用不同的資料結構會有截然不同的效能。
到底甚麼是演算法?
演算法是設計出更有效率的解題步驟。舉例來說,1 + 2 + 3 + 4 + … + n,有些人用迴圈去做計算,只需要 O(n) 的時間。但是為何不用高斯公式 ((1+n)*n)/2,這個只要 O(1) 的時間就可以處理完畢了,更快,電腦不必一個一個去加總。
演算法的重要性
為了讓各位體會演算法的重要性,比較遞迴處理費伯納西數列與利用帶有快取的資料結構來運算:
# 遞迴處理費伯納西數列
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]詳細原理是因為如果利用遞迴處理費伯納西數列,會一直不斷出現重複運算的情況,因為遞迴並不會記錄運算的結果。所以利用一個資料結構把運算結果做儲存,等到需要用到的時候就可以直接取得資料。
上面第二段的寫法有一個 Python 的細節值得注意:cache 寫成可變的預設參數,會在多次呼叫之間共用同一個 dict。這裡剛好達成了跨呼叫的記憶效果,但同樣的寫法用在其他函式上通常是 bug 來源。正式的專案裡改用 functools.lru_cache 或把 cache 明確傳入會安全得多。
增加硬體不也可以加快運算速度嗎?
用免費的方式獲得更好的運算效能。只要動腦筋改改資料結構或者演算法,就不用購置硬體設備增強處理效能!請從巨觀角度去想問題,當你的網站或程式從 5 人到 1,000,000 人同時登入使用,增加硬體會是一個好的解決方案嗎?
該怎麼開始學習?
學習資料結構與演算法幾乎是軟體工程師的命,不只是為了完成各種軟體公司的面試關卡,也是為了更有效率地解決日常的軟體開發過程中的各種問題。建議上解題網站練習(如 LeetCode, CodeWar)、寫部落格分享心路歷程、參加討論或加入開源專案、尋找實習機會。
重點整理
- 處理資料的三階段是輸入、運算、輸出;資料結構與演算法就是為了讓「運算」更快而存在。
- 同一個問題,演算法不同效能天差地遠:等差級數用高斯公式是 O(1),迴圈是 O(n);費伯納西數列加上快取就能消除大量重複運算。
- 改資料結構與演算法是「免費」的效能提升;在使用者從 5 人成長到百萬人的尺度下,只靠加硬體不是好解法。
常見問題
面試考演算法,實務上真的用得到嗎?
多數日常開發確實不會叫你手寫紅黑樹。但用得到的是判斷力:知道這段迴圈裡的查找是 O(n) 還是 O(1)、資料量長到十萬筆的時候會不會爆掉、該用 list 還是 set。這種判斷在寫的當下只差一行,拖到上線後才發現就是一次重構。真正稀有的不是會解題,是看得出哪裡將來會出事。
為什麼不直接增加硬體就好?
加硬體要花錢,而且規模放大後成本失控;改良資料結構或演算法是免費的效能提升,在大流量情境下往往才是根本解法。
LeetCode 要刷到幾題才夠?
題數不是重點,能不能講出來才是。同一題如果你只是想起答案,那沒有累積;能說清楚為什麼選這個資料結構、複雜度怎麼算出來的,一題抵十題。比較有效的做法是題數少一點但每題寫下解法筆記,並在一週後重做一次——想不起來的地方就是真正還沒學會的地方。搭配寫部落格輸出、參與開源專案,效果會比純刷題好得多。
Leave a Reply