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

CONTENTS · 內容目錄

P00低階陣列 P01位址計算 P02compact vs referential P03多維陣列 P04稀疏矩陣 EX練習題 REF總覽比較

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）。

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（dscpp/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² 個

PART 03 · 多維

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

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

y = x + Cols × i + j（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; // 列指標
// 後者每列各自配置，非連續！

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 {     // dscpp/sparsematrix.hpp（DOK）
    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 類別（dscpp/sparsematrix.hpp）

講義把 DOK 寫成一個可運算的類別：讀寫共用 operator()（const 版查不到回 0、非 const 版會插入）、nnz() 數非零項、sparsity() 算密度，連加法和乘法都直接在稀疏表示上做，完全不用把矩陣展開。一個容易誤會的細節：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) 永遠划算

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[5][3] 的位址是？

(A) 23

(B) 53

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 大

關鍵概念複習 ① O(1) 隨機存取 = 連續 + 等寬 + 一條位址公式。
② compact/referential 的差別在「值住哪」：cache 效應由此而生。
③ 多維只是攤平；走訪順序要順著佈局。
④ 稀疏結構只存非零：格式跟著存取模式選（建構用 COO、讀寫用 DOK）。

陣列的底層世界與稀疏矩陣

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

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

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