🏗️ 第 1 週：資料結構基礎（Data Structures） 5/150
05. 稀疏數組的程式碼實作 - 從邏輯到代碼的轉化
一、 實作核心目標程式實作不僅僅是將「稀疏數組」的數學定義寫出來，更重要的是掌握數據轉換的生命週期。我們的目標是編寫一套通用的轉換工具，能夠處理任意大小的二維矩陣，將其「無損壓縮」為輕量化的三欄式結構，並能隨時完美還原。
二、 壓縮邏輯的關鍵：兩次掃描法 (Two-Pass Strategy)
在程式設計（特別是像 Java 或 C++ 這類需預先定義陣列大小的語言）中，將二維陣列轉為稀疏數組通常需要執行兩次迴圈掃描：
- 第一次掃描（計數）： 遍歷整個原始二維陣列，計算出所有「非 0 元素」的總數（sum）。這一步至關重要，因為它決定了我們接下來要建立多大的稀疏數組空間（即 sum + 1 行）。
- 第二次掃描（填充）： 再次遍歷陣列，將非 0 元素的具體資訊——「所在的列（Row）、所在的行（Col）、以及數值（Value）」——依序填入稀疏數組中。
三、 還原邏輯的關鍵：檔頭解析 (Header Parsing)
還原過程是壓縮的逆運算，但它完全依賴於稀疏數組的第一行（Index 0），我們稱之為「檔頭」。
- 讀取維度： 程式必須先讀取第 0 行的前兩個數字，才能知道要初始化一個多大的全新二維陣列（例如 $6 \times 7$）。
- 回填數據： 接著從第 1 行開始讀取有效數據，利用座標直接定位並賦值。若沒有檔頭紀錄原始大小，還原出來的棋盤將會失去邊界，導致邏輯錯誤。
四、 Python 簡易實作範例
以下這段程式碼展示了從「建立棋盤」到「壓縮存檔」，再到「讀取還原」的完整流程：
Python
# --- 1. 模擬原始數據：建立一個 6x7 的棋盤 ---
# 0代表空位, 1代表黑子, 2代表白子
chess_arr = [
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0], # (1, 2) 有黑子
[0, 0, 0, 2, 0, 0, 0], # (2, 3) 有白子
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]
]
# --- 2. 壓縮：二維陣列 -> 稀疏數組 ---
# 步驟 A: 統計有效數據 (sum)
sum_val = 0
for row in chess_arr:
for val in row:
if val != 0:
sum_val += 1
# 步驟 B: 建立稀疏數組 (sum+1 行, 3 列)
# 第0行是檔頭：[原始列數, 原始行數, 有效數據總數]
sparse_arr = [[len(chess_arr), len(chess_arr[0]), sum_val]]
# 步驟 C: 填入數據
for i in range(len(chess_arr)):
for j in range(len(chess_arr[0])):
if chess_arr[i][j] != 0:
# 記錄 [列, 行, 值]
sparse_arr.append([i, j, chess_arr[i][j]])
print("=== 壓縮後的稀疏數組 (模擬存檔) ===")
for row in sparse_arr:
print(row)
# --- 3. 還原：稀疏數組 -> 二維陣列 ---
# 步驟 A: 讀取檔頭
orig_rows = sparse_arr[0][0]
orig_cols = sparse_arr[0][1]
# 步驟 B: 建立全 0 的新陣列
restored_arr = [[0] * orig_cols for _ in range(orig_rows)]
# 步驟 C: 回填有效數據 (從第1行開始讀)
for i in range(1, len(sparse_arr)):
cur_row = sparse_arr[i][0]
cur_col = sparse_arr[i][1]
cur_val = sparse_arr[i][2]
restored_arr[cur_row][cur_col] = cur_val
print("\n=== 還原後的棋盤 (模擬讀檔) ===")
for row in restored_arr:
print(row)
五、 AI 時代的實務價值
雖然學習時我們手寫迴圈來理解原理，但在 Python 的 AI 實務開發中（如 NLP 自然語言處理或推薦系統），我們通常會呼叫高效能函式庫（如 SciPy 或 NumPy）。這些函式庫底層運用的正是上述邏輯的優化版，用來處理那些維度高達數百萬、但有效數據極少的特徵矩陣（Feature Matrix），是現代 AI 模型節省記憶體與加速運算的基石。
