iT邦幫忙

2021 iThome 鐵人賽

DAY 24
1
Modern Web

Javascript 從寫對到寫好系列 第 24

Day 24 - 資料結構入門理解

前言

今天要來討論一些更進階的程式寫法,比較偏向效能方面的優化,怎麼寫可以讓效能變好、擴充容易,而不是討論如何寫出一個 feature,因為我們的目標是「更好」!

但本篇不會觸及太多實作,定向為「讓初學者有個概念」,可以大概知道為什麼會有資料結構的出現,不會每次看到這四個字就先暈倒。

因此如果你已經有基本概念了,可以簡單看過一起討論指教,或者左轉進我的隊友系列文,有非常實作的 LeetCode 刷題講解,完全可以滿足高手區的觀眾唷!

資料結構是什麼?

在電腦科學中,資料結構(Data Structure) 是電腦中儲存、組織資料的方式。當資料存在記憶體中的時候,決定資料的存放順序及存放位置的,就是資料結構。

聽起來還是很抽象,所以我們一步一步來,先來看如果沒有特別使用資料結構,我們會遇到什麼問題。

資料結構解決了什麼問題?

假如今天一個電商網站要條列出商品與價格:

const product1 = 'TV';
const product2 = 'laptop';
const product3 = 'washing machine';

const price1 = 12000;
const price2 = 25000;
const price3 = 8000;

console.log(`${product1} 的價錢是 ${price1}`);
console.log(`${product2} 的價錢是 ${price2}`);
console.log(`${product3} 的價錢是 ${price3}`);

執行結果

TV 的價錢是 12000
laptop 的價錢是 25000
washing machine 的價錢是 8000

老闆:欸那個 Joey 啊!商品太少了沒客人啦!多幫我把冷氣、電扇、螢幕、空氣清淨機、除濕機都放上去啊!

於是我就崩潰了,一個變數如果只能儲存一個值,我就要從 prodcut1 放到 product99,而且要把每個項目陳列出來的時候,完全就是複製貼上手抽筋。

聰明的你看到上面的案例,會怎麼去優化它呢?

沒錯,最基本的就是陣列加物件:

const products = [
    { name: 'TV', price: 12000 },
    { name: 'laptop', price: 25000 },
    { name: 'washing machine', price: 8000 },
];

products.forEach(product => console.log(`${product.name} 的價錢是 ${product.price}`));

當我們這樣改寫,即便老闆說要加項目,我也只要在原本的「結構」內,多添加項目即可,不用新增變數,且 forEach 的程式碼一個字都不用動:

const products = [
    { name: 'TV', price: 12000 },
    { name: 'laptop', price: 25000 },
    { name: 'washing machine', price: 8000 },
    { name: 'air conditioner', price: 20000 }, // 只加了這兩行
    { name: 'electric fan', price: 1000 }, // 只加了這兩行
];

products.forEach(product => console.log(`${product.name} 的價錢是 ${product.price}`));

雖然我們現在對於這個優化習以為常,而且信手拈來,很熟的人甚至不需要經過 prodcut1product2 那層思考,可以直接從陣列開始著手。

那你想過陣列到底在背後做了什麼,才能夠讓我們這麼方便嗎?

陣列在記憶體中的儲存方式

記得,變數就是用存放數值的地方

當我們宣告了一個字串變數,其實就是電腦在記憶體中抓一個位置,讓你存放 'TV' 這個數值,然後再抓一個位置(不一定是連續的位置),用來放 'laptop'

const product1 = 'TV';
const product2 = 'laptop';

而宣告陣列變數時,其實是電腦在記憶體中抓一連串的位置,幫你在第一格存 'TV',第二格存 'laptop',以此類推。

const products = ['TV', 'laptop', 'washing machine'];

所以我們在使用陣列時,才會只需要記住 products 這個變數名稱,因為它的記憶體位址是連續的,只要告訴它 index,就可以按圖索驥對應到你要的那一格。

陣列在記憶體擺放上,是特別安排過的、有順序、有結構的,所以我們才可以利用這個特性,使用 forEachfiltermap 等方便的函式,都是基於這個「結構」才有的操作。

這樣理解了嗎?Array 就是一個大家使用得相當熟練的,其中一種資料結構。

資料結構的種類

比較常見的就有以下幾種:

  • 陣列(Array)
  • 堆疊(Stack)
  • 佇列(Queue)
  • 連結串列(Linked List)
  • 樹(Tree)
  • 圖(Graph)
  • 堆積(Heap)
  • 雜湊表(Hash table)

不同種類的資料結構適合不同種類的應用,部分資料結構甚至是為了解決特定問題而設計出來的。

所以當我們要寫某個領域的實作時,通常也不會每個資料結構都拿出來用,而是「針對特定問題使用特定資料結構」。

比如密碼學的領域,就經常使用到 hash table;而如果要做 cron server (排程系統),則比較會用到 queue。

非同步核心的資料結構

還記得我們在 Day 14 討論到非同步核心,下列這些名詞還記得嗎:

  • Call Stack
  • Memory Heap
  • Callback Queue

有沒有某一塊拼圖突然吻合的感覺!

Call Stack

Call Stack 是用來存放指令的地方,為什麼要用 stack?因為 stack 的特性是 FILO (First-In-Last-Out),就像我的衣櫥一樣,最早放進去的衣服最晚才發現要穿((誤,第一個放進去的指令要最後才執行,而最後放進去的指令則第一個執行。

聽起來很不合理嗎?看看這個範例,父函式裡面有子函式,只要程式跑到子函式,就會等子函式跑完,才把父函式剩餘的程式跑完:

const child = () => {
    console.log('child 1');
};
const parent = () => {
    console.log('parent 1');
    child();
    console.log('parent 2');
};

parent();

執行結果

parent 1
child 1
parent 2

是不是正好符合 stack 的特性呢?

Callback Queue

Callback Queue 則更好理解了,queue 的特性是 FIFO (First-In-First-Out),就像排隊要吃一蘭拉麵的民眾一樣,先來排隊的人最先吃。

放在 callback queue 的指令,會等到 call stack 空了,就由 event loop 偵測放到 call stack,早來的先放。

是不是正好符合 queue 的特性呢?

解決不同問題

因為篇幅的關係,就沒有要把每個資料結構都介紹一遍,那也不是「入門理解」的範疇了。但透過上述這些範例,有沒有更了解為什麼要用資料結構呢?

當然我們可以全都用 Array 暴力解決:Call Array、Memory Array、Callback Array,存資料而已嘛,我怎麼存都沒人管得著。

但就像是把衣服放在書櫃上,或者把書本放在冰箱一樣的道理,不是不能放,只是使用這些資料的效率就降低了。

因此,沒有萬能的資料結構,只有使用不同資料結構解決不同問題

結語

資料結構是大學資工系基礎必修的一環,基本上只要沾到計算機科學的邊,都離不開資料結構,因為牽涉到數值怎麼擺放,記憶體如何分配。

雖然聽起來很生硬,背後也真的是很硬的一堆知識,但它無疑是邁向「更好」 develop 的一大步,起碼 FAANG 這些國際級的軟體大公司,處理的都是數百、數千萬的資料量,哪個容得下從頭到尾都在用 Array 的菜菜?

資料結構的討論深度與廣度,完全可以再開一個 30 天的鐵人賽來挑戰,但今天的內容,期待可以讓許多非本科系,看到資料結構就怕的人,可以有最基礎的理解!

崩壞後重建
以全新的姿態
征服鴻溝

參考資料

資料結構 wiki


上一篇
Day 23 - 開發人員工具的日常
下一篇
Day 25 - 演算法入門理解
系列文
Javascript 從寫對到寫好30

1 則留言

0
Chiahsuan
iT邦新手 4 級 ‧ 2021-10-09 18:21:20

你好~~小粉絲想請教關於資料結構你有推薦的書單嗎?感謝~
/images/emoticon/emoticon41.gif

看更多先前的回應...收起先前的回應...
ycchiuuuu iT邦新手 5 級 ‧ 2021-10-09 23:34:59 檢舉

哇!這個問題難倒我了,因為程式相關的資源更新太快了,大多時候我是不看書的((逃

如果不排斥英文的,我個人是推薦這堂 Udemy 線上課程,我有上這堂課,也敗了很多這個講師的 JavaScript 課程,他的英文講得偏慢,而且有很多舉例跟圖像可以幫助理解,等 Udemy 不定時特價四五百元可以去買,推推!

不過還是要衡量一下自己的需求唷!因為說實話,一般寫 JavaScript 的 developer,滿少機會碰到資料結構與演算法的,很容易拿了牛刀找不到牛XD (不過如果要刷題拼面試又是另外一回事了~)

Chiahsuan iT邦新手 4 級 ‧ 2021-10-09 23:48:31 檢舉

感謝推薦~~~意外發現我有訂閱這個講師的電子報/images/emoticon/emoticon37.gif

嗯嗯~我也還只是小菜菜!等之後有需要再學習~非常感謝你的建議(找不到牛的比喻真好XD)

TD iT邦新手 4 級 ‧ 2021-10-12 09:56:33 檢舉

我也是看同一堂課,大推!

另外也推一下我隊友這次鐵人賽的系列文 LeetCode 雙刀流:Python x JavaScript,雖然以 LeetCode 為主,但是也談到很多資料結構和演算法的概念

ycchiuuuu iT邦新手 5 級 ‧ 2021-10-12 12:08:05 檢舉

感謝推薦維元大大!等完賽再來追劇XD

LeetCode 真的是很熱門的主題啊!也是一個鍛鍊資結/演算的好地方,隨著程式規模愈來愈大,相關需求應該是有增無減,推推!

我要留言

立即登入留言