陣列與稀疏矩陣 — Arrays Interactive（C++）

📌 本頁使用方式（附錄 A（講義 03）｜講義 03）

① 照節次讀：每一節先讀說明、動手玩互動元件，預測結果再按按鈕驗證。 ② 對照講義：頁上 §徽章對應 cppds 章節；細節與完整程式請回講義 03 與 cppds 原文。 ③ 每節做 quiz：答錯就回到該節重讀，不要往下跳。 ④ 最後翻關鍵詞彙卡（11 張）自測術語（中文為主、術語附英文），並用 REF 總覽區當速查表。標「講義補充」的節是課堂沒細講的延伸，第一輪可略過。

📑 講義 03 PDF 🖥 講義 03 HTML 📘 Hello 演算法（陣列）🏠 章節總覽

CONTENTS · 內容目錄

P00低階陣列 P01位址計算 P02compact vs referential P03多維陣列 P04稀疏矩陣 EX練習題 REF總覽比較 CARD關鍵詞彙卡（11 張）

PROLOGUE · 開場

低階陣列：連續記憶體是一切的起點課程補充 A.1

本章是課程補充教材（cppds 書中散見於 §1.9 與 §2.5）：往下鑽一層，看陣列在記憶體裡的真實長相。電腦記憶體 = 一長條可編號的位元組（byte）； 陣列 = 一段連續的、等寬的格子。這個「連續＋等寬」就是 O(1) 隨機存取的全部秘密。

本章路線 A.1 低階陣列與位址計算 → A.2 compact vs referential → A.3 多維陣列與 row-major → A.4 稀疏矩陣（COO/DOK）。

講義 03 · sizeof 與位址親眼看

using namespace std;
cout << sizeof(double) << " bytes per double" << endl;
cout << sizeof(int) << " bytes per int" << endl;
cout << sizeof(char) << " byte per char" << endl;
 
double data[6];
cout << sizeof(data) << " bytes for the whole array" << endl;
cout << &data[0] << " <- base address" << endl;
cout << &data[1] << " <- 8 bytes later" << endl;
 

示範執行（位址每次不同）

8 bytes per double
4 bytes per int
1 byte per char
48 bytes for the whole array
0x7ffcd3b1e2a0 <- base address
0x7ffcd3b1e2a8 <- 8 bytes later

兩個位址恰好差 8（十六進位 a0 → a8）：陣列元素連續排在記憶體裡，一格一個 double。整個陣列 6 × 8 = 48 bytes，一條 sizeof 全算得出來。

PART 01 · 位址計算

a[i] 為什麼是 O(1)：一條乘法公式課程補充 A.1

addr(a[i]) = base + i × sizeof(元素)

sizeof：

兩個直接推論

① 存取任何 a[i] 成本相同：不用走訪。
② 格子必須等寬：所以 C++ 陣列是同型別元素。

C++ 對照

int a[6];
&a[3] == a + 3 // 指標算術
sizeof(a) // 24（6×4）

PART 02 · 兩種存法

Compact vs Referential：值放格子裡，還是放「別處」？課程補充 A.2

Compact array：元素的值直接躺在連續格子裡（C++ int a[]、vector<int>、甚至 string 本身就是字元的 compact array）。 Referential array：格子裡放的是指標，真正的物件散落在 heap。想存一排長短不一的名字（"Rene"、"Joseph"、"Virginia"…）又要維持 O(1) 索引，格子就必須等寬，於是「什麼都能裝」的動態串列一律存 8 byte 的參考。代價有二：每個元素多付 8 byte 的指標稅，以及取值都要多跳一次記憶體。

手刻一個 compact 動態陣列：ArrayList

講義用原生 new[] 自己刻了一個簡化版 vector（pythonds3/cppds/arraylist.hpp），把「動態陣列到底在做什麼」攤開來看。幾個值得停下來看的細節：解構子要 delete[]（自己配置的自己收）、 operator[] 回傳參考（讀寫共用一個運算子）、insert 與 remove 都要搬移元素，而且容量滿了 grow() 會開一個兩倍大的新陣列搬家：vector 的 push_back 底下就是這件事。

骨架與索引 CODE

class ArrayList {
    int maxSize, lastIndex;
    int *myArray;            // 原生動態陣列
  public:
    ArrayList(int cap = 8) {
        maxSize = cap;  lastIndex = 0;
        myArray = new int[maxSize];
    }
    ~ArrayList() { delete[] myArray; }  // 誰配置誰釋放
    int size() { return lastIndex; }
    bool isEmpty() { return lastIndex == 0; }
    int& operator[](int idx) {
        if (0 <= idx && idx < lastIndex) return myArray[idx];
        throw out_of_range("index out of bounds");
    }   // 回傳參考：a[i] 讀寫都通
};

append 與 grow()：滿了就搬兩倍大的家 CODE

void append(int val) {
    if (lastIndex == maxSize) grow();  // 滿了先搬家
    myArray[lastIndex] = val;
    lastIndex++;
}
private:
void grow() {               // 容量加倍
    maxSize = maxSize * 2;
    int* bigger = new int[maxSize];
    for (int i = 0; i < lastIndex; i++)
        bigger[i] = myArray[i];      // 整批搬過去
    delete[] myArray;            // 舊屋退租
    myArray = bigger;
}

搬一次是 O(n)，但加倍策略讓搬家越來越少發生：平均每次 append 攤到 O(1)。第 2 章用「n 加倍、量時間」抓 push_back 的行為，抓到的就是這個。

insert / remove：搬移的真面目 CODE

void insert(int idx, int val) {
    if (lastIndex == maxSize) grow();
    for (int i = lastIndex; i > idx; i--)
        myArray[i] = myArray[i - 1];   // 右移讓位
    myArray[idx] = val;  lastIndex++;
}
void remove(int val) {
    找到 val 所在的 i;
    for (int j = i; j < lastIndex - 1; j++)
        myArray[j] = myArray[j + 1];   // 左移補洞
    lastIndex--;
}

第 2 章說 vector 的 insert/erase 是 O(n)，這兩個迴圈就是那個 n 的本體。講義的完整版還有 erase(idx)（照索引左移補洞）與 display()。

QUIZ · cache 效應

走訪加總 10⁶ 個 int，compact 版比 referential 版快很多，主因是？

(A) 連續記憶體對 CPU cache 友善

(B) 指標比 int 大

QUIZ · grow() 的攤銷成本

從空的 ArrayList 連續 append n 個元素（容量 8 起跳、滿了加倍）。總共搬移了大約幾個元素？

(A) 約 n 個：平均每次 append 攤到 O(1)

(B) 約 n² 個

講義 03 · compact 與 referential 的空間帳

using namespace std;
int primes[] = {2, 3, 5, 7, 11, 13, 17, 19};
 
cout << sizeof(primes[0]) << " bytes per element" << endl;
cout << sizeof(primes) << " bytes in total" << endl;
cout << sizeof(primes) / sizeof(primes[0]) << " elements" << endl;
 
string* names[3];   // referential array：3 根指標，各 8 bytes
cout << sizeof(names) << " bytes for three pointers" << endl;
 

預期輸出

4 bytes per element
32 bytes in total
8 elements
24 bytes for three pointers

sizeof(陣列) / sizeof(第一個元素) 是經典的「元素個數」算法（只在原生陣列上有效，退化成指標後就失靈）。referential 版本存的是指標：資料本體另外住，陣列只付 3 × 8 bytes 的「門牌費」。

PART 03 · 多維

多維陣列：row-major 的攤平公式課程補充 A.3

記憶體是一維的，二維陣列只是「攤平」。C++ 標準保證 row-major： M[0][0], M[0][1], M[1][0] 在記憶體裡連續排列，印位址就能親眼看到。定位公式：

y = x + (Cols × i + j) × sizeof(元素)（x 是起始位址、Cols 是每列的欄數；括號內是攤平後的索引，再乘元素大小才是位址）

Fortran 和 MATLAB 用 column-major（整欄放完才放下一欄）；C++ 沒有內建這種佈局，需要的話自己開一維陣列、把公式的 i、j 對調。記住一個原則就夠了：走訪順序跟佈局一致才快。

速度

效能後果

row-major 佈局下，for i for j a[i][j] 是順著記憶體走（cache 友善）；內外圈對調就變成每步跳 4×行數 bytes：大矩陣可差 5~10 倍。

C++ 寫法

int a[3][4]; // 真 2D
vector<vector<int>> v; // 列指標
// 後者每列各自配置，非連續！

講義完整範例：二維陣列的每一種看法

講義 03 · 宣告、走列、走行、看位址

using namespace std;
int M[2][2] = {{1, 1}, {2, 2}};   // 巢狀大括號初始化

cout << "M has " << sizeof(M) / sizeof(M[0]) << " rows and "
     << sizeof(M[0]) / sizeof(M[0][0]) << " columns, "
     << sizeof(M) << " bytes in total" << endl;
 
for (int j = 0; j < 2; j++) cout << M[0][j] << " ";   // 第 0 列
cout << endl;
for (int i = 0; i < 2; i++) cout << M[i][0] << " ";   // 第 0 行
cout << endl;
 
cout << &M[0][0] << " " << &M[0][1] << endl;   // 差 4 bytes
cout << &M[1][0] << " " << &M[1][1] << endl;   // 下一列緊接著

示範執行（位址每次不同）

M has 2 rows and 2 columns, 16 bytes in total
1 1 
1 2 
0x7ffe013c4e50 0x7ffe013c4e54
0x7ffe013c4e58 0x7ffe013c4e5c

四個位址一路 +4：C++ 的二維陣列就是「一條連續記憶體」按 row-major 攤平。M[1][0] 緊跟在 M[0][1] 後面，中間沒有縫。

講義 03 · 動手攤平：column-major 版

using namespace std;
int flat[4];
int rows = 2, cols = 2;
int M[2][2] = {{1, 1}, {2, 2}};
 
for (int i = 0; i < rows; i++)
    for (int j = 0; j < cols; j++)
        flat[j * rows + i] = M[i][j];   // column-major：j*Rows + i

for (int k = 0; k < 4; k++) cout << flat[k] << " ";
cout << endl;
 

預期輸出

1 2 1 2

column-major 的攤平公式是 j*Rows + i，一行一行直著放。輸出 1 2 1 2 就是「第 0 行、第 1 行」依序排開。

講義 03 · 練習：用平面索引找 student[5][3]

#include <cassert>
#include <iostream>
using namespace std;
 
int main() {
    int student[100][4];
    for (int i = 0; i < 100; i++)
        for (int j = 0; j < 4; j++) student[i][j] = i * 4 + j;
    int* s = &student[0][0];   // 把二維陣列當一維看
    // 把 ? 換成你的答案
    assert(student[5][3] == s[?]);
    cout << "Pass" << endl;
    return 0;
}
 

填對之後的輸出

Pass

row-major 公式 i*Cols + j = 5×4 + 3 = 23。assert 是驗收利器：條件為假直接中止程式，考自己最誠實。

PART 04 · 稀疏矩陣

稀疏矩陣：只存非零，空間從 O(mn) 降到 O(nnz) 課程補充 A.4

推薦系統的「使用者×商品」矩陣 99.9% 是 0：整片存起來是浪費。 COO（座標表：三條平行陣列 row/col/val）適合建構與批次運算； DOK（dictionary of keys：map 以 (r,c) 當 key）適合隨機讀寫。

DOK 實作 CODE

class SparseMatrix {     // 講義說明版（課程 sparsematrix.hpp 沒有 nnz()／sparsity()，自己補很容易）
    map<pair<size_t,size_t>, double> data;  // (r,c) → 值
  public:  // 讀：const 版，查不到回 0
    double operator()(size_t i, size_t j) const {
        auto it = data.find({i, j});
        return it != data.end() ? it->second : 0.0;
    }
    // 寫：非 const 版，m(i,j)=v 查無此位置時插入
    double& operator()(size_t i, size_t j) { return data[{i, j}]; }
    size_t nnz() const { return data.size(); }
    double sparsity(size_t rows, size_t cols) const {
        return 1.0 - double(data.size()) / (rows * cols);
    }   // 維度用參數傳入，類別本身不存 rows/cols
};

稀疏度（sparsity）

完整的 SparseMatrix 類別（pythonds3/cppds/sparsematrix.hpp）

講義把 DOK 寫成一個可運算的類別：讀寫共用 operator()（const 版查不到回 0、非 const 版會插入）、nnz() 數非零項、sparsity() 算稀疏度（這兩個是講義說明版的方法，課程 sparsematrix.hpp 沒有，自己補很容易），連加法和乘法都直接在稀疏表示上做，完全不用把矩陣展開。一個容易誤會的細節：m(i,j) = 0 寫進去的 0 也會佔一個項目，類別不會自動把它刪掉（上面的互動格子「點一下歸零」是示範用的簡化）：

稀疏加法 CODE

SparseMatrix operator+(const SparseMatrix& other) {
    SparseMatrix result;
    for (item : data)          // 自己的非零項
        result[item.pos] = item.val + other(item.pos);
    for (item : other.data)    // 對方獨有的非零項
        if (data 沒有 item.pos) result[item.pos] = item.val;
    return result;   // 成本只跟 nnz 有關，跟 m×n 無關
}

稀疏乘法 CODE

SparseMatrix operator*(const SparseMatrix& other) {
    SparseMatrix result;
    for (item1 : data)
        for (item2 : other.data)
            if (item1 的欄 == item2 的列)
                result(item1.列, item2.欄)
                    += item1.val * item2.val;
    return result;  // 只在非零×非零時才有工作
}

A.4.3 第三種表示：每列一條串列

講義最後給了一張圖：整個矩陣是一個「列陣列」，每列掛一條鏈結串列，節點存（欄號、值、next 指標）。同一列的非零項照欄號串起來，逐列運算（例如稀疏矩陣相加）變成兩條串列的合併。這是下一章鏈結串列的預告：等你學完 ch4，回頭就能自己實作這個版本。

QUIZ · 稀疏運算的成本

兩個 10⁵×10⁵、各有 10⁶ 個非零項的矩陣用 DOK 相加，工作量大約跟什麼成正比？

(A) 兩邊 nnz 的總和（約 2×10⁶ 項）

(B) 矩陣尺寸 10⁵ × 10⁵

QUIZ · 什麼時候划算？

5×6 的 double 矩陣（8B/值）。DOK 每個非零項約需 24B（key+值+map 開銷）。幾個非零以下 DOK 才省空間？

(A) 約 10 個以下

(B) 永遠划算

講義 03 · SparseMatrix 使用畫面：加減乘一次看

#include <iostream>
#include "pythonds3/cppds/sparsematrix.hpp"
using namespace std;
 
int main() {
    vector<vector<double>> denseMatrix = {{1, 0, 0}, {0, 2, 0}, {0, 0, 3}};
    SparseMatrix sparseMatrix;
    sparseMatrix.fromDenseMatrix(denseMatrix);
    cout << sparseMatrix << endl;
 
    SparseMatrix matrix1({{{0, 1}, 1}, {{1, 1}, 2}, {{2, 2}, 3}});
    SparseMatrix matrix2({{{1, 1}, 3}, {{2, 2}, 4}});
 
    cout << matrix1 + matrix2 << endl;
    cout << matrix1 - matrix2 << endl;
    cout << matrix1 * matrix2 << endl;
    return 0;
}
 

預期輸出

(0, 0): 1  (1, 1): 2  (2, 2): 3  
(0, 1): 1  (1, 1): 5  (2, 2): 7  
(0, 1): 1  (1, 1): -1  (2, 2): -1  
(0, 1): 3  (1, 1): 6  (2, 2): 12

乘法那行值得慢讀：DOK 版本的矩陣乘法只要「A 的 (i, k) 遇上 B 的 (k, j)」才產生貢獻，兩層迴圈都只走非零元素。(0,1)×(1,1) 給 (0,1)：3；(1,1)×(1,1) 給 (1,1)：6；(2,2)×(2,2) 給 (2,2)：12。

EXERCISES · 練習

動手驗證課程補充綜合

EXERCISE 1 · 位址計算

double a[100]（8B/格）base = 2000。&a[13] 是？

(A) 2104

(B) 2013

EXERCISE 2 · row-major

int a[3][4] base=1000（int=4B）。&a[2][1] 是？

(A) 1036

(B) 1024

EXERCISE 4 · 講義練習：students 陣列

100×4 的陣列，students[0][0] 的位址是 0、每個元素佔 1 格、row-major。students[7][2] 的位址是？

(A) 30

(B) 702

EXERCISE 3 · 結構選擇

10⁵×10⁵ 矩陣、約 10⁶ 個非零、需要頻繁「讀寫任意 (r,c)」。選哪個？

(A) DOK（map/unordered_map）

(B) COO 三陣列

REFERENCE · 總覽

陣列家族總覽課程補充總覽

結構	空間	讀 (r,c)/[i]	強項	弱項
compact array / vector	O(n)	O(1)	cache 友善、零 overhead	等寬元素、中間插刪 O(n)
referential array	O(n)+物件	O(1)+一跳	元素可異質/可共享	cache 不友善
2D row-major	O(mn)	O(1)	整片連續、公式定位	走訪順序敏感
稀疏 COO	O(nnz)	O(nnz)	建構、批次運算	隨機存取慢
稀疏 DOK	O(nnz)	O(log nnz)/O(1)	隨機讀寫	每項 overhead 大