iT邦幫忙

2025 iThome 鐵人賽

DAY 24
0

還記得在我們程式碼重構的第一天,把難用的資料形狀,改成了比較好處理的資料形狀嗎?

//// 不好用的資料形狀
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 次。

「演算法」會教我們有個很棒的方法:

  1. 先翻開正中間那一頁,也就是第 512 頁。
  2. 看看這頁第一個字的筆劃,比我們要查的字筆劃多還是少。
  3. 如果是我們的字筆劃比較少時,直接去翻前面那半正中間那頁,也就是第 256 頁。
    如果比較多,那翻後面那半正中間那頁,也就是第 768 頁。
  4. 比較第 256 頁第一個的筆劃,比我們要查的字筆劃多還是少。
  5. 如果還是比較少,那就再翻前面那一半,也就是第 128 頁。
    如果比較多,改翻後面那半: 128 跟 256 的中間,也就是第 384 頁。
  6. 重複這個動作直到找到。

這個演算法有個名字,叫二分搜尋法。就是每次都可以排除掉一半的意思。

由於每一次翻頁,都可以排除一半無關的資訊,所以一本 1024 頁的字典,不管什麼字,最多就是翻 10 次可以找得到。

而如果變成兩倍厚的字典,2048 頁的話,最多翻 11 次就能找到。

演算法挑戰

每年 12 月 1 日的時候,有個叫 Advent of Code 的網站,會連出 25 天的演算法挑戰,直到耶誕節那天。有興趣的話可以玩玩看。

另外如果你有聽到找工作的人說了刷題,是指去練習在 LeetCode 演算法題庫上的題目。有些大公司會從這裡出面試的題目。如果是想學習的話, exercismHakerRank 也是不錯的選擇。

跟 AI 聊聊看

如果你不知道你想做的功能會不會太複雜,可以跟 AI 用這幾句話來聊聊看:

  • 我想做的這個功能,有沒有什麼效能上的瓶頸
  • 這個瓶頸是否能用什麼演算法改進它?

[進階] 在你往下看之前

資料結構及演算法這張地圖是程式領域裡比較進階的知識(當然它也很有趣),通常只會在你想要寫出相當複雜的功能,或是你的程式要處理的資訊非常多的時候比較用得到。所以不需要急著往下看,而是知道有這個領域,有需要的時候再回來看就可以了。


為什麼 10 次一定翻得完?

把一個數字不斷的除以 2,除幾次會變成 1的概念,在以後學到複雜一點的數學時,會知道可以用次方的概念來計算。

Equation

所以當字典變成兩倍厚,也就是 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) 的資料結構,它們在想要做到很複雜的事的時候非常有用。


營火前的回顧

  • 資料結構及演算法討論程式流程的好壞
  • 通常要寫很複雜的功能,或是資料量很大時才要擔心
  • 跟 AI 聊「演算法」或「資料結構」,它蠻厲害的

小測驗

  1. 想想二分搜尋法還可以用在生活中什麼事情上?
  2. 全班 30 個學生站成一排,你要找出誰最高。用幾句話說明就好,例如:
1. 從第一個學生開始,記住目前看過最高的學生。
2. 接著看下一個學生,如果比目前記住的還高,就更新記錄。
3. 走完全班後,記錄的就是最高的學生。

有更棒的方法嗎?跟 AI 聊聊看!

  1. [相當難] 學校裡每個人都有好朋友,隨便挑一個不是你朋友的人,怎麼算出你經過幾個朋友可以選到這個人?

地圖


上一篇
Ch 22. 為什麼程式設計師喜歡用蘋果電腦?
系列文
Just enough code with AI: 給新手們的程式設計世界觀24
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言