# 2024q1 Homework1 (lab0)
contributed by < `marsh-fish` >
### Reviewed by `marvin0102`
q_ascend 和 q_descend 的實作中，我原本的作法是透過 `list_for_each_entry_safe` 逐一排查，當檢查到不符合 ascned 或 descend 的節點時，將期刪除後還須回過頭檢查之前的佇列，review 時，發現 marsh-fish 同學的作法更有效率。
> 需要解釋 marsh-fish 的方案為何更有效率，這樣才有同儕程式碼審查的效果。 :notes: jserv
### Reviewed by `mesohandsome`
可以貼出修改或新增的程式碼，或是貼出 commit 紀錄，以便日後修改或參考時較為便利。
`q_ascend` 和 `q_descend` 中，重複了很多一樣的程式碼，能提高程式碼的可重用程度。
我讓兩個函式同樣都是從尾端往前端走訪，以類似 `q_sort` 用一個 boolean 變數讓比較時可以更改方式，從而讓他們呼叫同一個函式，透過變數去控制行為。
```c
if (descend ? strcmp(entry1->value, entry2->value) > 0
: strcmp(entry1->value, entry2->value) < 0)
```
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-4590 CPU @ 3.30GHz
CPU family: 6
Model: 60
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
Stepping: 3
CPU max MHz: 3700.0000
CPU min MHz: 800.0000
BogoMIPS: 6584.43
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 128 KiB (4 instances)
L1i: 128 KiB (4 instances)
L2: 1 MiB (4 instances)
L3: 6 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-3
```
## 針對佇列操作的程式碼實作
:::danger
說好的進度呢？
:::
### q_new
使用在 list.h 定義的 `INIT_LIST_HEAD` 來實作
### q_free
由於需要釋放所有的節點，所以用 `list_for_each_entry_safe` 以便能更刪除節點，最後也別忘記將空的串列空間釋放出來。
### q_insert_head 和 q_insert_tail
與 [Ackerman666](https://github.com/Ackerman666/lab0-c) 及 [dockyu](https://github.com/dockyu/lab0-c) 討論的結果，使用 `strdup` 便會自動複製字串並配置記憶體空間，另可參照 [strcpy vs strdup](https://stackoverflow.com/questions/14020380/strcpy-vs-strdup)(內也有提到 `memcpy` 較 `strcpy` 有效率，所以在 `q_remove_head` 和 `q_remove_tail` 的實作有使用到)。
:::warning
注意超連結的標示方式，該提及摘要標題。
:::
### q_delete_mid
用快慢指標（Fast & Slow pointers）找到中間節點，這邊選擇讓兩個指標（烏龜和兔子）在初始就移動到第一個節點，這樣的好處是當迴圈結束時慢指標所指向的節點剛好會是中間節點。
```c
for (slow = head->next, fast = head->next;
fast != head && fast->next != head;
fast = fast->next->next, slow = slow->next)
;
```
### q_swap
這裡的概念和快慢指標類似，但與 `q_delete_mid` 不同的是初始並未移動到第一個節點，因為這裡先移動不會有額外的好處，所以我選擇先不移動。
:::warning
1. 討論「先移動不會有額外的好處」，提供量化分析。
2. 改進漢語表達。
:::
```c
for (this = head, temp = head;
temp->next != head && temp->next->next != head;
temp = temp->next->next) {
this = temp->next;
...
```
### q_delete_dup
這個函式我認為還有很大的改進空間，我使用 `list_for_each_entry_safe` 來作為方便刪除節點的迴圈，但我是選擇判斷當前節點與下一個節點，所以當到達最後一個節點時便會出錯，此時我的想法有兩個，一個是我從第二個節點開始搜尋，但我想保留 `list_for_each_entry_safe` 的使用，我不知道要如何在使用 `list_for_each_entry_safe` 的前提下從第二個節點開始搜尋，所以我選擇在最後節點時便跳出迴圈。
```c
list_for_each_entry_safe (entry, safe, head, list) {
if (&safe->list == head) {
break;
}
...
```
### q_reverse 和 q_reverseK
嘗試使用指標的指標來實作，每次將倒數第二個節點移動到最後一個
```c
struct list_head **sec_last = &head->prev->prev;
```
### q_sort
用分治法（Divide-and-conquer algorithm）來實作，以遞迴來實作較為容易，再次使用快慢指標將前半串列和後半串列分別遞迴，多建立一個 `merge_two_sorted` 函式以利於再次利用，由於 `strcmp` 會回傳正數或複數，便可以用以下的方式直接判斷要做遞增排序或遞減排序。
```c
if (strcmp(entry1->value, entry2->value) * (descend ? -1 : 1) > 0)
```
:::danger
如果不採取遞迴，你要怎麼開發排序程式？
>若不採取遞迴，可以先將原始串列分群(每個群將會是排列好的串列)，較簡單的分群方式即相鄰的節點分成一群，如果串列個數是奇數，最後一個節點自己一群即可，接著將相鄰的群依序合併，重複此流程便可得到排列好的串列，由與每次合併群的節點數目會是 2 的冪，所以不需要遞迴，用一個變數紀錄每次欲合併的群之大小就能知道每次迭代要合併的範圍，如此分析，可用兩個迴圈來實現。
:::
### q_ascend 和 q_descend
`q_descend` 每當下一個節點比當前節點小就將其刪除便會是~~答案~~移除所有右側比自身小的節點之串列了，`q_ascend` 反過來搜尋即是~~答案~~移除所有左側比自身小的節點之串列。
:::danger
答案？使用明確的詞彙。
>已修正
:::
### q_merge
使用在 queue.h 定義的 `queue_contex_t` 來實作，並再次利用前面定義的 `merge_two_sorted` 函式，由於我是將後面的串列(第二個之後)合併進第一個串列，所以在 `list_for_each_entry_safe` 迴圈的第一步跳過。
### 新增 q_shuffle 命令
新增 `do_shuffle` 至 `qtest.c` ，別忘了加入對應的 `ADD_COMMAND` 。
```c
ADD_COMMAND(shuffle, "Shuffle the queue with Fisher–Yates shuffle algorithm", "");
```
實作演算法為 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) ，從最後一個節點開始，用 `rand()` 隨機選擇前面的節點進行交換，新增一個 `swap` 函式以交換選擇到的節點， `swap` 的功能為交換兩個節點的 `value` 值實作演算法為 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) ，從最後一個節點開始，用 `rand()` 隨機選擇前面的節點進行交換，新增一個 `swap` 函式以交換選擇到的節點， `swap` 的功能為交換兩個節點的 `value` 值。
:::warning
思考如何針對鏈結串列特性，減少記憶體存取的次數。
>可以考慮刪除節點並加入插入節點的方式實作交換，例如:想要交換 a,b 兩個節點，其中 a 在 b 的前方，先將 a 移除並插入在 b 之後面，再將 b 移除並插入於 a 原先的位置，如此不會對串列存取之內容讀寫，能夠減少記憶體存取的次數。
:::
#### shuffle 分析
新增腳本程式至 `scripts` 目錄，新增 `make shuffle_test` 命令到 `Makefile` ，由於實際上只是執行一個 python 程式，所以多加 make 命令不是必要的步驟。
以下是分析的結果
```
Expectation: 41666
Observation: {'1234': 41760, '1243': 41852, '1324': 41221, '1342': 41732, '1423': 41779, '1432': 41722, '2134': 41618, '2143': 41706, '2314': 41726, '2341': 41683, '2413': 41465, '2431': 41686, '3124': 42107, '3142': 41863, '3214': 41455, '3241': 41635, '3412': 41428, '3421': 41840, '4123': 41781, '4132': 41280, '4213': 41571, '4231': 41671, '4312': 41829, '4321': 41590}
chi square sum: 21.11121777948447
```
### 比較 list_sort
sort
```
Performance counter stats for './qtest -f ./traces/trace-sort-1000000.cmd' (5 runs):
3504,6613 cache-misses # 58.30% of all cache refs ( +- 0.15% )
7,0088,4938 branches ( +- 0.01% )
6011,4640 cache-references ( +- 0.09% )
48,0760,5459 instructions # 0.61 insn per cycle ( +- 0.01% )
78,4441,2454 cycles ( +- 0.62% )
24 context-switches ( +- 38.61% )
2.17923 +- 0.00332 seconds time elapsed ( +- 0.15% )
```
list_sort from Linux
```
Performance counter stats for './qtest -f ./traces/trace-list_sort-1000000.cmd' (5 runs):
3297,2745 cache-misses # 64.60% of all cache refs ( +- 0.77% )
6,8959,4174 branches ( +- 0.01% )
5104,1682 cache-references ( +- 0.09% )
47,6232,0583 instructions # 0.64 insn per cycle ( +- 0.01% )
74,7756,7293 cycles ( +- 0.78% )
28 context-switches ( +- 58.00% )
2.0907 +- 0.0162 seconds time elapsed ( +- 0.77% )
```
### 引入 ttt
#### hlist 相關的程式碼抽出
閱讀[linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h)並將與 `hlist` 相關的程式碼抽出，同時閱讀[jserv/ttt](https://github.com/jserv/ttt)專案，將未使用到的函式移除，使其精簡。
Sign in with Wallet
Connect another wallet