2023q1 Homework1 (lab0)

contributed by < kart81604 >

開發環境

$ 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`

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 的條件要加進去，要如何判別配置失敗。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

中文和英文字元之間要有空白字元

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

好的，之後會注意。

`q_free`

這是一開始的想法，利用 indirect pointer cur 來指向 l->next 然後利用 list_del 將該點獨立出來，再將它釋放，接著 cur 再指向 l->next ，直到 l->next == l 最後再釋出 l 的空間。

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 和非連續記憶體。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

看完這張圖意識到，佇列形式應為此圖表示的， Head 型別為 list_head，而 Node 0, Node 1, Node 2 的型別為 element_t。

element_t 的結構由 char *value 與 struct list_head list 組成，因此圖上 Node 中的
int Data_A、int Data_B、int Data_C 替換成 char *value 會更完整代表此題的形式。

於是將程式碼更改為

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`

 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`

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`

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;
}

~~偶然查詢到 [ 資料 ](https://skylinelimit.blogspot.com/2018/02/c-2.html)，了解到使用 `strncpy` 來處理 buffer overflow 的問題。~~

查閱 C 語言標準和 man page 這類第一手材料！

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

`q_remove_tail`

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 。

思考進一步縮減程式碼的方式，善用前置處理器。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

`q_delete_mid`

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 。

 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`

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 會失敗，是因為疏忽了有出現重複的全部都要刪掉，以上程式碼會造成只有出現第二次的元素會被刪除，而導致結果錯誤。
而更改的結果如下。

善用 diff，只列出變更的部分程式碼。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

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`


















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`

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`

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`

不用張貼完整程式碼，開發紀錄著重於你的想法、中間遭遇到的問題、分析和試驗等等。程式碼僅為輔助性質。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

`merge_two_list`




































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 的實作。

~~因為 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`

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`

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`

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 。

文字訊息不要用螢幕截圖展現，尊重視障者閱讀的權益。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

好的！

而加入之後就會正確執行了。

`q_merge`

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 的方法。

考慮測試案例 17 中， q_insert_tail 與 q_insert_head 都不能在常數時間內完成。

測試案例和測試資料不同，前者是若干筆測試資料的集合。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

作業要求有提到， lab0-c 並沒有具備 percentile 的處理，參考 oreparaz/dudect 後，新增 percentile 功能，trace-17 已能通過，目前分數為100分。
由於原始碼有使用結構 dudect_ctx_t ， lab0-c 則沒有，因此原始碼有些 input 裡有
ttest_ctx_t *ctx ，在 lab0-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 的原始碼中的一個 function 。

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 中參考後的程式碼。

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 中函式放入 queue.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 是比較大小所需的函式，這邊改用以下的方式代替，因此也不需要此參數。

- cmp(priv, a, b)
+ strcmp(list_entry(a, element_t, list)->value,
+        list_entry(b, element_t, list)->value

移除不需要的 callback


if (unlikely(!++count))
    cmp(priv, b, b);

在 qtest.c 加入新命令

static void console_init()
{
    ...
    ADD_COMMAND(list_sort, "Sort queue in ascending order by list_sort", "");
    ...
}

藉由 console.h 中

#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)

可以知道會呼叫 do_list_sort 這個函式，因此我們要在 qtest.c 新增 do_list_sort 函式

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 之前加入其實就可以)

// In qtest.c
#include "queue.h"
void list_sort(struct list_head *head);

測試

將 qtest.c 裡的 do_sort 稍作更改，來確認是否能正確執行。

- 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 裡面。

//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", "");
    ...
}

//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 演算法， shuffle 的原理如下圖所示。
設一開始資料如下，長度為 9 的陣列。

隨機選擇 1 ~ 9 中隨機一個數 roll，以及最後一項 cur 。
此例 cur = 4 (陣列第一個位置為 1 )。

roll 與 cur 交換位子。

之後在從 1 ~ 8 中選擇一個數 roll ，以及還未換過得 cur ，以此類推，直到 cur 指向陣列的開頭，這樣下來就會得到與之前不同排列的陣列。(如果某一輪 roll 恰好等於 cur 則不交換，進到下一輪)

以下為實做的程式碼。

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 。

2023q1 Homework1 (lab0)

開發環境

完善 queue.c

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

q_sort

merge_two_list

merge_sort

q_sort

q_descend

q_merge

更改 dudect

將 lib/list_sort 引入至 lab0-c 專案

測試

與自行實做的 sort 進行比較

新增 shuffle 命令

Read more

一對一問題回答

2023q1 Homework2 (quiz2)

2023q1 Homework1 (quiz1)

`q_new`

`q_free`

`q_insert_head`

`q_insert_tail`

`q_remove_head`

`q_remove_tail`

`q_delete_mid`

`q_delete_dup`

`q_swap`

`q_reverse`

`q_reverseK`

`q_sort`

`merge_two_list`

`merge_sort`

`q_sort`

`q_descend`

`q_merge`