還記得在我們程式碼重構的第一天,把難用的資料形狀,改成了比較好處理的資料形狀嗎?
//// 不好用的資料形狀
var itemPrice = [
{name: "遙控車", price: 250},
{name: "玩偶", price: 180},
{name: "拼圖", price: 120}
]; // 商品價格
var amounts = [2, 0, -10]; // 購買數量
// 不好用的計算方法
itemPrice[0].price * amounts[0]
//===========================================
//// 新的資料形狀
// 商品價格字典, 以後可以很方便的新增或修改商品跟價格
let itemPrice = {
"遙控車": 250,
"玩偶": 180,
"拼圖": 120
}
// 改成用物件,可以用 name 當 key 來取得 itemPrice 的價格
let cart = [
{name: "遙控車", amount: 2},
{name: "玩偶", amount: 0},
{name: "拼圖", amount: -10}
]
// 好用的計算方法
let {name, amount} = cart[0]
itemPrice[name] * amount
這種知道用哪種資料的形狀,可以讓我們的程式更容易處理的知識,叫做資料結構與演算法 (data structures and algorithms)。這個在程式的領域是很重要的進階級學問,是在大學裡做為一個單獨的課來學習的。
這個領域在討論有什麼程式的流程跟資料的形狀,可以更容易更快的解決問題。
資料結構與演算法有一個很經典的問題,就是「怎麼查字典最快?」。例如我們手上有一本 1024 頁的字典,裡面是用每個字的筆劃數排好順序的,而且沒有目錄,那麼當我們想要查任何一個字,你會怎麼翻字典呢?
如果你是每次都從前面開始翻,在遇到筆劃最多的字時,最多要翻到第 1024 次才找得到。反之從後面開始翻,在遇到筆劃最少的字時,最多也是翻 1024 次。
「演算法」會教我們有個很棒的方法:
這個演算法有個名字,叫二分搜尋法。就是每次都可以排除掉一半的意思。
由於每一次翻頁,都可以排除一半無關的資訊,所以一本 1024 頁的字典,不管什麼字,最多就是翻 10 次可以找得到。
而如果變成兩倍厚的字典,2048 頁的話,最多翻 11 次就能找到。
每年 12 月 1 日的時候,有個叫 Advent of Code 的網站,會連出 25 天的演算法挑戰,直到耶誕節那天。有興趣的話可以玩玩看。
另外如果你有聽到找工作的人說了刷題,是指去練習在 LeetCode 演算法題庫上的題目。有些大公司會從這裡出面試的題目。如果是想學習的話, exercism、HakerRank 也是不錯的選擇。
如果你不知道你想做的功能會不會太複雜,可以跟 AI 用這幾句話來聊聊看:
我想做的這個功能,有沒有什麼效能上的瓶頸
這個瓶頸是否能用什麼演算法改進它?
資料結構及演算法這張地圖是程式領域裡比較進階的知識(當然它也很有趣),通常只會在你想要寫出相當複雜的功能,或是你的程式要處理的資訊非常多的時候比較用得到。所以不需要急著往下看,而是知道有這個領域,有需要的時候再回來看就可以了。
把一個數字不斷的除以 2
,除幾次會變成 1
的概念,在以後學到複雜一點的數學時,會知道可以用次方的概念來計算。
所以當字典變成兩倍厚,也就是 2048 頁時,二分搜尋法最多只要 11 次就一定找得到。只多了一次。
這個概念在演算法裡叫時間複雜度 (Time Complexity),討論一個演算法在資料量不斷的增加時,所花的時間增加的幅度是多少。我們會用一種叫 Big O 的符號來表示怎麼增加, 有下列這些:
Big O | 名稱 | 時間增長 | 例子 | 說明 |
---|---|---|---|---|
O(1) | 常數 | 資料多時間都不變 | 陣列取值 arr[0] |
超快 ⚡ |
O(log n) | 對數 | 資料兩倍,時間多一點點 | 二分搜尋 | 很快 🚀 |
O(n) | 線性 | 資料兩倍,時間兩倍 | 走訪陣列 | 還好 😊 |
O(n log n) | 線性對數 | 資料兩倍,時間兩倍再多一點 | 快速排序、合併排序 | 可接受 😐 |
O(n²) | 平方 | 資料兩倍,時間四倍 | 泡沫排序、兩層迴圈 | 慢 😱 |
O(n³) | 立方 | 資料兩倍,時間八倍 | 三層迴圈 | 很慢 🐢 |
O(2ⁿ) | 指數 | 資料多一個,時間加倍 | 費氏數列(遞迴) | 超慢 🐌 |
O(n!) | 階乘 | 資料多一個,時間乘以資料量 | 排列組合 | 別用 💀💀💀 |
除了常用的 陣列[]
與字典{}
之外,可以用它們組合成很多種叫做 樹(Tree)
及 圖(Graph)
的資料結構,它們在想要做到很複雜的事的時候非常有用。
1. 從第一個學生開始,記住目前看過最高的學生。
2. 接著看下一個學生,如果比目前記住的還高,就更新記錄。
3. 走完全班後,記錄的就是最高的學生。
有更棒的方法嗎?跟 AI 聊聊看!