# 2020q3: quiz4
###### tags: `sysprog-2020`
> [作業說明](https://hackmd.io/@sysprog/r1z0WPWLD)
> [題目](https://hackmd.io/@sysprog/2020-quiz4)
## 開發環境
```shell
$ uname -a
Linux jonec76-Aspire-M7720 5.4.0-47-generic #51-Ubuntu SMP GNU/Linux
```
## 參考解答
OP = ^
AAA = int **
BBB = -1
CCC = 1 << i
KK1 = div5
KK2 = div3
KK3 = 2
## Q1
- 解題想法
```c=1
int hammingDistance(int x, int y) {
return __builtin_popcount(x ^ y);
}
```
可以先觀察一下圖上的點，如果兩點之間 bit 中只有 1 位不相同的話，那可以知道兩個點的距離只差 1。根據這個原則，只要找出兩個數字有多少個 bit 不同即可。
那如何找出呢？這邊可以使用 XOR 找出，因為 XOR 的特性剛好可以使不同 bit （`0^1`）出來的結果是 1，若是相同的話就會變成 0。
接著，再使用 `__builtin_popcount` 計算出有多少個 1，即可知道答案了。
### 延伸問題
1. 解釋上述程式碼運作原理，並舉出不使用 gcc extension 的 C99 實作程式碼
閱讀了 [Other-Builtins](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 的說明文件，裡頭說到
> Built-in Function: int __builtin_popcount (unsigned int x)
Returns the number of 1-bits in x.
需要注意傳入的參數要為 `unsigned int` 的型態，改寫如下
1. 暴力法
遍歷所有的 bit 並且紀錄 1 的個數。
```c=1
int _popcount(unsigned int x) {
int count = 0;
while(x){
count += (x & 1);
x >>= 1;
}
return count;
}
```
2. 二補數減法特性
閱讀 [详解二进制数中1的个数](http://github.tiankonguse.com/blog/2014/11/16/bit-count-more.html) 裡頭提到的方法，覺得蠻神奇的。
在二補數做減 `1` 時，從最右邊的 `1` 值開始往右，`1` 會變 `0` 且 `0` 會變 `1` 。舉個例子，可以看到 `101100 - 1 = 101011`
利用這個特性，再將減去後的值 `101011` 回去跟原本的值 `101100` 做 `&`，就會消去最低位 `1` 變成 `0` 了。這樣的方法不像 (1) 一樣，要遍歷所有的 bit，時間複雜度是取決於該值有多少個 `1`
```c=1
int _popcount_v2(unsigned int x) {
int count = 0;
while(x){
x &= (x - 1);
count ++;
}
return count;
}
```
3. log 法
以算法 (2) 來說，時間複雜度會依據有多少個 1 而定，也就是說當所有 bit 幾乎為 1 時，複雜度會跟 (1) 的遍歷法是差不多的。log 法的想法，跟 merge sort 提到的 divide & conquer 的切法很像，差別在於所有的子問題可以同時處理（直接相加即可，不用遞迴各個子問題），bit n 數目則時間複雜度是 log(n)。
```c=1
int _popcount_log(unsigned int x) {
uint32_t mask[]= {0x55555555,0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};
for(int i=0;i<5;i++)
x=(x & mask[i]) + ((x>>(1<<i)) & mask[i]);
return x;
}
```
使用 `mask` 是為了在兩值相加時將高位的項目（沒有用到的部分）移除，`mask` 的用法就是拿來將相鄰特定 bit 數目增加的，隨著不同的 iteration 有不同的相加方法，順序是相鄰的 1 -> 2 -> 4 -> 8 -> 16 位相加後，即可得到所有的 1 的個數。
2. 練習 [LeetCode 477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)，你應當提交 (submit) 你的實作 (C 語言實作)，並確保執行結果正確且不超時
- Submission code
- [GitHub](https://github.com/Jonec76/sysprog2020-final/blob/master/477.c)
- Submission Detail
- runtims: 32ms (80.56 %)
memory: 6.7Mb (91.67 %)
- 解題想法
在 477 題中，要求算出所有數值之間兩兩 hamming distance 並且加總。
自己嘗試過使用暴力法，也就是使用 for 迴圈跑過所有的可能組合 ( 時間 $O(n^2)$ )，並對每個組合做 `XOR` 得到一值，計算該值中的所有 1 數目，此方法會使程式執行時間 time limit。
觀察後，得到一個新的想法。能使 total hamming distance 增加，只有當 bit 值為 `0` 對上 bit 值為 `1` 時。若在某特定 bit 值下，算出有 a 個值為 `1` 且 b 個值為 `0`，那 $a*b$ 就是該 bit 值下的 total hamming distance，而計算所有 bit 之後就可得到答案。這樣的時間複雜度為 : 跑過所有數 $O(n)$ $*$ 該陣列中最大值 `max_value` 的最高 bit 數 $O(log(max\_value))$ = $O(n * log(max\_value))$
- 程式碼優化
因為程式碼執行 `if/else` 的部分會有 branch prediction cost，而第一版的程式碼是希望算出 bit 值為 `0` 跟 `1` 的各自數目，如下
```c=1
if(nums[i] & 1)
bit_1_ctr++;
else
bit_0_ctr++;
// ...
total_ham_distance += bit_0_ctr * bit_1_ctr;
```
之後更改這部分，改成只計算 `1` 的數目
```c=1
bit_1_ctr += (nums[i] & 1);
// ...
total_ham_distance += (numsSize - bit_1_ctr) * bit_1_ctr;
```
在 runtime 上從 `38.89%` 上升到 `80.56%`
3. 研讀[錯誤更正碼](https://w3.math.sinica.edu.tw/math_media/d184/18404.pdf)簡介及[抽象代數的實務應用](https://www.math.sinica.edu.tw/www/file_upload/summer/crypt2017/data/2017/%E4%B8%8A%E8%AA%B2%E8%AC%9B%E7%BE%A9/[20170710][%E6%8A%BD%E8%B1%A1%E4%BB%A3%E6%95%B8%E7%9A%84%E5%AF%A6%E5%8B%99%E6%87%89%E7%94%A8].pdf)，摘錄其中 Hamming Distance 和 Hamming Weight 的描述並重新闡述，舉出實際的 C 程式碼來解說;
- 搭配閱讀 [Hamming codes, Part I](https://www.youtube.com/watch?v=X8jsijhllIA&feature=youtu.be) 及 [Hamming codes](https://www.youtube.com/watch?v=b3NxrZOu_CE&feature=youtu.be), Part II，你可適度摘錄影片中的素材，但應當清楚標註來源
---
## Q2
- 解題方向
在解 AAA 時，可以從下方這行程式碼得出
```c=1
obj->parent = malloc(n * sizeof(int *));
```
表示 `obj->parent` 是個具有 n 個 `int *` 的 pointer，如此即可知道應為 `int **` 型態。
在解 BBB 之前，可以先了解此題題目目的，參考下方程式碼
```c=1
int max_level = 32 - __builtin_clz(n) + 1;
for (int i = 0; i < n; i++) {
obj->parent[i] = malloc(max_level * sizeof(int));
for (int j = 0; j < max_level; j++)
obj->parent[i][j] = -1;
}
```
找出 `max_level` 的方法蠻有趣的，背後含義是做了 $\lfloor log\ n\rfloor$。一開始想說應該是想要找出 n 最大會在哪個 level，但是！之後再看一次題目才知道不是這樣子（需要配合 `treeAncestorGetKthAncestor` 來看）
這邊就是建立每個點的 parent table，用來記錄該點之上的 "幾個" parent（不是所有都紀錄！），並且對每個 node 的 parent table 做初始化。
```c=1
for (int i = 0; i < parentSize; i++)
obj->parent[i][0] = parent[i];
```
接著可以看到下方 BBB 的填空
```c=1
for (int i = 0; i < parentSize; i++) {
obj->parent[i][j] = obj->parent[i][j + BBB] == -1
? -1
: obj->parent[obj->parent[i][j - 1]][j - 1];
if (obj->parent[i][j] != -1) quit = 0;
}
```
若是倒著推回來的話，可以先思考一下怎樣的情況，parent 會是 `-1`？
同時，又可以看到需要根據該點之外的其他 parent ，來更新目前的 parent。此時就可以推測出，如果在 level `j - 1` 已經是 `-1`，也就是沒有任何 node 在 level `j - 1` 之上，那 `j` 一定也不會有 parent。
接著，看到最後 CCC 選項
```c=1
int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)
{
int max_level = obj->max_level;
for (int i = 0; i < max_level && node != -1; ++i)
if (k & (CCC))
node = obj->parent[node][i];
return node;
}
```
上述程式碼蠻有趣的，是要拿第 k 個 parent。當初看到此題時，想說就是 n 往上數到第 k 個 node 並且回傳。但事實上並非如此，以下圖為例子
```graphviz
digraph skew_BST {
size="10,3!"
node [fontname="Arial"];
0 -> 1;
1 -> 2;
2 -> 3;
3 -> 4;
4 -> 5;
5 -> 6;
}
```
以例子來看，在 node 6 的 parent table 應為下圖，parent[i] 紀錄的是往上數第 $2^i$ 個點（如果存在）
```graphviz
digraph hash_table {
nodesep = .05;
rankdir = LR;
node[shape = record, width = .1, height = .1];
node0[label = "<f9> 6", height = 0.5];
node [width = 1.5];
node9[label = "{ 5|4|2}"];
node0:f9 -> node9;
}
```
why? 由下方程式碼可以看出
```c=1
for (int j = 1;; j++) {
int quit = 1;
for (int i = 0; i < parentSize; i++) {
obj->parent[i][j] = obj->parent[i][j + BBB] == -1
? -1
: obj->parent[obj->parent[i][j - 1]][j - 1];
```
以 `parent[5][1]` (node 6 往上 2 格) 來看，那就會被更新為 `parent[4][0]` (node 5 往上 1 格)。
以 `parent[5][2]` (node 6 往上 4 格) 來看，那就會被更新為 `parent[3][1]` (node 4 往上 2 格)。
這樣的紀錄方法，將會使得 `parent[i]` 紀錄的是往上數第 $2^i$ 個點。對於這樣設計的原因，自己思考後是認為這樣的設計在處理 balanced tree 和 skewed tree 時都能減少 partent table size，不必將該點之上所有的 parent 都存入。
既然如此，再回到 CCC 選項。若 node=6, k=5 時，也就是要找出 node=6 往上數第 5 個的 node。這邊以 `treeAncestorGetKthAncestor` 來看，跑法會是
1. 取出 node 6 的第 $2^0$ parent，也就是 5
2. 5 再取出第 $2^2$ 點，也就是 0
打破原先那直觀的觀念（往上走 5 步），而是用走 "2 的冪次方" 的方法取點。
### 延伸問題:
1. 解釋上述程式碼運作原理，指出可改進的地方，並實作對應的程式碼;
- 優化記憶體
- [**演(1)**] 原始程式碼
Runtime: 288 ms (47.47 %)
Memory: 70.3 MB (10%，吊車尾超出排名圖表)
可看出原始程式碼還有相當多的空間能夠進步，以下提出若干個調整
- [**演(2)**]
Runtime: 280 ms (63.16 %)
Memory: 68 MB (89.47 %)
在 [**演(1)**] 中，分配記憶體的方式如下：
```c=1
int max_level = 32 - __builtin_clz(n) + 1;
for (int i = 0; i < n; i++) {
obj->parent[i] = malloc(max_level * sizeof(int));
// ...
}
```
可以看到每個節點的 `parent_size` 會被分配到 $\lfloor log\ n\rfloor$ 的大小空間。試想如果是一棵 skewed tree 的話，那會浪費相當多的空間（越靠近 root 的 node，depth 小但是一樣要分配 max depth 的空間），於是做了以下的優化：
若以 n=8 的 skewed tree 去設想 [**演(2)**] ，建出來的 table 如下表
```graphviz
digraph hash_table {
nodesep = .05;
rankdir = LR;
node[shape = record, width = .1, height = .1];
node7:f7 -> n7;
node6:f6 -> n6;
node5:f5 -> n5;
node4:f4 -> n4;
node3:f3 -> n3;
node2:f2 -> n2;
node1:f1 -> n1;
node0:f0 -> n0;
node0[label = "<f0> 0", height = 0.5];
node1[label = "<f1> 1", height = 0.5];
node2[label = "<f2> 2", height = 0.5];
node3[label = "<f3> 3", height = 0.5];
node4[label = "<f4> 4", height = 0.5];
node5[label = "<f5> 5", height = 0.5];
node6[label = "<f6> 6", height = 0.5];
node7[label = "<f7> 7", height = 0.5];
n0[label = "{-1}"];
n1[label = "{0}"];
n2[label = "{1|0}"];
n3[label = "{2|1}"];
n4[label = "{3|2|0}"];
n5[label = "{4|3|1}"];
n6[label = "{5|4|2}"];
n7[label = "{6|5|3|0}"];
}
```
可以看出，該圖每個點的 size 就是該點的最大 parent size，不可能找到其他 tree 比 skewed tree 的深度還要更大，若是依據這樣的想法，那可以節省掉 <br> **[演(1)]** 將所有點都分配了 $\lfloor log\ n\rfloor$ 的空間。
提交 [**演(2)**] 可以得到下方結果
- [**演(3)**]
Runtime: 264 ms (97.37%)
Memory: 65 MB (100%，超過圖表範圍)
[**演(2)**] 確實減少配置記憶體空間，但仍有能改善的地方，可以看到以下的例子
```graphviz
digraph skew_BST {
size="10,3!"
node [fontname="Arial"];
0 -> 1;
0 -> 2;
0 -> 3;
0 -> 4;
0 -> 5;
0 -> 6;
}
```
若用 [**演(2)**] 的方法配置記憶體，因為大部分的點 depth=1，在 node 2~6 會有些許的浪費，那是否還有辦法能節省這些空間呢？
於是在 [**演(3)**] 裡頭使用了 `depth` 表格，依據每個 node 的深度精確的配置大小。
```c=1
typedef struct {
int *depth; // For record each depth of node
int **parent;
int max_depth;
int n;
} TreeAncestor;
for (int i = 1; i < n; i++) {
obj->depth[i] = obj->depth[parent[i]]+1;
// ...
int node_level = 32 - __builtin_clz(obj->depth[i]);
obj->parent[i] = malloc(node_level * sizeof(int));
}
```
更新 table 的部份如下：
```c=1
int bit_idx = 1;
int max_bit = 32 - __builtin_clz(max_depth) + 1;
while(bit_idx < max_bit){
int start_idx = (1 << bit_idx);
for(int j=start_idx;j<parentSize;j++){
if(32 - __builtin_clz(obj->depth[j]) <= bit_idx)
continue;
obj->parent[j][bit_idx] = obj->parent[obj->parent[j][bit_idx - 1]][bit_idx - 1];
}
bit_idx++;
}
```
`bit_idx` 會從 1 開始增加，若 node 的深度 大於 $2^{bit\_idx}$ 則更新其 parent，否則就 `continue`。多出 `depth` 表格能夠省略掉設定 `-1` 的過程，因為每個 parent array 都是剛好符合該深度，不會有多餘要設為 `-1` 的過程。
而如果在 `treeAncestorGetKthAncestor` 要找的超過深度的話，再回傳 `-1` 即可
```c=
int max_depth = obj->max_depth;
if(obj->depth[node] < k)
return -1;
```
- 優化執行時間
在 [**演(1)**] 中，更新 `obj->parent` 的演算法中，由於 `obj->parent` 的空間很大 ($O(n * log(n))$)，需要更新每格，程式碼如下
```c=1
for (int j = 1;; j++) {
int quit = 1;
for (int i = 0; i < parentSize; i++) {
// ...
}
}
```
而改善了空間配置之後，在更新 `obj->parent` 的程式碼如下
```c=1
int bit_idx = 1;
int max_bit = 32 - __builtin_clz(max_depth) + 1;
while(bit_idx < max_bit){
int start_idx = (1 << bit_idx);
for(int j=start_idx;j<parentSize;j++){
if(32 - __builtin_clz(obj->depth[j]) <= bit_idx)
continue;
obj->parent[j][bit_idx] = obj->parent[obj->parent[j][bit_idx - 1]][bit_idx - 1];
}
bit_idx++;
}
```
首先，改成跑過 `max_depth` 的 bit 數目就好，別跑過 `n` 的 bit 數。接著，若要更新 node i 的第 j 格 obj->parent[i][j]，則 i 從 $2^j$ 開始跑，不要從 `0` 開始，因為只有 node $2^j$ 才有可能有深度為 `j` 的大小。
舉個例子：
```graphviz
digraph hash_table {
nodesep = .05;
rankdir = LR;
node[shape = record, width = .1, height = .1];
node4:f4 -> n4;
node3:f3 -> n3;
node2:f2 -> n2;
node1:f1 -> n1;
node0:f0 -> n0;
node0[label = "<f0> 0", height = 0.5];
node1[label = "<f1> 1", height = 0.5];
node2[label = "<f2> 2", height = 0.5];
node3[label = "<f3> 3", height = 0.5];
node4[label = "<f4> 4", height = 0.5];
n0[label = "{-1}"];
n1[label = "{0}"];
n2[label = "{1|0}"];
n3[label = "{2|1}"];
n4[label = "{3|2|0}"];
}
```
若要更新 `j=2`，那就從 $2^j=4$ 開始更新，為何呢？
因為在 node=4 之下的 node，不可能會有 `j=2` 的可能，所以這段可以省略掉 (但是 [**演(1)**] 是每次都從頭 node=0 更新，會浪費一些時間)
另外，在 `treeAncestorGetKthAncestor` 也能加速，在 [**演(1)**] 中會透過 k 的每個 bit 去找出來答案，但有些時候 k 其實比點的深度還要大，都要花一些時間遇到 `-1` 之後才知道。透過 `depth` 表格，能夠在一開始函式獲得 `k` 的時候就立刻判斷，如果 `k` 大於深度就可以直接回傳 `-1`，節省許多時間
```c=
int max_depth = obj->max_depth;
if(obj->depth[node] < k)
return -1;
```
2. 在 treeAncestorCreate 函式內部，若干記憶體被浪費，請撰寫完整測試程式碼，並透過工具分析;
3. 在 [LeetCode 1483. Kth Ancestor of a Tree Node](https://leetcode.com/problems/kth-ancestor-of-a-tree-node/) 提交你的實作，你應該要在 C 語言項目中，執行時間領先 75% 的提交者;
- Runtime: 264 ms (97.37%)
- Memory: 65 MB (100%，超過圖表範圍)
- [Github](https://github.com/Jonec76/sysprog2020-final/blob/master/1483.c)
---
## Q3
- 程式碼分析
```c=1
if (i % 3 == 0) printf("Fizz");
if (i % 5 == 0) printf("Buzz");
if (i % 15 == 0) printf("FizzBuzz");
if ((i % 3) && (i % 5)) printf("%u", i);
```
此題的原意其實很簡單，目的就是根據以上的程式碼印出。
接著此題希望使用 `strncpy` 的方式，來複製出原始字串的 substring。複製的參數是
1. start 字串的起始位置
2. 複製的長度
複製程式碼如下：
```c=1
#define MSG_LEN 8
char fmt[MSG_LEN + 1];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
```
- 解題想法
```c=1
strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> KK1) >> (KK2 << KK3)], length);
```
此題基本上就是要把數字湊出來，在 [quiz2-Q4](https://hackmd.io/@jonec76/2020q3-quiz2#Q4) 中分析過 `is_divisible` 的原理。所以可以知道此題的 `div3` 、 `div5` 就會表示出目前的數可否被相對 `3` 或 `5` 整除，可以的話就得 `1`，否則 `0`。
以下為 output 合併 `strncpy` 參數的 table：
|value|output|start index|length|
|---|---|---|---|---|
|n 整除 3|"Fizz"|0|4|
|n 整除 5|"Buzz"|4|4|
|n 整除 15|"FizzBuzz"|0|8|
|以上皆非|n|0|0|
湊了幾組後即可得到答案。
這邊在課堂上寫的時候發生了粗心的情況，順便記錄一下。當時把 `div3 << 2` 跟 `2 << div3` 寫相反，當 `div3=1` 時的確值是一樣，但是缺少考慮了 `div3=0` 的 case。
## Q4
- 程式碼
```c=1
#include <stdint.h>
#define ffs32(x) ((__builtin_ffs(x)) - 1)
size_t blockidx;
size_t divident = PAGE_QUEUES;
blockidx = offset >> ffs32(divident);
divident >>= ffs32(divident);
switch (divident) {
CASES
}
```
- 解題想法
因為 `PAGE_QUEUES` 已知，此題希望能夠不要使用到除法，來完成 `size_t blockidx = offset / PAGE_QUEUES;` 的運算。
使用 `ffs32(x)` ，可以知道 1+(x 的最低 bit index)。若用數學式表達，可看到下方
$page\_queues = x * 2^i,\ where\ x\ is\ odd,\ i=0,1,...$
從所求分解回推：
$\ =(
{\dfrac{offset}{page\_queues}}
)$
$\ =(
{\dfrac{offset}{x * 2^i}}
)$
接著依據程式碼的算式
```c=1
blockidx = offset >> ffs32(divident);
divident >>= ffs32(divident);
```
可得：
$\ =(
{\dfrac{blockidx}{divident}}
)$
看到 `switch/case` 的要求，也就是找出所有 `divident` 的可能數，並且讓 `blocksize` 除以一個常數。
`divident` 的所有可能數，因為做了 `ffs32(divident)`，也就是對 0~8 的每個數除掉 2 的冪次方直到變奇數為止。所以所有可能為 `3`, `5`, `7`。
### 延伸問題:
1. 解釋程式運算原理，可搭配 Microsoft Research 的專案 snmalloc 來解說;
- 對應的原始程式碼 src/mem/sizeclass.h
2. 練習 [LeetCode 51. N-Queens](https://leetcode.com/problems/n-queens/)，應選擇 C 語言並善用上述的 __builtin_ffs，大幅降低記憶體開銷;
- [**演(1)**] bitwise 解法 (未優化)
[Github](https://github.com/Jonec76/sysprog2020-final/blob/master/51.c)
Runtime: 52 ms (16.81 %)
Memory: 8.3 MB (39.45 %)
(因為 `c` 的解答說明不清楚，所以改成用 `cpp` 寫)
自己試著用 bit 的觀點，來解皇后問題，想法如下：
每個棋子的「米」字方向上，都不能有任何其他的棋子存在。而 n=a 的時候要找出 a-Queen 的解答。試想若將上面的圖，用二進制來表示的話可以得到
```
0100
0001
1000
0010
```
由上而下就是 「4, 1, 8, 2」。
觀察了一下，只要找出 $2^n$ 內的所有 2 的冪次方（水平方向只有 一個 bit 為 1），且不重複（垂直方向只有一個 bit 為 1），就可以滿足 "「十」字方向不能有任何棋子" 的條件了。
接著，再把「4, 1, 8, 2」用「2, 0, 3, 1」的表示，以簡化想法。整個演算法就是找出 「0, 1, 2, 3」的所有排列，並且拿掉 "斜對角有棋子" 的情況（例：「0, 1, 2, 3」）就是答案了。
程式碼分析如下：
1. 找出 0~n 的所有排列
```c=1
int* nums = (int*)malloc(n * sizeof(int));
for(int i=0;i<n;i++)
nums[i] = i;
permute(nums, 0, n-1, ans);
// ...
for (i = l; i <= r; i++){
// ...
swap((a+l), (a+i));
permute(a, l+1, r, ans);
swap((a+l), (a+i)); //backtrack
}
```
2. 挪去對角線上有棋子的 case
```c=1
void permute(int *a, int l, int r, vector<vector<string> >& ans){
if (l == r){
bool skip = false;
for(int j=0;j<l+1;j++){
int diff = 1;
for(int k=j+1;k<l+1;k++){
if((a[j] - a[k]) == diff || (a[j] - a[k]) == -diff)
return;
diff++;
}
}
// ...
}
}
```
這部分花了 $O(n^2)$ 的時間。以例子來看，若得到 "0, 4, 2, 3" ，則會在 `j=0`, `k=2` 的時候，也就是 `a[j]` 為 `4` 且 `a[k]` 為 `2` 時因為不滿足對角項而 `return`
- [**演(2)**] bitwise 解法 (優化執行時間)
[Github](https://github.com/Jonec76/sysprog2020-final/blob/master/51_v2.cpp)
Runtime: 8 ms (74.41 %)
Memory: 8.3 MB (39.45 %)
可以看到 [**演(1)**] 的執行時間表現不佳，思考之後發現說，在做排列的遞迴時，其實若知道該 substring 中有 "斜對角有棋子" 的話，那就可以直接停止了，這樣可以減少需多重複檢查，不必將所有的可能性都跑完。
參考 [geek-permutate](https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/) 中的圖
可以發現 `permutate` 在往下遞迴時，會將 `l` 的值加 `1`去遞迴右邊的子字串。如圖中紅色的部分（`l` 的左邊）越來越多，在紅色的部分是 fixed ，也就是不會被 swap 了，所以說若在這 fix 的部分已經知道不符合 "斜對角不能有棋子" 的話，那就可以直接不用進入右邊子字串的遞迴。
程式碼如下：
```c=1
for (i = l; i <= r; i++){
bool skip = false;
if(l>1){
for(int j=1;j<l;j++)
if(((a[l-1] - a[l-1-j]) == j)||((a[l-1] - a[l-1-j]) == -j))
skip = true;
}
if(skip)
continue;
swap((a+l), (a+i));
permute(a, l+1, r, ans);
swap((a+l), (a+i)); //backtrack
}
```
有趣的是，這樣使用 bitwise 想法的做法，跟原本經典的解法在時間、空間使用率上是一樣的，所以在 [**演(3)**] 中試著用 `__builtin_ffs` 優化經典的解法。
- [**演(3)**] 經典解法 (優化執行時間)
Runtime: 4 ms (97.37 %)
Memory: 8.3 MB (39.45 %)
先看到原本經典的皇后問題解法：
```c=1
for (int i = 0; i < n; i++) {
/* Check if the queen can be placed on
board[i][col] */
if (isSafe(board, i, col, n)) {
/* Place this queen in board[i][col] */
board[i][col] = 1;
/* recur to place rest of the queens */
solvenQUtil(board, col + 1, n, ans);
/* If placing queen in board[i][col]
doesn't lead to a solution, then
remove queen from board[i][col] */
board[i][col] = 0; // BACKTRACK
}
}
/* A utility function to check if a queen can
be placed on board[row][col]. Note that this
function is called when "col" queens are
already placed in columns from 0 to col -1.
So we need to check only left side for
attacking queens */
bool isSafe(int** board, int row, int col, int n) {
int i, j;
/* Check this row on left side */
for (i = 0; i < col; i++)
if (board[row][i])
return false;
/* Check upper diagonal on left side */
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
/* Check lower diagonal on left side */
for (i = row, j = col; j >= 0 && i < n; i++, j--)
if (board[i][j])
return false;
return true;
}
```
該解法是給定一張 N*N 的 table `board`，並且從最左上角開始放棋子，若放得下 (`isSafe`) 表示該棋子滿足問題的所有條件，則 `col+1` 往下一層遞迴繼續放。由左而右的放棋子有個優點，就是在 `isSafe` 裡頭檢查棋子時，因為該行的右半邊不會有任何棋子，所以只要檢查該棋子的左半部。
接著，再看看如何嘗試使用 `__builtin_ffs` 進行優化：
```c=1
for (int i = 0; i < n; i++) {
/* Check if the queen can be placed on
board[i][col] */
if (isSafe(board, i, col, n)) {
// board[i][col] = 1;
board[i] = 1 << (n-col-1);
solvenQUtil(board, col + 1, n, ans);
// board[i][col] = 0;
board[i] = 0; // BACKTRACK
}
}
bool isSafe(int** board, int row, int col, int n) {
int i, j;
/* Check this row on left side */
// if (board[row][i])
if(board[row] > (1<<(n-col-1)))
return false;
// /* Check upper diagonal on left side */
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
// if (board[i][j])
if(board[i] == 1<<(n-j-1))
return false;
// /* Check lower diagonal on left side */
for (i = row, j = col; j >= 0 && i < n; i++, j--)
// if (board[i][j])
if(board[i] == 1<<(n-j-1))
return false;
return true;
}
```
原本是使用 N*N 的大小儲存 `board`，在優化後使用 N*1 的大小來儲存。想法是將每個 row 的 `N` 格，用 2 進位的方式合併成一個十進位的數字。舉例來說
```c=1
// board[i][col] = 1;
board[i] = 1 << (n-col-1);
```
若原本是要在第 0 個 col 設為 1，那可以看成是值 $2^{n-1}$ 的意思。
而想要把 `board[i]` 的值轉換成對應到哪個 index 應該為 `Q`，就可以用到 `__builtin_ffs` 了
```c=1
for (int i = 0; i < n; i++) {
string tmp = dots;
tmp[__builtin_ffs(board[i])-1] = 'Q';
sol.push_back(tmp);
}
```
在記憶體使用上，仍然沒有大幅的增長，但是確實改善了執行時間。
:::warning
TODO: 透過 non-recursive 手段改寫 n-queen 程式碼
:::
Sign in with Wallet
Connect another wallet