資料結構

資料結構筆記 0 – 為什麼要學資料結構?

KEEP 資料結構與演算法 OUT YOUR FUCKING MOUTH!(影片支援 XD) 這大概是正在轉職或是剛轉職的人聽到資料結構與演算法的第一個反應吧哈哈哈!

剛轉職的時候覺得:真的有必要學演算法和資料結構嗎?明明工作上就用不太到,感覺學這個就是單純為了面試和刷題而已。

但在工作一陣子後你會發現,在不同的應用場景使用正確的資料結構,有助於效能的提升,雖然以當今的電腦效能對使用者來說並不會有太大的差別,但以一個工程師來說,把功能做到盡善盡美是必須的!

以我目前的經驗來說,我認為學習資料結構最主要有兩個原因:

1. 根據不同應用使用對應的資料結構

1.1 範例一:Map v.s. Array

假設今天你會用到一串國家列表和縮寫的資料,但因為成本的考量,為了減少資料量,只能將縮寫存入 database 中,前端發 request 時,response 只會拿到國家的縮寫,要顯示國家名的話要再額外寫 function 找出對應的國家名,以剛轉職還是隻菜雞的我,就會這樣寫:

const nameMappingArray = [
  {
    id: 'AUT',
    name: 'Austria'
  },
  {
    id: 'BEL',
    name: 'Belgium'
  },
  {
    id: 'BRA',
    name: 'Brazil'
  },
  {
    id: 'CAN',
    name: 'Canada'
  },
  {
    id: 'EGY',
    name: 'Egypt'
  }
]

const id = 'BRA';
const arrayName = nameMappingArray.find((v) => v.id === id).name;
console.log(arrayName);
// Brazil

宣告一個陣列,把每個 id 對應到的 name 都塞到一個 object,再用 Array.prototype.find 找到相對應的 id,因為 find 會從陣列的第一個元素開始找,所以找到第 n 個元素的時間複雜度是 O(n)。

比較正確的資料結構應該是:

const nameMappingMap = new Map([
  ['AUT', 'Austria'],
  ['BEL', 'Belgium'],
  ['BRA', 'Brazil'],
  ['CAN', 'Canada'],
  ['EGY', 'Egypt'],
]);

const id = 'BRA';
const mappingName = nameMappingMap.get(id);
console.log(mappingName);
// Brazil

JavaScript 中的 Map 是用 Hash Table implement 的,因此直接用 get 存取 key 相對應的 value,時間複雜度是 O(1)。

所以說不同的場景雖然有很多解決方案,但學好資料結構有助於找到最好的解決方案。

1.2 範例二:瀏覽器的瀏覽紀錄 – Stack

假設今天要實作瀏覽器的瀏覽紀錄,應該使用哪種資料結構呢?一般來說會使用 Stack 這種資料結構,因為他有 LIFO (Last In First Out) 的特性,在使用者點擊上一頁時,會將最後存入 Stack 的資料給移除,回到上一頁,若是要回到第一頁(也就是第一個存入這個 Stack 的資料),則要不停地移除元素,最後才會剩下第一個元素,也就是先進後出的特性。

2. 了解許多軟體技術的原理

在學習許多軟體工具之後,你會發現有很多底層的原理都會用到這些基礎的資料結構,以前端為例,在 JavaScript 的原理中就會有 call stack 和 task queue 的存在,瀏覽器的實作原理也有許多 queue 和 stack:

資料結構
Browser Main Thread in the Renderer Process
圖片來源:JavaScript main thread. Dissected. 🔬

學習完整的資料結構有助於更快掌握這些開發工具的原理。

3. 結論

其實還有一個最重要的原因(可能也是唯一重要的原因?)就是面試會考🤣 這對大部分的人來說大概是最重要的吧哈哈哈

不過在經驗不足的情況下學習資料結構與演算法確實是滿硬的,因為在工作上用到的場景實在是不多,也無法理解學習資料結構與演算法的理由。

在這一年接觸許多開發工具和一些工作上的經驗累積再回過頭來好好整理資料結構與演算法讓我覺得比較有意義,也希望讓看到這篇文章的你多了解一些學習資料結構與演算法的動機。

看完這篇文章是不是想換工作了呢(咦?那就千萬別錯過 2024 職涯博覽會!想換工作的,有機會在博覽會遇見更好的另一半,不想換工作的,有機會在博覽會遇見更好的工作!趕快點擊下面的 banner,拯救你的人生!!!https://s.yourator.co/jimmy

如果覺得我的文章有幫助的話,歡迎幫我的粉專按讚哦~謝謝你!

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top