OVERVIEW
Sparse Matrix 又名稀疏矩陣，意思是一個矩陣超多零；使用一般的矩陣註記方法，有浪費空間之虞，所以產生了列表式的註記法，如以下舉例：
我們給定一個稀疏矩陣$ \boldsymbol{M}$，其中矩陣內容為： $$ \boldsymbol{M} = \begin{bmatrix} 15 & 0 & 0 & 22 & 0 & -15 \newline 0 & 11 & 3 & 0 & 0 & 0 \newline 0 & 0 & 0 & -6 & 0 & 0 \newline 0 & 0 & 0 & 0 & 0 & 0 \newline 91 & 0 & 0 & 0 & 0 & 0 \newline 0 & 0 & 28 & 0 & 0 & 0 \newline \end{bmatrix} $$ 轉化為稀疏矩陣記法為：
| # | Row | Col | Val |
|---|---|---|---|
a[0] |
6 | 6 | 8 |
a[1] |
0 | 0 | 15 |
a[2] |
0 | 3 | 22 |
a[3] |
0 | 5 | -15 |
a[4] |
1 | 1 | 11 |
a[5] |
1 | 2 | 3 |
a[6] |
2 | 3 | -6 |
a[7] |
4 | 0 | 91 |
a[8] |
5 | 2 | 28 |
其中 a[0] 記錄著 $\boldsymbol{M}$ 矩陣有幾個 row 幾個 column 和非零 value 的總數，其餘所記載的是該元素在第幾個 row 第幾個 col 然後他的元素值為何；所以，解釋下來為：此 $\boldsymbol{M}$ 為 6 乘 6 的矩陣，其中非零值有 8 個；而事實上這種註記方法可以節省掉不少的空間。
在此我們用C的struct去註記這個稀疏矩陣記法：
typedef struct {
int row;
int col;
int val;
} term;
這樣的話，a[6].row為 2、 a[6].col為 3 ，以此類推。
稱呼
因為我實在搞不懂 row column 到底誰是行誰是列，所以我們以下都是 row column 這樣叫，其中有幾點需要注意：
我們在稱 a.row 時，代表在 a 稀疏矩陣裡面的某一條 row。
我們在稱 a.col 時，代表在 a 稀疏矩陣裡面的某一條 column。
我們在稱 b.row 時，代表在 b 稀疏矩陣裡面的某一條 row。
我們在稱 b.col 時，代表在 b 稀疏矩陣裡面的某一條 column。
稱呼 data row 時，代表是稀疏矩陣記法內某一條的資料，每一條 data row 應包含 <row, col, val> 這三項資訊。
單純稱呼 row 與 column，代表矩陣的 row 及 column。
TYPICAL SPARSE MATRIX TRANSPOSE
最基礎的矩陣轉置其實就是 row 與 column 之間的 value 交換，也是我們在手寫矩陣轉置運算時，最為直覺的方法，我們重用矩陣 $\boldsymbol{M}$ ，我們註記轉置後的矩陣為 $\boldsymbol{M}^T$：
$$ \boldsymbol{M}^T = \begin{bmatrix} 15 & 0 & 0 & 0 & 91 & 0 \newline 0 & 11 & 0 & 0 & 0 & 0 \newline 0 & 3 & 0 & 0 & 0 & 28 \newline 22 & 0 & -6 & 0 & 0 & 0 \newline 0 & 0 & 0 & 0 & 0 & 0 \newline 15 & 0 & 0 & 0 & 0 & 0 \newline \end{bmatrix} $$ 我們用最基礎的數學註記法，其中： $$ [\boldsymbol{M}^T]_{ij} = [\boldsymbol{M}]_{ji} $$ 亦即，比如說我們有一個「4」這個值，放在矩陣 $i=5$，$j=8$的位置，那他的轉置後的位置就在$i=8$，$j=5$。但是在稀疏矩陣記法內，我們要保證每一筆 data row 裡面的 row 值保持遞增的情形，在數筆 data row 有相同 row 值時，要保持著 column 值遞增情形，而非單純的 i 、 j 值交換；據此，我們有一套流程：
void transpose(term a[], term b[]){
b[0].row = a[0].col;
b[0].col = a[0].row;
b[0].val = a[0].val;
int current_record = 1;
for (int i = 0; i < a[0].col; i++) {
for (int j = 1; j <= a[0].val; j++) {
if (a[j].col == i) {
b[current_record].row = a[j].col;
b[current_record].col = a[j].row;
b[current_record].val = a[j].val;
current_record++;
}
}
}
}
這個程式大概是這樣跑的，先放上 a 稀疏矩陣內容：
| row | col | val |
a[0] | 6 | 6 | 8 |
a[1] | 0 | 0 | 15 |
a[2] | 0 | 3 | 22 |
a[3] | 0 | 5 | -15 |
a[4] | 1 | 1 | 11 |
a[5] | 1 | 2 | 3 |
a[6] | 2 | 3 | -6 |
a[7] | 4 | 0 | 91 |
a[8] | 5 | 2 | 28 |
關於第一層迴圈：
/* 第一層迴圈，我們記作 first_loop */
for (int i = 0; i < a[0].col; i++) {
...
}
其實就是我現在要讀取哪一個原始矩陣 column 當成我的轉置後矩陣的 row；比如說i就是我現在要瞄準 a 第i個 column 要寫進 b 的第 i 個 row。
關於第二層迴圈：
/* 第二層迴圈，我們記作 second_loop */
for (int j = 1; j <= a[0].val; i++) {
...
}
就是說我每一個值（也就是a[1]到a[8]）都要看過，為啥要看過，要看下面的if在幹嘛：
/* 第二層迴圈裡面，我們記作 second_loop_inside */
if (a[j].col == i) {
b[current_record].row = a[j].col;
b[current_record].col = a[j].row;
b[current_record].val = a[j].val;
current_record++;
}
就是說，因為我要保證我轉置出來的 b的資料 b.row 都是以遞增形式增長，所以我必須要從 b.row == 0 的時候開始看起，而 b.row 又是 a.col 轉置後的結果，所以會先去看 a data row 裡面所有（第二層迴圈的功用） a.col 等於 0 的情況（也就是 if (a[j].col == i)的功用了）先寫進去 b 裡面，隨時記錄 b 寫到哪一條了（也就是current_record的功用），以此類推。
就好比說，我今天有五種水果，香蕉、鳳梨、芭樂、蘋果和西瓜，全部混在一起要做分類，香蕉要放在香蕉區、鳳梨要放在鳳梨區等等，典型的方法就好像是我今天先分香蕉，水果一顆一顆挑起來看，是香蕉的就挑出來放在香蕉區，其他不是香蕉的先不要管。
我們實際跑幾輪看看：
第一輪
/* first_loop i = 0: 所以我只看 col 為 0 的時候 */
/* second_loop j = 1: 所以先看 a[j] 也就是 a[1] 的時候 */
/* second_loop_inside: 看看 a[1].col 是否為 i 也就是 0 */
| row | col | val | 符合 if?
a[0] | 6 | 6 | 8 |
a[1] | 0 | 0 | 15 | O
a[2] | 0 | 3 | 22 |
a[3] | 0 | 5 | -15 |
a[4] | 1 | 1 | 11 |
a[5] | 1 | 2 | 3 |
a[6] | 2 | 3 | -6 |
a[7] | 4 | 0 | 91 |
a[8] | 5 | 2 | 28 |
/* 此時，current_record 為 1，轉置，寫進 b[current_record] 裡 */
| row | col | val |
b[0] | 6 | 6 | 8 |
b[1] | 0 | 0 | 15 |
/* current_record++，current_record 變成 2 */
/* second_loop j = 2: 所以先看 a[j] 也就是 a[2] 的時候 */
/* second_loop_inside: 看看 a[2].col 是否為 i 也就是 0 */
| row | col | val | 符合 if?
a[0] | 6 | 6 | 8 | 不比對
a[1] | 0 | 0 | 15 | O
a[2] | 0 | 3 | 22 | X
a[3] | 0 | 5 | -15 |
a[4] | 1 | 1 | 11 |
a[5] | 1 | 2 | 3 |
a[6] | 2 | 3 | -6 |
a[7] | 4 | 0 | 91 |
a[8] | 5 | 2 | 28 |
/* 不符合 if 跳過 */
/* second_loop j = 3: 所以先看 a[j] 也就是 a[3] 的時候 */
/* second_loop_inside: 看看 a[3].col 是否為 i 也就是 0 */
| row | col | val | 符合 if?
a[0] | 6 | 6 | 8 | 不比對
a[1] | 0 | 0 | 15 | O
a[2] | 0 | 3 | 22 | X
a[3] | 0 | 5 | -15 | X
a[4] | 1 | 1 | 11 |
a[5] | 1 | 2 | 3 |
a[6] | 2 | 3 | -6 |
a[7] | 4 | 0 | 91 |
a[8] | 5 | 2 | 28 |
/* 不符合 if 跳過 */
/* second_loop j = 4: 所以先看 a[j] 也就是 a[4] 的時候 */
/* second_loop_inside: 看看 a[4].col 是否為 i 也就是 0 */
| row | col | val | 符合 if?
a[0] | 6 | 6 | 8 | 不比對
a[1] | 0 | 0 | 15 | O
a[2] | 0 | 3 | 22 | X
a[3] | 0 | 5 | -15 | X
a[4] | 1 | 1 | 11 | X
a[5] | 1 | 2 | 3 |
a[6] | 2 | 3 | -6 |
a[7] | 4 | 0 | 91 |
a[8] | 5 | 2 | 28 |
/* 不符合 if 跳過 */
/* second_loop j = 5: 所以先看 a[j] 也就是 a[5] 的時候 */
/* second_loop_inside: 看看 a[5].col 是否為 i 也就是 0 */
| row | col | val | 符合 if?
a[0] | 6 | 6 | 8 | 不比對
a[1] | 0 | 0 | 15 | O
a[2] | 0 | 3 | 22 | X
a[3] | 0 | 5 | -15 | X
a[4] | 1 | 1 | 11 | X
a[5] | 1 | 2 | 3 | X
a[6] | 2 | 3 | -6 |
a[7] | 4 | 0 | 91 |
a[8] | 5 | 2 | 28 |
/* 不符合 if 跳過 */
/* second_loop j = 6: 所以先看 a[j] 也就是 a[6] 的時候 */
/* second_loop_inside: 看看 a[6].col 是否為 i 也就是 0 */
| row | col | val | 符合 if?
a[0] | 6 | 6 | 8 | 不比對
a[1] | 0 | 0 | 15 | O
a[2] | 0 | 3 | 22 | X
a[3] | 0 | 5 | -15 | X
a[4] | 1 | 1 | 11 | X
a[5] | 1 | 2 | 3 | X
a[6] | 2 | 3 | -6 | X
a[7] | 4 | 0 | 91 |
a[8] | 5 | 2 | 28 |
/* 不符合 if 跳過 */
/* second_loop j = 7: 所以先看 a[j] 也就是 a[7] 的時候 */
/* second_loop_inside: 看看 a[7].col 是否為 i 也就是 0 */
| row | col | val | 符合 if?
a[0] | 6 | 6 | 8 | 不比對
a[1] | 0 | 0 | 15 | O
a[2] | 0 | 3 | 22 | X
a[3] | 0 | 5 | -15 | X
a[4] | 1 | 1 | 11 | X
a[5] | 1 | 2 | 3 | X
a[6] | 2 | 3 | -6 | X
a[7] | 4 | 0 | 91 | O
a[8] | 5 | 2 | 28 |
/* 此時，current_record 為 2，轉置，寫進 b[current_record] 裡 */
| row | col | val |
b[0] | 6 | 6 | 8 |
b[1] | 0 | 0 | 15 |
b[2] | 0 | 4 | 91 |
/* current_record++，current_record 變成 3 */
/* second_loop j = 8: 所以先看 a[j] 也就是 a[8] 的時候 */
/* second_loop_inside: 看看 a[8].col 是否為 i 也就是 0 */
| row | col | val | 符合 if?
a[0] | 6 | 6 | 8 | 不比對
a[1] | 0 | 0 | 15 | O
a[2] | 0 | 3 | 22 | X
a[3] | 0 | 5 | -15 | X
a[4] | 1 | 1 | 11 | X
a[5] | 1 | 2 | 3 | X
a[6] | 2 | 3 | -6 | X
a[7] | 4 | 0 | 91 | O
a[8] | 5 | 2 | 28 | X
/* 不符合 if 跳過 */
/* 結束第 1 輪 first_loop 迴圈 */
第二輪
/* first_loop i = 1: 所以我只看 col 為 1 的時候 */
/* second_loop j = 1: 所以先看 a[j] 也就是 a[1] 的時候 */
/* second_loop_inside: 看看 a[1].col 是否為 i 也就是 1 */
| row | col | val | 符合 if?
a[0] | 6 | 6 | 8 |
a[1] | 0 | 0 | 15 | X
a[2] | 0 | 3 | 22 |
a[3] | 0 | 5 | -15 |
a[4] | 1 | 1 | 11 |
a[5] | 1 | 2 | 3 |
a[6] | 2 | 3 | -6 |
a[7] | 4 | 0 | 91 |
a[8] | 5 | 2 | 28 |
/* 不符合 if 跳過 */
/* second_loop j = 2: 所以先看 a[j] 也就是 a[2] 的時候 */
/* second_loop_inside: 看看 a[2].col 是否為 i 也就是 1 */
| row | col | val | 符合 if?
a[0] | 6 | 6 | 8 | 不比對
a[1] | 0 | 0 | 15 | X
a[2] | 0 | 3 | 22 | X
a[3] | 0 | 5 | -15 |
a[4] | 1 | 1 | 11 |
a[5] | 1 | 2 | 3 |
a[6] | 2 | 3 | -6 |
a[7] | 4 | 0 | 91 |
a[8] | 5 | 2 | 28 |
/* 不符合 if 跳過 */
/* second_loop j = 3: 所以先看 a[j] 也就是 a[3] 的時候 */
/* second_loop_inside: 看看 a[3].col 是否為 i 也就是 1 */
| row | col | val | 符合 if?
a[0] | 6 | 6 | 8 | 不比對
a[1] | 0 | 0 | 15 | X
a[2] | 0 | 3 | 22 | X
a[3] | 0 | 5 | -15 | X
a[4] | 1 | 1 | 11 |
a[5] | 1 | 2 | 3 |
a[6] | 2 | 3 | -6 |
a[7] | 4 | 0 | 91 |
a[8] | 5 | 2 | 28 |
/* 不符合 if 跳過 */
/* second_loop j = 4: 所以先看 a[j] 也就是 a[4] 的時候 */
/* second_loop_inside: 看看 a[4].col 是否為 i 也就是 1 */
| row | col | val | 符合 if?
a[0] | 6 | 6 | 8 | 不比對
a[1] | 0 | 0 | 15 | X
a[2] | 0 | 3 | 22 | X
a[3] | 0 | 5 | -15 | X
a[4] | 1 | 1 | 11 | O
a[5] | 1 | 2 | 3 |
a[6] | 2 | 3 | -6 |
a[7] | 4 | 0 | 91 |
a[8] | 5 | 2 | 28 |
/* 此時，current_record 為 3，轉置，寫進 b[current_record] 裡 */
| row | col | val |
b[0] | 6 | 6 | 8 |
b[1] | 0 | 0 | 15 |
b[2] | 0 | 4 | 91 |
b[3] | 1 | 1 | 11 |
/* current_record++，current_record 變成 4 */
/* second_loop j = 5: 所以先看 a[j] 也就是 a[5] 的時候 */
/* second_loop_inside: 看看 a[5].col 是否為 i 也就是 1 */
| row | col | val | 符合 if?
a[0] | 6 | 6 | 8 | 不比對
a[1] | 0 | 0 | 15 | X
a[2] | 0 | 3 | 22 | X
a[3] | 0 | 5 | -15 | X
a[4] | 1 | 1 | 11 | O
a[5] | 1 | 2 | 3 | X
a[6] | 2 | 3 | -6 | X
a[7] | 4 | 0 | 91 |
a[8] | 5 | 2 | 28 |
/* 不符合 if 跳過 */
/* second_loop j = 6: 所以先看 a[j] 也就是 a[6] 的時候 */
/* second_loop_inside: 看看 a[6].col 是否為 i 也就是 1 */
| row | col | val | 符合 if?
a[0] | 6 | 6 | 8 | 不比對
a[1] | 0 | 0 | 15 | X
a[2] | 0 | 3 | 22 | X
a[3] | 0 | 5 | -15 | X
a[4] | 1 | 1 | 11 | O
a[5] | 1 | 2 | 3 | X
a[6] | 2 | 3 | -6 | X
a[7] | 4 | 0 | 91 | X
a[8] | 5 | 2 | 28 | X
/* 不符合 if 跳過 */
/* second_loop j = 7: 所以先看 a[j] 也就是 a[7] 的時候 */
/* second_loop_inside: 看看 a[7].col 是否為 i 也就是 1 */
| row | col | val | 符合 if?
a[0] | 6 | 6 | 8 | 不比對
a[1] | 0 | 0 | 15 | X
a[2] | 0 | 3 | 22 | X
a[3] | 0 | 5 | -15 | X
a[4] | 1 | 1 | 11 | O
a[5] | 1 | 2 | 3 | X
a[6] | 2 | 3 | -6 | X
a[7] | 4 | 0 | 91 | X
a[8] | 5 | 2 | 28 |
/* 不符合 if 跳過 */
/* second_loop j = 8: 所以先看 a[j] 也就是 a[8] 的時候 */
/* second_loop_inside: 看看 a[8].col 是否為 i 也就是 0 */
| row | col | val | 符合 if?
a[0] | 6 | 6 | 8 | 不比對
a[1] | 0 | 0 | 15 | X
a[2] | 0 | 3 | 22 | X
a[3] | 0 | 5 | -15 | X
a[4] | 1 | 1 | 11 | O
a[5] | 1 | 2 | 3 | X
a[6] | 2 | 3 | -6 | X
a[7] | 4 | 0 | 91 | X
a[8] | 5 | 2 | 28 | X
/* 不符合 if 跳過 */
/* 結束第 2 輪 first_loop 迴圈 */
以此類推，推完迴圈。
但是這樣有兩層迴圈，在分析上時間複雜度最差可以到平方項，所以有更快的方法，稱之為 Fast Matrix Transpose。
FAST SPARSE MATRIX TRANSPOSE
這個演算法利用以空間換取時間的方式，壓縮本來 Typical Sparse Matrix Transpose 方法所需時平方項次的時間複雜度。簡單來說，在這個演算法裡面，我們利用額外的註記，去加速我們的運算。
| 演算法 | b[] 行為模式 | a[] 行為模式 |
|---|---|---|
| Typical | 按照順序寫 | 鎖定第 i 個 a.col，逐條挑出 a[].col == i 者，轉置，寫入 b[] 內。 |
| Fast | 跳著寫 | 逐條看，看了之後轉置，去看看要寫去 b[] 的哪邊 |
在 Fast 演算法時，我看完 a[] 其實就已經寫完 b[] 了；而 Typical 我還不知道要看幾遍 a[] 才能寫完 b[]。
再以水果的例子說明，我今天也是有五種水果，香蕉、鳳梨、芭樂、蘋果和西瓜，全部混在一起要做分類，香蕉要放在香蕉區、鳳梨要放在鳳梨區等等，快速的方法就是我今天挑到啥水果就放到對應的區域裡就行了；當然綜觀的方法可以這樣比喻，但是實際上要實作需要考量到一些問題才能進行這樣有效的方法。
要如何實現「跳著寫」這個問題，我們就必須額外開一張表去註記「我們這個東西究竟要寫去哪裡」。
所以說，在此，我們開兩個矩陣去註記一些東西：nonZeroRow和startingPos
nonZeroRow是註記每一個原始稀疏矩陣 col 裡面，有幾個 row 是有非零值的。
startingPos是註記這個原始稀疏矩陣 col 轉置後變成新的稀疏矩陣 row 後要從哪一個 b（新稀疏矩陣） index 開始寫起。
據此幾個概念，我們形成了一些程式碼：
void fastTranspose(term a[], term b[]) {
int nonZeroRow[MAX_COL] = {0}, startingPos[MAX_COL] = {0};
b[0].col = a[0].row;
b[0].row = a[0].col;
b[0].val = a[0].val;
for (int i = 1; i <= a[0].val; i++) {
nonZeroRow[a[i].col]++;
}
startingPos[0] = 1;
for (int i = 1; i <= a[0].col; i++) {
startingPos[i] = startingPos[i-1] + nonZeroRow[i-1];
}
for (int i = 1; i <= a[0].val; i++) {
int j = startingPos[a[i].col]++;
b[j].row = a[i].col;
b[j].col = a[i].row;
b[j].val = a[i].val;
}
}
首先，第一隻迴圈
for (int i = 1; i <= a[0].val; i++) {
nonZeroRow[a[i].col]++;
}
我們是要計算固定一個矩陣 col，該 col 有多少非 0 值；由於稀疏矩陣記法已經撇除登記 0 值，所以計算每條 a.col 出現的次數，即可得到該矩陣各 col 所擁有的非 0 值。
而 staringPos[0] = 1代表，我從b[1]開始寫起（b[0]是註記稀疏矩陣資訊，不能寫的）
startingPos[0] = 1;
第二隻迴圈，是要註記每一條矩陣 col 個別要寫到哪一個 b 的 data row 位置
for (int i = 1; i <= a[0].col; i++) {
startingPos[i] = startingPos[i-1] + nonZeroRow[i-1];
}
每一個 startingPos 都是由上一個 startingPos位置 和 上一個nonZeroRow的個數加總起來的新位置；因為我們有記錄每一條 col 所擁有的非 0 值元素個數，每一條 col 起始第一個非 0 元素值都會有一個 startingPos再加上該 col 擁有的非 0 值元素個數就是下一個 col 的startingPos位置。
也就是，假若上一條 colstartingPos位置為3那我上一個條 col 的nonZeroRow有4個，此時，上一次的寫入就是已經被占用 b data row 3、4、5、6的位置，基本上你的 b data row 新位置就是起始點3再跳4格，所以是7。
接下來，第三隻迴圈：
for (int i = 1; i <= a[0].val; i++) {
int j = startingPos[a[i].col];
b[j].row = a[i].col;
b[j].col = a[i].row;
b[j].val = a[i].val;
startingPos[a[i].col]++;
}
首先取出目前這個 a.col 應該寫在 b 的哪一條 data row，然後進行轉置寫入。
接下來根據這個 a.col 的 startingPos 再往前加 1 上去（也就是我們日後要寫到相同的矩陣 col 時，新的位置應該在哪）。
就結束了，一樣我們跑個幾輪看看：
我們也把 a 矩陣放在這裡：
| row | col | val |
a[0] | 6 | 6 | 8 |
a[1] | 0 | 0 | 15 |
a[2] | 0 | 3 | 22 |
a[3] | 0 | 5 | -15 |
a[4] | 1 | 1 | 11 |
a[5] | 1 | 2 | 3 |
a[6] | 2 | 3 | -6 |
a[7] | 4 | 0 | 91 |
a[8] | 5 | 2 | 28 |
第一隻迴圈發生的事：
/* i = 1 時 */
/* a[1].col 為 0，所以 nonZeroRow[0]++ */
nonZeroRow[0] | 1
nonZeroRow[1] | 0
nonZeroRow[2] | 0
nonZeroRow[3] | 0
nonZeroRow[4] | 0
nonZeroRow[5] | 0
/* i = 2 時 */
/* a[2].col 為 3，所以 nonZeroRow[3]++ */
nonZeroRow[0] | 1
nonZeroRow[1] | 0
nonZeroRow[2] | 0
nonZeroRow[3] | 1
nonZeroRow[4] | 0
nonZeroRow[5] | 0
/* i = 3 時 */
/* a[3].col 為 5，所以 nonZeroRow[5]++ */
nonZeroRow[0] | 1
nonZeroRow[1] | 0
nonZeroRow[2] | 0
nonZeroRow[3] | 1
nonZeroRow[4] | 0
nonZeroRow[5] | 1
/* i = 4 時 */
/* a[4].col 為 1，所以 nonZeroRow[1]++ */
nonZeroRow[0] | 1
nonZeroRow[1] | 1
nonZeroRow[2] | 0
nonZeroRow[3] | 1
nonZeroRow[4] | 0
nonZeroRow[5] | 1
/* i = 5 時 */
/* a[5].col 為 2，所以 nonZeroRow[2]++ */
nonZeroRow[0] | 1
nonZeroRow[1] | 1
nonZeroRow[2] | 1
nonZeroRow[3] | 1
nonZeroRow[4] | 0
nonZeroRow[5] | 1
/* i = 6 時 */
/* a[6].col 為 3，所以 nonZeroRow[3]++ */
nonZeroRow[0] | 1
nonZeroRow[1] | 1
nonZeroRow[2] | 1
nonZeroRow[3] | 2
nonZeroRow[4] | 0
nonZeroRow[5] | 1
/* i = 7 時 */
/* a[7].col 為 0，所以 nonZeroRow[0]++ */
nonZeroRow[0] | 2
nonZeroRow[1] | 1
nonZeroRow[2] | 1
nonZeroRow[3] | 2
nonZeroRow[4] | 0
nonZeroRow[5] | 1
/* i = 8 時 */
/* a[1].col 為 2，所以 nonZeroRow[2]++ */
nonZeroRow[0] | 2
nonZeroRow[1] | 1
nonZeroRow[2] | 2
nonZeroRow[3] | 2
nonZeroRow[4] | 0
nonZeroRow[5] | 1
第二隻迴圈發生的事：註記每一條矩陣 col 轉置到新矩陣（變成新矩陣的 row）時候該擺在 b 的哪裡。
/* i = 1 時，startPos[1] 為上一次起始點 (startPos[0] == 1) 以及上一次被填了多少非零值 (nonZeroRow[0] == 2) 的總和 */
startingPos[0] | 1 // 在迴圈之前已經設定好了
startingPos[1] | 3
startingPos[2] | 0
startingPos[3] | 0
startingPos[4] | 0
startingPos[5] | 0
/* i = 2 時，startPos[2] 為上一次起始點 (startPos[1] == 3) 以及上一次被填了多少非零值 (nonZeroRow[1] == 1) 的總和 */
startingPos[0] | 1 // 在迴圈之前已經設定好了
startingPos[1] | 3
startingPos[2] | 4
startingPos[3] | 0
startingPos[4] | 0
startingPos[5] | 0
/* i = 3 時，startPos[3] 為上一次起始點 (startPos[2] == 4) 以及上一次被填了多少非零值 (nonZeroRow[2] == 2) 的總和 */
startingPos[0] | 1 // 在迴圈之前已經設定好了
startingPos[1] | 3
startingPos[2] | 4
startingPos[3] | 6
startingPos[4] | 0
startingPos[5] | 0
/* i = 4 時，startPos[4] 為上一次起始點 (startPos[3] == 6) 以及上一次被填了多少非零值 (nonZeroRow[3] == 2) 的總和 */
startingPos[0] | 1 // 在迴圈之前已經設定好了
startingPos[1] | 3
startingPos[2] | 4
startingPos[3] | 6
startingPos[4] | 8
startingPos[5] | 0
/* i = 5 時，startPos[5] 為上一次起始點 (startPos[4] == 8) 以及上一次被填了多少非零值 (nonZeroRow[4] == 0) 的總和 */
startingPos[0] | 1 // 在迴圈之前已經設定好了
startingPos[1] | 3
startingPos[2] | 4
startingPos[3] | 6
startingPos[4] | 8
startingPos[5] | 8
第三隻迴圈：開始依照startingPos填資料：
/* i = 1 時，a[1].col == 0，此時 startingPos[0] 為 1，b 從 1 寫起 */
| row | col | val |
b[0] | 6 | 6 | 8 |
b[1] | 0 | 0 | 15 |
/* startingPos[0]++，以備下一次遇到 col == 0 時使用 */
/* i = 2 時，a[2].col == 3，此時 startingPos[3] 為 6，b 從 6 寫起 */
| row | col | val |
b[0] | 6 | 6 | 8 |
b[1] | 0 | 0 | 15 |
...
b[6] | 3 | 0 | 22 |
/* startingPos[3]++，以備下一次遇到 col == 3 時使用 */
/* i = 3 時，a[3].col == 5，此時 startingPos[5] 為 8，b 從 8 寫起 */
| row | col | val |
b[0] | 6 | 6 | 8 |
b[1] | 0 | 0 | 15 |
...
b[6] | 3 | 0 | 22 |
...
b[8] | 5 | 0 | -15 |
/* startingPos[5]++，以備下一次遇到 col == 5 時使用 */
/* i = 4 時，a[4].col == 1，此時 startingPos[1] 為 3，b 從 3 寫起 */
| row | col | val |
b[0] | 6 | 6 | 8 |
b[1] | 0 | 0 | 15 |
...
b[3] | 1 | 1 | 11 |
...
b[6] | 3 | 0 | 22 |
...
b[8] | 5 | 0 | -15 |
/* startingPos[1]++，以備下一次遇到 col == 1 時使用 */
/* i = 5 時，a[5].col == 2，此時 startingPos[2] 為 4，b 從 4 寫起 */
| row | col | val |
b[0] | 6 | 6 | 8 |
b[1] | 0 | 0 | 15 |
...
b[3] | 1 | 1 | 11 |
b[4] | 2 | 1 | 3 |
...
b[6] | 3 | 0 | 22 |
...
b[8] | 5 | 0 | -15 |
/* startingPos[2]++，以備下一次遇到 col == 2 時使用 */
/* i = 6 時，a[6].col == 3，此時 startingPos[3] 為 7，b 從 4 寫起 */
| row | col | val |
b[0] | 6 | 6 | 8 |
b[1] | 0 | 0 | 15 |
...
b[3] | 1 | 1 | 11 |
b[4] | 2 | 1 | 3 |
...
b[6] | 3 | 0 | 22 |
b[7] | 3 | 2 | -6 |
b[8] | 5 | 0 | -15 |
/* startingPos[3]++，以備下一次遇到 col == 3 時使用 */
/* i = 7 時，a[7].col == 0，此時 startingPos[0] 為 2，b 從 2 寫起 */
| row | col | val |
b[0] | 6 | 6 | 8 |
b[1] | 0 | 0 | 15 |
b[2] | 0 | 4 | 91 |
b[3] | 1 | 1 | 11 |
b[4] | 2 | 1 | 3 |
...
b[6] | 3 | 0 | 22 |
b[7] | 3 | 2 | -6 |
b[8] | 5 | 0 | -15 |
/* startingPos[0]++，以備下一次遇到 col == 0 時使用 */
/* i = 8 時，a[8].col == 2，此時 startingPos[2] 為 5，b 從 5 寫起 */
| row | col | val |
b[0] | 6 | 6 | 8 |
b[1] | 0 | 0 | 15 |
b[2] | 0 | 4 | 91 |
b[3] | 1 | 1 | 11 |
b[4] | 2 | 1 | 3 |
b[5] | 2 | 5 | 28 |
b[6] | 3 | 0 | 22 |
b[7] | 3 | 2 | -6 |
b[8] | 5 | 0 | -15 |
/* startingPos[2]++，以備下一次遇到 col == 2 時使用 */
就這樣嚕。
後記：看看有沒有機會動畫化
Share this post
Twitter
Google+
Facebook
Reddit
LinkedIn
Pinterest
Email