# 2023q1 Homework1 (lab0)
contributed by < `kart81604` >
## 開發環境
```shell
$ gcc -version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.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): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 9
CPU max MHz: 3800.0000
CPU min MHz: 800.0000
BogoMIPS: 5599.85
```
## 完善 queue.c
### `q_new`
```c
struct list_head *q_new()
{
struct list_head *li =
(struct list_head *) malloc(sizeof(struct list_head));
if (!li)
return NULL;
INIT_LIST_HEAD(li);
return li;
}
```
回傳 `NULL` 的條件要加進去，要如何判別配置失敗。
:::warning
:warning: 中文和英文字元之間要有空白字元
:notes: jserv
> 好的，之後會注意。
:::
### `q_free`
這是一開始的想法，利用 indirect pointer `cur` 來指向 `l->next` 然後利用 `list_del` 將該點獨立出來，再將它釋放，接著 `cur` 再指向 `l->next` ，直到 `l->next == l` 最後再釋出 `l` 的空間。
```c
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head **cur = &l->next;
while (*cur != l){
list_del(*cur);
free(*cur);
cur = &l->next;
}
free(l);
}
```
但這樣的話，我每次釋出的都是 `list_head` 大小的空間，中間不包含任何資訊，對於一種儲存結構來說太弔詭了，於是我再次拜讀[ 你所不知道的 C 語言: linked list 和非連續記憶體 ](https://hackmd.io/@sysprog/c-linked-list)。
看完這張圖意識到，佇列形式應為此圖表示的， Head 型別為 `list_head`，而 Node 0, Node 1, Node 2 的型別為 `element_t`。
:::info
`element_t` 的結構由 `char *value` 與 `struct list_head list` 組成，因此圖上 Node 中的
`int Data_A`、`int Data_B`、`int Data_C` 替換成 `char *value` 會更完整代表此題的形式。
:::
於是將程式碼更改為
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *entry, *safe;
list_for_each_entry_safe(entry, safe, l, list){
q_release_element(entry);
}
free(l);
}
```
使用 `list_for_each_safe` 走訪每個 `element_t` 並進行 `q_release_element` 做完之後只會剩下最開頭的 `list_head` ，然後 `free(l)` ，就完成了。
### `q_insert_head`
```diff
bool q_insert_head(struct list_head *head, char *s)
{
+ if (!head)
+ return false;
element_t *new = (element_t *) malloc(sizeof(element_t));
+ if (!new)
+ return false;
char *new_s = (char *) malloc((strlen(s) + 1) * sizeof(char));
- if (!new || !new_s || !head)
+ if (!new_s) {
+ free(new);
return false;
+ }
```
值得注意的是要將 input 中的 `*s` 複製到新配置的空間。
考慮到執行 `make valgrind` 會發生插入失敗但有記憶體空間被分配而切沒有被釋放出去，發現原因是因為 `report.c` 中有 `allocate_cnt` 及 `free_cnt` 參數，會隨著 `free` 以及 `malloc` 指令來增減， insert 分配順序為先分配 `new` 再來是 `new_s` ，要是分配 `new_s` 失敗時，但沒有釋出 `new` 已配置的空間，則會造成失敗。
### `q_insert_tail`
```diff
bool q_insert_tail(struct list_head *head, char *s)
{
+ if (!head)
+ return false;
element_t *new = (element_t *) malloc(sizeof(element_t));
+ if (!new)
+ return false;
char *new_s = (char *) malloc((strlen(s) + 1) * sizeof(char));
- if (!new || !new_s)
+ if (!new_s) {
+ free(new);
return false;
+ }
```
基本上就是照著 `q_insert_head` 的方法作，單純的把 `q_insert_head` 中的第 9 行改成 `list_add_tail(&new->list, head)` 。
### `q_remove_head`
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *ele = list_entry(head->next, element_t, list);
list_del_init(&ele->list);
if (sp != NULL) {
strncpy(sp, ele->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return ele;
}
```
<s>
偶然查詢到 [ 資料 ](https://skylinelimit.blogspot.com/2018/02/c-2.html)，了解到使用 `strncpy` 來處理 buffer overflow 的問題。
</s>
:::warning
查閱 C 語言標準和 man page 這類第一手材料！
:notes: jserv
:::
### `q_remove_tail`
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *ele = list_entry(head->prev, element_t, list);
list_del_init(&ele->list);
if (sp != NULL) {
strncpy(sp, ele->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return ele;
}
```
也是照著 `q_remove_head` 的方法作，只是把 `q_remove_head` 中的第 5 行中的第一個參數改成
`head->prev` 。
:::warning
思考進一步縮減程式碼的方式，善用前置處理器。
:notes: jserv
:::
### `q_delete_mid`
```c
bool q_delete_mid(struct list_head *head)
{
if (!head)
return false;
struct list_head **forward, **back;
forward = &head->next;
back = &head->prev;
while (*forward != *back && *forward != (*back)->next) {
forward = &(*forward)->next;
back = &(*back)->prev;
}
element_t *cur = list_entry(*forward, element_t, list);
list_del_init(*forward);
q_release_element(cur);
return true;
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
}
```
2 月 16 號晚上上課時，多虧老師的指點，利用 doubly-linked list 的特性，設置兩個 indirect pointer 為 `forward` 與 `back` ，如命名，一個是往前走，另一個則是往後走，直到兩個指到同一點，或是 `back` 在 `forward` 後面，之後對 `forward` 指到的位置進行 `list_entry` ，找出包含 `forward` (`forward` 的型別為 `list_head` )的 `element_t` 的位置，接著再
進行 `list_del_int` 以及 `q_release_element` 。
```diff
bool q_delete_mid(struct list_head *head
{
if (!head)
return false;
- struct list_head **forward, **back;
- forward = &head->next;
- back = &head->prev;
- while (*forward != *back && *forward != (*back)->next) {
- forward = &(*forward)->next;
- back = &(*back)->prev;
+ struct list_head *forward, *back;
+ forward = head->next;
+ back = head->prev;
+ while (forward != back && forward != back->next) {
+ forward = forward->next;
+ back = back->prev;
}
- element_t *cur = list_entry(*forward, element_t, list);
- list_del_init(*forward);
+ element_t *cur = list_entry(forward, element_t, list);
+ list_del_init(forward);
q_release_element(cur);
return true;
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
}
```
之後重新審視程式碼，發現所有取用 indirect pointer 都有透過 `*` 來操作，就代表根本沒有必要使用 indirect pointer 來操作，這樣反而還使程式碼變更複雜，因此改成沒有使用 indirect pointer 的版本。
### `q_delete_dup`
```c
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
struct list_head **cur, **test;
cur = &head->next;
while (cur != &head) {
test = &(*cur)->next;
while (test != &head &&
!strcmp(list_entry(*cur, element_t, list)->value,
list_entry(*test, element_t, list)->value)) {
list_del_init(*test);
q_release_element(list_entry(*test, element_t, list));
test = &(*cur)->next;
}
cur = test;
}
return true;
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
}
```
以上為之前的想法，跑 test 會失敗，是因為疏忽了有出現重複的全部都要刪掉，以上程式碼會造成只有出現第二次的元素會被刪除，而導致結果錯誤。
而更改的結果如下。
:::warning
善用 `diff`，只列出變更的部分程式碼。
:notes: jserv
:::
```c
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
struct list_head *cur, *del;
int count = 0;
cur = head->next;
while (cur != head) {
struct list_head *test = cur->next;
while (test != head &&
strcmp(list_entry(cur, element_t, list)->value,
list_entry(test, element_t, list)->value) == 0) {
count++;
list_del_init(test);
q_release_element(list_entry(test, element_t, list));
test = cur->next;
}
cur = cur->next;
if (count) {
del = cur->prev;
list_del_init(del);
q_release_element(list_entry(del, element_t, list));
count = 0;
}
}
return true;
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
}
```
除了跟 `q_delete_mid` 一樣，不再使用 indirect pointer ，其餘與以上方法相似，只是多使用了一個參數 `count` 來判斷該元素是否有出現重複，如果有的話，就在把那個元素刪除。
### `q_swap`
```c=
void q_swap(struct list_head *head)
{
if (!head)
return;
struct list_head *cur;
cur = head->next;
while (cur != head && cur->next != head) {
struct list_head *tmp = cur->next;
list_del(cur);
cur->next = tmp->next;
cur->prev = tmp;
tmp->next->prev = cur;
tmp->next = cur;
cur = cur->next;
}
return;
// https://leetcode.com/problems/swap-nodes-in-pairs/
}
```
先紀錄`tmp` 為 `cur` 的下一個，再把 `cur` 孤立出來。
而第 10 ~ 13 行，把 `cur` 插進 `tmp` 的後面。
### `q_reverse`
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head) != 0)
return;
struct list_head *cur = head->next;
while (cur != head) {
cur = cur->next;
list_move(cur->prev, head);
}
return;
}
```
把 queue 中的每一項都進行 `list_move` 移到 queue 的第一項就完成了。
### `q_reverseK`
```c
void q_reverseK(struct list_head *head, int k)
{
if (!head || list_empty(head) != 0 || list_is_singular(head) != 0 || k < 2)
return;
int len = q_size(head);
struct list_head *cur_head = head;
struct list_head *cur = cur_head->next;
while (len - k > -1) {
for (int i = 0; i < k; i++) {
cur = cur->next;
list_move(cur->prev, cur_head);
}
cur_head = cur;
cur = cur_head->next;
len = len - k;
}
return;
// https://leetcode.com/problems/reverse-nodes-in-k-group/
}
```
與上題類似的方法，每一段進行 k 次的 `list_move` ，再用個 `cur_head` 紀錄等等誰要當新的 head 。
### `q_sort`
:::danger
不用張貼完整程式碼，開發紀錄著重於你的想法、中間遭遇到的問題、分析和試驗等等。程式碼僅為輔助性質。
:notes: jserv
:::
#### `merge_two_list`
```c=
struct list_head *merge_two_list(struct list_head *L1, struct list_head *L2)
{
struct list_head *head = NULL, **node, *tmp;
node = strcmp(list_entry(L1, element_t, list)->value,
list_entry(L2, element_t, list)->value) < 0
? &L1
: &L2;
head = *node;
*node = (*node)->next;
list_del_init(head);
while ((*node) != head && (*node)->next != head) {
node = strcmp(list_entry(L1, element_t, list)->value,
list_entry(L2, element_t, list)->value) < 0
? &L1
: &L2;
*node = (*node)->next;
tmp = (*node)->prev;
list_del(tmp);
list_add_tail(tmp, head);
}
if (L1 == head || L1->next == head) {
tmp = L2->prev;
L2->prev->next = head;
L2->prev = head->prev;
head->prev->next = L2;
head->prev = tmp;
} else {
tmp = L1->prev;
L1->prev->next = head;
L1->prev = head->prev;
head->prev->next = L1;
head->prev = tmp;
}
return head;
}
```
設計這個 `merge_two_list` 是希望我的 input 是保留原本的 doubly-linked list 結構， output 也是 doubly-linked list 結構。
其他 function 是把一開始的 `head` 僅視為 queue 的開頭，不包含資料的，而 `merge_two_list` 的兩個 input 都是某個 `element_t` 的 `list` 也就是對 input 執行 `list_entry` 是找的到其 `element_t` 的位子的， output 也是同理，輸出的 queue 中的每個 head ，都是找得到其 `element_t` 的位子，主要執行方式還是參考[ 你所不知道的C語言-Merger Sort 的實作 ](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)。
- ~~因為 input 的結構，所以對 input 作 `q_size` 時，要多加上 1 ，才會是 queue 正確的長度~~。
- 而在進入 while 迴圈前，為了盡可能減少使用記憶體資源，將兩個 queue 的開頭比較小的當 output 的 head (這邊指的 head 仍是有乘載資料的)。
- 進入 while 迴圈，使用與上文 Merge Sort 的實作相近的方法去進行，~~而結束判定方式是使用哪個 queue 的長度先歸零。~~ 跳出迴圈的條件為判定是否 `node` 所指或是他的下一個為 `head` 。
- 而跳出 while 迴圈，代表有一個 intput queue 已經都被加入到 sorted queue 裡了，而在將另外一個 intput queue 直接接到 sorted queue 的後面，這邊沒有採用 `list_h` 中的 `splice` 功能是因為 input 的格式，所以只能自己寫上去。
更正的目的是為了保證測試案例 14 能順利通過。
#### `merge_sort`
```c
struct list_head *merge_sort(struct list_head *start)
{
if (list_empty(start) != 0)
return start;
struct list_head *forward = start, *back = start->prev, *tail = start->prev;
do {
forward = forward->next;
back = back->prev;
} while (forward != back && forward->prev != back);
if (forward == back)
forward = forward->next;
start->prev = back;
back->next = start;
forward->prev = tail;
tail->next = forward;
return merge_two_list(merge_sort(start), merge_sort(forward));
}
```
input 與 output 的格式與 `merger_two_list` 一樣，指得都是某個 queue 的開頭，但這個開頭也是某個 `element_t` 的 `list` 。
值得一提的是這邊採用的是 do-while 的迴圈，處理 input 為長度為 2 的 queue 就不會出錯。
#### `q_sort`
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) != 0)
return;
struct list_head *start = head->next;
list_del_init(head);
struct list_head *init = merge_sort(start);
head->next = init;
head->prev = init->prev;
init->prev->next = head;
init->prev = head;
return;
}
```
了解 `merge_two_sort` 與 `merger_sort` ，就知道一開始要先把 input 的 head 孤立出來，等做完排序後，再把他接上。
### `q_descend`
```c
int q_descend(struct list_head *head)
{
if (!head || list_empty(head) != 0)
return 0;
struct list_head *cur = head->next->next, *del;
while (cur != head) {
while (cur->prev != head &&
strcmp(list_entry(cur, element_t, list)->value,
list_entry(cur->prev, element_t, list)->value) >= 0) {
del = cur->prev;
list_del_init(del);
q_release_element(list_entry(del, element_t, list));
}
cur = cur->next;
}
// https://leetcode.com/problems/remove-nodes-from-linked-list/
return q_size(head);
}
```
比較在意的問題是，題目描述是用 remove ，但如果沒有加入第 12 行的 `q_relaese_element` 會造成`ERROR: Freed queue, but 4 blocks are still allocated` 。
:::danger
文字訊息不要用螢幕截圖展現，尊重視障者閱讀的權益。
:notes: jserv
>好的！
:::
而加入之後就會正確執行了。
### `q_merge`
```c
int q_merge(struct list_head *head)
{
if (!head || list_empty(head) != 0)
return 0;
struct list_head *ret_head, *cur_head = head->next->next, *sorted;
ret_head = list_entry(head->next, queue_contex_t, chain)->q;
sorted = ret_head->next;
list_del_init(ret_head);
while (cur_head != head) {
struct list_head *first =
list_entry(cur_head, queue_contex_t, chain)->q->next;
list_del_init(first->prev);
sorted = merge_two_list(sorted, first);
cur_head = cur_head->next;
}
ret_head->next = sorted;
ret_head->prev = sorted->prev;
sorted->prev->next = ret_head;
sorted->prev = ret_head;
// https://leetcode.com/problems/merge-k-sorted-lists/
return q_size(ret_head);
}
```
重用了 `q_sort` 中使用的 `merge_two_list` ，將 `chain` 上每個 queue 的 `head`斷開，再與第一個 queue 進行 `merge_two_list` ，之後再接上 `chain` 上的第一個 `head` 。
## 更改 dudect
主要參考 [willwillhi](https://hackmd.io/@willwillhi/lab0-2023#dudect) 的方法。
考慮測試案例 17 中， `q_insert_tail` 與 `q_insert_head` 都不能在常數時間內完成。
:::warning
測試案例和測試資料不同，前者是若干筆測試資料的集合。
:notes: jserv
:::
作業要求有提到， `lab0-c` 並沒有具備 percentile 的處理，參考[ oreparaz/dudect ](https://github.com/oreparaz/dudect)後，新增 percentile 功能，trace-17 已能通過，目前分數為100分。
由於原始碼有使用結構 `dudect_ctx_t` ， lab0-c 則沒有，因此原始碼有些 input 裡有
`ttest_ctx_t *ctx` ，在 lab0-c 會用到結構裡的那些參數，就要自己加進去。
```c
typedef struct {
int64_t *ticks;
int64_t *exec_times;
uint8_t *input_data;
uint8_t *classes;
dudect_config_t *config;
ttest_ctx_t *ttest_ctxs[DUDECT_TESTS];
int64_t *percentiles;
} dudect_ctx_t;
```
以下為 [ oreparaz/dudect ](https://github.com/oreparaz/dudect)的原始碼中的一個 function 。
```c
static void prepare_percentiles(dudect_ctx_t *ctx) {
for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
ctx->percentiles[i] = percentile(
ctx->exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)),
ctx->config->number_measurements);
}
}
```
以下為 lab0-c 中的 `fixture.c` 中參考後的程式碼。
```c
static void prepare_percentiles(int64_t *percentiles, int64_t *exec_times)
{
for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
percentiles[i] = percentile(
exec_times,
1 - (pow(0.5, 10 * (double) (i + 1) / DUDECT_NUMBER_PERCENTILES)),
N_MEASURES);
}
}
```
## 將 lib/list_sort 引入至 lab0-c 專案
將 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 中函式放入 `queue.c`。
```c
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
struct list_head *a, struct list_head *b);
static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
struct list_head *a, struct list_head *b);
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
```
函式中的參數， `priv` 表示是私密資料，這邊用不到，所以將其移除， `cmp` 是比較大小所需的函式，這邊改用以下的方式代替，因此也不需要此參數。
```diff
- cmp(priv, a, b)
+ strcmp(list_entry(a, element_t, list)->value,
+ list_entry(b, element_t, list)->value
```
移除不需要的 callback
```c=
if (unlikely(!++count))
cmp(priv, b, b);
```
在 `qtest.c` 加入新命令
```c
static void console_init()
{
...
ADD_COMMAND(list_sort, "Sort queue in ascending order by list_sort", "");
...
}
```
藉由 `console.h` 中
```c
#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)
```
可以知道會呼叫 `do_list_sort` 這個函式，因此我們要在 `qtest.c` 新增 `do_list_sort` 函式
```c
bool do_list_sort(int argc, char *argv[])
```
這個函式的內容與原本的 `do_sort` 幾乎一模一樣，差別只有差在 `do_sort` 執行 `q_sort` ，而 `do_list_sort` 執行 `list_sort` 。
由上可知，我們在 `qtest.c` 會執行 `list_sort` 指令，因此要先宣告，原本是在 `queue.h` 宣告，但在 git commit 時會發出錯誤，系統表示不允許更改 `list.h` 以及 `queue.h` ，因此雖然在 `queue.c` 引入 list_sort ，但 `qtest.c` 只會 `#include <queue.h>` ，沒有先行宣告的話， compile 階段就不會過，解決方法為在 `#include <queue.h>` 下一行手動加入宣告。(在執行 list_sort 之前加入其實就可以)
```c
// In qtest.c
#include "queue.h"
void list_sort(struct list_head *head);
```
### 測試
將 `qtest.c` 裡的 `do_sort` 稍作更改，來確認是否能正確執行。
```diff
- q_sort(current->q);
+ list_sort(current->q);
```
儲存後執行以下指令。
```
make test
```
所得分數為 100 ， 代表此方法為正確的排序。
### 與自行實做的 sort 進行比較
兩者都使用以下指令來測試性能
```
new
ih RAND 300000
list_sort/ sort
quit
```
在使用 perf 來觀察差異。
但這樣兩者對不同的 queue 進行排序，考慮到公平性，對同一個queue排列是最好的，因此在 `qtest.c` 中新加入兩條命令，分別是 `write_in` 及 `write_out` ，前者是將 `data.txt` 中的資料加入當前的 queue 中，後者則是將目前的 queue 的資料寫進 `data.txt` 裡面。
```c
//in qtest.c
static bool do_write_in(int argc, char *argv[])
{
if (argc != 2) {
report(1, "%s needs 2 arguments", argv[0]);
return false;
}
FILE *fptr;
bool res;
int num;
get_int(argv[1], &num);
int unused __attribute__((unused));
fptr = fopen("data.txt","r");
char buff[10];
for (int i = 0; i < num; i++) {
unused = fscanf(fptr, "%s", buff);
res = q_insert_tail(current->q, buff);
if (!res) {
report(1, "%s needs 2 arguments", argv[0]);
return res;
}
current->size++;
}
fclose(fptr);
q_show(0);
return true;
};
...
static void console_init()
{
...
ADD_COMMAND(write_in, "Read data from data.txt", "");
...
}
```
```c
//in qtest.c
static bool do_write_out()
{
write_out(current->q);
return true;
};
...
static void console_init()
{
...
ADD_COMMAND(write_out, "Let queue be writed in data.txt","");
...
}
//in queue.c
void write_out(struct list_head *head)
{
if (!head)
return;
FILE *fptr;
fptr = fopen("data.txt","w");
element_t *entry;
list_for_each_entry(entry, head, list) {
fprintf(fptr,"%s ",entry->value);
}
fclose(fptr);
return;
}
```
先執行以下指令，將隨機 300000 筆資料寫進 `data.txt` 裡。
```
make
./qtest
new
ih RAND 300000
write_out
quit
```
這時候 `data.txt` 已被寫進了密密麻麻的資料，就可以來進行比較了。
執行以下指令
```
sudo perf stat ./qtest
cmd> new
l = []
cmd> write_in 300000
l = [hdmfo ttvctx iqyvaq ioufrfgcl vazjmmx lgfhqanj uzhpgtda jxddkzos vhfzvt ibmheb kmqndzh kzueygb xvdongpqf zkksctovy ggvlhhcw ezajagx bsygnhw okhanmkn fiywwnfuw hjrvzp zqhygvci amqoctgi pydlfqzuu sattycu stbelywk qgpguvmo pgxoa nyouik gatugwx jesxmnj ... ]
cmd> sort / list_sort (二選一)
l = [aaaltwj aaanu aaanwr aaaoyp aaapzi aaayxlwe aabec aabmqqv aabmsg aabnkul aabwcf aabxgrdco aabzibig aacpkh aacra aacrcwz aadfbdjyl aadipypol aadxhk aaebts aaezrdv aafbzhb aafgi aafgiwb aafgkvm aaflym aafnikkc aafpssefw aafpubi aafuxr ... ]
cmd> quit
Freeing queue
```
以下為不同 sort 的效能分析。
```
//q_sort
Performance counter stats for './qtest':
617.17 msec task-clock # 0.030 CPUs utilized
173 context-switches # 280.312 /sec
23 cpu-migrations # 37.267 /sec
10,630 page-faults # 17.224 K/sec
1,903,190,923 cycles # 3.084 GHz
914,314,784 instructions # 0.48 insn per cycle
177,202,493 branches # 287.121 M/sec
3,519,618 branch-misses # 1.99% of all branches
20.585745007 seconds time elapsed
0.573715000 seconds user
0.044757000 seconds sys
```
```
//list_sort
Performance counter stats for './qtest':
507.80 msec task-clock # 0.033 CPUs utilized
60 context-switches # 118.156 /sec
28 cpu-migrations # 55.140 /sec
10,629 page-faults # 20.931 K/sec
1,507,473,192 cycles # 2.969 GHz
821,585,687 instructions # 0.55 insn per cycle
173,594,834 branches # 341.855 M/sec
5,707,655 branch-misses # 3.29% of all branches
15.617930042 seconds time elapsed
0.481652000 seconds user
0.028096000 seconds sys
```
## 新增 shuffle 命令
透過閱讀 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法， shuffle 的原理如下圖所示。
設一開始資料如下，長度為 9 的陣列。
```graphviz
digraph array
{
edge[]
node[shape=plaintext]
" " [color=white];
node [shape=record, fontcolor=black, width=2.5];
values [ shape = record, label = "k|a|r|t|8|1|6|0|4"];
}
```
隨機選擇 1 ~ 9 中隨機一個數 `roll`，以及最後一項 `cur` 。
此例 `cur = 4` (陣列第一個位置為 1 )。
```graphviz
digraph {
node[shape=plaintext]
" " -> " " [color=white];
node [shape=record, fontcolor=black, width=2.5];
pointers [label="|||<roll>roll|||||<cur>cur", color=white];
values [label="k|a|r|<roll>t|8|1|6|0|<cur>4"];
{ rank=same; " "; pointers }
{ rank=same; " "; values }
pointers:roll->values:roll;
pointers:cur->values:cur;
}
```
`roll` 與 `cur` 交換位子。
```graphviz
digraph array
{
edge[]
node[shape=plaintext]
" " [color=white];
node [shape=record, fontcolor=black, width=2.5];
values [ shape = record, label = "k|a|r|4|8|1|6|0|t"];
}
```
之後在從 1 ~ 8 中選擇一個數 `roll` ，以及還未換過得 `cur` ，以此類推，直到 `cur` 指向陣列的開頭，這樣下來就會得到與之前不同排列的陣列。(如果某一輪 `roll` 恰好等於 `cur` 則不交換，進到下一輪)
```graphviz
digraph {
node[shape=plaintext]
" " -> " " [color=white];
node [shape=record, fontcolor=black, width=2.5];
pointers [label="||<roll>roll|||||<cur>cur|", color=white];
values [label="k|a|<roll>r|4|8|1|6|<cur>0|t"];
{ rank=same; " "; pointers }
{ rank=same; " "; values }
pointers:roll->values:roll;
pointers:cur->values:cur;
}
```
以下為實做的程式碼。
```c
void shuffle(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
int remaining = q_size(head);
struct list_head *current = head->prev;
srand(time(NULL));
while (remaining > 1) {
struct list_head *exchange = head, *tmp;
int roll = rand() % remaining + 1;
while (roll > 1) {
exchange = exchange->next;
roll--;
}
tmp = exchange->next;
list_del(tmp);
list_add(tmp, current);
tmp = current->prev;
list_del(current);
list_add(current, exchange);
current = tmp;
remaining--;
}
}
```
之後再加進命令裡，作法與之前加入新命令的方法一致，就不多作贅述。
以下是測試是否會得到與之前不同的 queue 。
```
cmd> new
l = []
cmd> ih RAND 10
l = [ovflb wopuah ltrioqjob beapz uejeblg jiekomlze kxtfgwpjb ctcoptbl wvlamebmx sictvjfx]
cmd> shuffle
l = [wvlamebmx sictvjfx beapz ovflb jiekomlze ctcoptbl ltrioqjob wopuah kxtfgwpjb uejeblg]
```
測試可得與之前不同排列的 queue 。
Sign in with Wallet
Connect another wallet