🏗️ 第 1 週：資料結構基礎（Data Structures） 3/150
03. 稀疏數組的應用場景 - 棋盤、地圖、遊戲場景，都可以用稀疏數組來節省空間！
一、 問題的起源：為什麼我們要存那麼多「空氣」？
試想一下，你正在寫一個「五子棋」或「圍棋」的程式。
棋盤通常是 11 * 11 甚至 19*19 的網格。當玩家想要「存檔」時，你會怎麼做？
· 直覺的做法（二維陣列）：建立一個 11*11 的表格，把這 121 個格子通通記錄下來。
o 0 代表沒有棋子
o 1 代表黑子
o 2 代表白子
· 現實的情況：
如果棋局才剛開始，只下了 3 顆棋子，那你的存檔數據可能會長這樣：
Plaintext
0 0 0 0 0 0 ...
0 0 1 0 0 0 ...
0 0 0 2 0 0 ... (剩下全是 0)
發現了嗎？ 你為了存這 3 顆棋子，卻不得不記錄 100 多個「無意義的 0」。這就是典型的空間浪費。
二、 解決方案：稀疏數組（Sparse Array）
當一個陣列中，大部分的元素都是同一個值（通常是 0 或預設值），只有少部分是有意義的數據時，我們稱之為「稀疏數組」。
為了節省空間，我們不再儲存整個棋盤，而是只記錄「有棋子」的位置。這就是稀疏數組的壓縮邏輯。
壓縮後的資料結構（三元組記錄法）：
我們只需要記錄三個關鍵資訊：[行, 列, 值]。
1. 第一行（檔頭）： 記錄原始棋盤多大、總共有幾個棋子。
o
[11, 11, 2](11行，11列，共有 2 顆棋子)
2. 後續行（有效數據）：
o [1, 2, 1] (第 1 行，第 2 列，是黑子)
o [2, 3, 2] (第 2 行，第 3 列，是白子)
效果對比：
· 原始方式： 需儲存 121 個數據。
· 稀疏方式： 僅需儲存 3 行數據（共 9 個數字）。
空間瞬間節省了 90% 以上！
三、 生活與遊戲中的應用場景
除了棋盤，這種思維在電腦科學中無處不在：
1. 遊戲地圖（Open World Map）：
o 在一個巨大的 RPG 遊戲地圖中，可能大部分區域都是「空地」或「海洋」，只有少數座標有建築物或寶箱。
o 應用： 伺服器不會傳送整個地圖的數據給你，只會傳送「物件的座標點」，大幅降低網路延遲。
2. 圖片壓縮（Image Compression）：
o 想像一張簡單的圖畫，大片背景都是純白色。
o 應用： 我們不需要記錄每個像素點是「白色」，只需記錄「非白色」的線條位置，這也是某些圖片格式能這麼小的原因。
3. 地圖導航數據：
o 城市的地圖網格中，絕大多數地方是「建築物」或「障礙」，只有少數線條是「道路」。使用稀疏圖（Sparse Graph）來儲存道路網，能讓導航運算更快。
四、 AI 時代的「稀疏」思維
在人工智慧與大數據領域，稀疏數組的重要性被提升到了全新高度：
1. 推薦系統（Recommender Systems）：
o Netflix 或 Spotify 有上億個用戶和數百萬部影片/歌曲。
o 建立一個「用戶-商品」的評分矩陣時，這張表會大得驚人（億 x 百萬），但絕大多數格子是空的（因為一個用戶不可能看過所有影片）。
o 若不用稀疏矩陣（Sparse Matrix）技術，現今沒有一台超級電腦存得下這些數據。
2. 自然語言處理（NLP）：
o 在分析文章時，我們常把文字轉成向量（One-hot Encoding）。
o 字典裡有 10 萬個字，但一句話只有 10 個字。這意味著向量中有 99,990 個位置是 0。稀疏運算是讓 AI 能高效讀懂文字的關鍵。
五、 總結
• 稀疏數組的核心在於「去蕪存菁」，只關注有意義的資訊，忽略大量的預設值。
• 這是一種「時間換空間」或「空間換時間」的權衡：雖然壓縮讓儲存變小了（省空間），但讀取時需要還原（可能多花一點點時間），但在大數據場景下，這種交換絕對是划算的。
• 工程師思維：看到大量重複數據時，永遠要問自己：「我需要全部存下來嗎？還是只存差異就好？」
