# 2023q1 Homework1 (lab0) contributed by < `csm1735` > ## 開發環境 ```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): 4 On-line CPU(s) list: 0-3 Vendor ID: GenuineIntel Model name: Intel(R) Core(TM) i5-7300HQ CPU @ 2.50GHz CPU family: 6 Model: 158 Thread(s) per core: 1 Core(s) per socket: 4 Socket(s): 1 Stepping: 9 CPU max MHz: 3500.0000 CPU min MHz: 800.0000 BogoMIPS: 4999.90 ``` ## 改進 `queue.c` ### q_new ```c struct list_head *q_new() { struct list_head *head = malloc(sizeof(*head)); if (!head) { free(head); return NULL; } INIT_LIST_HEAD(head); return head; } ``` ### q_free ```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_entry_safe` 來實作。 ### q_insert_head / tail ```c element_t *new_element(char *s) { element_t *element = malloc(sizeof(*element)); if (!element) { free(element); return NULL; } element->value = strdup(s); if (!element->value) { free(element); return NULL; } return element; } ``` 實作後發現 `q_insert_head` 跟 `q_insert_tail` 在程式碼上有大量重複的狀況，考量到精簡度及維護性，因此選擇將重複部分獨立成 `new_element` 來使用。 ```c bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *element = new_element(s); if (!element) return false; list_add(&element->list, head); return true; } ``` ```c bool q_insert_tail(struct list_head *head, char *s) { if (!head) return false; element_t *element = new_element(s); if (!element) return false; list_add_tail(&element->list, head); return true; } ``` `q_insert_head` 跟 `q_insert_tail` 主要差異在於一個使用了 `list_add` 而另一個使用了 `list_add_tail` 。 ### 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 *tmp = list_first_entry(head, element_t, list); if (sp) { strncpy(sp, tmp->value, bufsize - 1); sp[bufsize - 1] = '\0'; } list_del(&tmp->list); return tmp; } ``` 一開始沒有看懂說明，以為要對 `sp` 做 `malloc` ，所以產生了問題，後來發現應該直接去檢查 `sp` 是否為 `NULL` ， 再來做 `strncpy` 。 ### 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 *tmp = list_last_entry(head, element_t, list); if (sp) { strncpy(sp, tmp->value, bufsize - 1); sp[bufsize - 1] = '\0'; } list_del(&tmp->list); return tmp; } ``` 跟 `q_remove_head` 主要差異在於其使用了 `list_first_entry` 而這邊使用了 `list_last_entry` 。 ### q_size ```c int q_size(struct list_head *head) { if (!head || list_empty(head)) return 0; size_t len = 0; struct list_head *cur; list_for_each (cur, head) { ++len; } return len; } ``` 目前沒有想到其他更有效率的做法，只能透過走訪所有的節點來計算 `size` 。 ### q_delete_mid ```c bool q_delete_mid(struct list_head *head) { if (!head || list_empty(head)) return false; size_t len = q_size(head), count = -1; element_t *entry, *safe; list_for_each_entry_safe (entry, safe, head, list) { ++count; if (count == len / 2) { list_del(&entry->list); q_release_element(entry); break; } } return true; } ``` 找出中間的節點後，將其移除並釋放記憶體。 ### q_delete_dup ```c bool q_delete_dup(struct list_head *head) { if (!head) return false; bool flag = 0; element_t *entry, *safe; list_for_each_entry_safe (entry, safe, head, list) { if (&safe->list == head) { if (flag == 1) { list_del(&entry->list); q_release_element(entry); } break; } if (strcmp(entry->value, safe->value) == 0) { list_del(&entry->list); q_release_element(entry); flag = 1; } else if (flag == 1) { list_del(&entry->list); q_release_element(entry); flag = 0; } } return true; } ``` 這邊函式需要佇列在排序完的狀況下執行，去刪除具有相同字串的節點，假設這邊有 $N$ 個相同字串的節點，那麼前 $N-1$ 個可以透過 `strcmp` 的判斷來做刪除，第 $N$ 個則是透過 `flag` 的檢查來做刪除 。 :::warning 撰寫更精簡的程式碼。 :notes: jserv ::: ```c list_for_each_entry_safe (entry, safe, head, list) { if (&safe->list != head && strcmp(entry->value, safe->value) == 0) { list_del(&entry->list); q_release_element(entry); flag = 1; } else if (flag == 1) { list_del(&entry->list); q_release_element(entry); flag = 0; } } ``` 將 `list_for_each_entry_safe` 內調整為更精簡的寫法 ### q_swap ```c void q_swap(struct list_head *head) { if (!head || list_empty(head)) return; q_reverseK(head, 2); return; } ``` 此函式 `swap` 的實質意義就等同於 `q_reverseK` 在參數 k 值為 2 的時候。 :::warning 是否可據此進一步精簡程式碼？ :notes: jserv ::: ### q_reverse ```c void q_reverse(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *node, *safe; list_for_each_safe (node, safe, head) { list_move(node, head); } return; } ``` 將所有的節點依序搬到頭後就等同於完成 `reverse` ， 要注意這邊得使用 `list_for_each_safe` 。 ### q_reverseK ```c void q_reverseK(struct list_head *head, int k) { if (!head || list_empty(head)) return; struct list_head *node, *safe, *head_from = head, tmp; INIT_LIST_HEAD(&tmp); size_t count = 0; list_for_each_safe (node, safe, head) { ++count; if (count == k) { list_cut_position(&tmp, head_from, node); q_reverse(&tmp); list_splice_init(&tmp, head_from); head_from = safe->prev; count = 0; } } return; } ``` 這邊參考了 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_reverseK-%E5%AF%A6%E4%BD%9C) 的作法，每 k 個節點就切出來做 `reverse` 的動作，然後再將其連接回去。 ### q_sort :::danger 不用張貼完整程式碼，你應該闡述自己的想法、考量因素，還有分析已有方案的優缺點，並記錄過程中遇到的問題。 :notes: jserv ::: ```c struct list_head *mergeTwoList(struct list_head *l1, struct list_head *l2) { if (!l2) return l1; if (!l1) return l2; element_t *n1 = list_entry(l1, element_t, list); element_t *n2 = list_entry(l2, element_t, list); if (strcmp(n1->value, n2->value) < 0) { l1->next = mergeTwoList(l1->next, l2); return l1; } else { l2->next = mergeTwoList(l1, l2->next); return l2; } } ``` `mergeTwoList` 原先的遞迴寫法，雖然程式碼較為精簡，但在 `make test` 時效能上無法通過，因此修正為以下的迴圈版本 ```c struct list_head *mergeTwoList(struct list_head *l1, struct list_head *l2) { struct list_head *head, *tmp; element_t *n1 = list_entry(l1, element_t, list); element_t *n2 = list_entry(l2, element_t, list); if (strcmp(n1->value, n2->value) < 0) { tmp = l1; l1 = l1->next; } else { tmp = l2; l2 = l2->next; } head = tmp; while(l1 && l2) { n1 = list_entry(l1, element_t, list); n2 = list_entry(l2, element_t, list); if(strcmp(n1->value, n2->value) < 0) { tmp->next = l1; tmp = tmp->next; l1 = l1->next; } else { tmp->next = l2; tmp = tmp->next; l2 = l2->next; } } if(l1) tmp->next = l1; if(l2) tmp->next = l2; return head; } ``` ```c struct list_head *mergeSortList(struct list_head *head) { // merge sort if (!head || !head->next) return head; struct list_head *fast = head->next; struct list_head *slow = head; // split list while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } fast = slow->next; slow->next = NULL; // sort each list struct list_head *l1 = mergeSortList(head); struct list_head *l2 = mergeSortList(fast); // merge sorted l1 and sorted l2 return mergeTwoList(l1, l2); } ``` 以上 `merge sort` 實作參考自 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) ```c void q_sort(struct list_head *head) { if (!head || list_empty(head)) return; head->prev->next = NULL; head->next = mergeSortList(head->next); struct list_head *cur; for (cur = head; cur->next; cur = cur->next) cur->next->prev = cur; cur->next = head; head->prev = cur; return; } ``` 透過 `merge sort` 來完成排序，在實作時一開始忘記將最後一個節點的 next 指向 NULL ，導致程式有無窮迴圈的問題，需要注意，另外在排序完後，記得要將每個節點的 prev 重新連結上，還有將最後一個節點的 next 重新指向 head ，這樣才算完成。 ### q_descend ```c int q_descend(struct list_head *head) { if (!head || list_empty(head)) return 0; element_t *maxNode = list_last_entry(head, element_t, list), *curNode = NULL; int count = 0; for (struct list_head *cur = head->prev, *safe = cur->prev; cur != head; cur = safe, safe = cur->prev) { curNode = list_entry(cur, element_t, list); if (strcmp(maxNode->value, curNode->value) > 0) { list_del(&curNode->list); q_release_element(curNode); } else { maxNode = curNode; ++count; } } return count; } ``` 這邊的做法是從後往前掃來做檢查， `maxNode` 即為當前節點右側的節點中擁有最大值的那一個，當前節點的值如果小於 `maxNode` 的值則做刪除的動作，反之則更新成 `maxNode` 。 ### q_merge ```c int q_merge(struct list_head *head) { queue_contex_t *first = list_first_entry(head, queue_contex_t, chain), *entry = NULL; list_for_each_entry (entry, head, chain) { if (entry->id == first->id) { continue; } list_splice_init(entry->q, first->q); } q_sort(first->q); return q_size(first->q); } ``` 這邊很直接的先將所有的佇列連接在一起，然後再<s>一口氣</s>一次將全部做排序，但這邊並沒有運用到各個佇列已經排序好的性質，可以再思考更好的做法。 :::warning 避免不精準的詞彙，「一口氣」對應的英語是什麼？這對於解析程式有何幫助？ :notes: jserv > 已修正，謝謝老師 ::: :::info 目前測試分數 95 / 100 複雜度仍須提升 ::: --- ## 以 Valgrind 分析記憶體問題 用 `make valgrind` 來測試，發現大部分都有如下的狀況: ``` ==32347== 32 bytes in 1 blocks are still reachable in loss record 1 of 6 ==32347== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==32347== by 0x10CBE0: do_new (qtest.c:146) ==32347== by 0x10DF3F: interpret_cmda (console.c:181) ==32347== by 0x10E4F4: interpret_cmd (console.c:201) ==32347== by 0x10E8F5: cmd_select (console.c:610) ==32347== by 0x10F1E1: run_console (console.c:705) ==32347== by 0x10D331: main (qtest.c:1274) ``` 後來發現在 `qtest.c` 中的 `q_quit` 裡面，第一行就直接做了 `return true;` ，因此趕快將這行拿掉就恢復正常了，而後來發現這個問題在原本的 [lab0](https://github.com/sysprog21/lab0-c) 已經被修正掉了，這也提醒了我要記得同步專案。 :::info 測試結果 100 / 100 ::: --- ## 在 qtest 提供新的命令 shuffle ### 實作 shuffle 一開始花了一些時間摸索如何在 `qtest` 中提供新的命令，後來發現要在 qtest.c 中的 `console_init` 加入以下程式碼。 ```c ADD_COMMAND(shuffle, "Shuffle queue", ""); ``` 並在 qtest.c 中新增 `do_shuffle` 函式來實作洗牌功能。 ```c static bool do_shuffle(int argc, char *argv[]) { if (argc != 1) { report(1, "%s takes no arguments", argv[0]); return false; } if (!current) { report(3, "Warning: Try to operate null queue"); return false; } set_noallocate_mode(true); if (exception_setup(true)) q_shuffle(current->q); exception_cancel(); set_noallocate_mode(false); q_show(3); return !error_check(); } ``` 以下 `q_shuffle` 則是基於 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法的 Modern method 來實作。 ```c void q_shuffle(struct list_head *head) { int len = q_size(head), roll = 0; struct list_head *rollNode = head->next, *lastNode = head->prev; for (int i = len; i > 1; --i) { roll = rand() % i; if (roll == i - 1) { lastNode = lastNode->prev; continue; } rollNode = head->next; for (int j = 0; j < roll; ++j) rollNode = rollNode->next; // swap value element_t *A = list_entry(rollNode, element_t, list), *B = list_entry(lastNode, element_t, list); char *tmp = A->value; A->value = B->value; B->value = tmp; lastNode = lastNode->prev; } return; } ``` 如果隨機抽選到的 `node` 是尚未被選擇的最後一個 `node` (也就是將被交換的那一個)，則省略交換的過程，直接做 continue ，反之則針對值來做交換的動作。 ### 亂度分析 :::warning 有待分析 ::: ## 執行 `option entropy 1` ``` cmd> option entropy 1 cmd> ih RAND 10 l = [jmhfj(21.88%) dlubbo(26.56%) abzjqxrsr(35.94%) uuiye(21.88%) mxfangfme(32.81%) rdjtz(26.56%) dpjujvuf(29.69%) yvrkshlka(35.94%) dkgjszx(32.81%) xgvygicw(32.81%)] ```
Last changed by  
 
yozz
285

Read more

2023q1 Homework5 (assessment)

contributed by < csm1735 > 〈因為自動飲料機而延畢的那一年〉心得 一開始看到這篇文章的標題時，我感到有些疑惑。作者竟然選擇了延畢來做飲料機，這樣的決定是否真的值得呢？在閱讀文章時，我了解到作者為了這個專案承受了各種壓力。如果換做是我，恐怕沒有勇氣做出這樣的決定。但是，仔細想想，當我們還年輕、還是學生的時候，就應該勇於放手一搏，做自己真正想做且值得去做的事情。畢竟，這樣的經驗不是每個人都能擁有，值得珍惜。 其中令我印象深刻的一段是，作者去找 Jserv 聊聊後， Jserv 指出作者最大的問題在太害怕失敗了，我認為這是許多人都面臨的問題，包括我自己。每當我遇到困難時，我會因為害怕失敗而選擇逃避，只做自己有把握的事情，然而，這樣做會錯過許多變強的機會，最終還是在原地，停滯不前。 此外，在文章的最後，作者提到 「飲料機的程式愷宏是寫不出來的，之所以能在一個月內完成，是因為我在大學期間就寫過好幾個網站了。愷宏能和工廠溝通、設計出可用的零件，是因為他在大一就在跑工廠做東西了。紘銘能輕易的設計出飲料機的電路，是因為他曾花了很多時間在電子電路課上頭，做了很多習題，纏著教授把每個疑惑都搞懂才罷休。」

4/16/2023
2023q1 Homework3 (quiz3)

contributed by < csm1735 > 測驗 1 測驗 2 測驗 3 LFSR 的運作原理及案例 Linear feedback shift register (LFSR) 是指給定前一狀態，將該輸出的線性函數作為輸入的移位暫存器 static void lfsr(uint64_t *up) {

3/22/2023
2023q1 Homework3 (fibdrv)

contributed by < csm1735 > 開發環境 $ 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

3/18/2023
2023q1 Homework2 (quiz2)

contributed by < csm1735 > 測驗 1 解釋程式碼原理 此題關鍵在於找出最高位元的 1 ，並將從此位元到最低位元的所有位元 set 為 1 ，再透過對 x + 1 來使其進位成 2 的冪的值。 舉例來說 x 如果是 $(0010$ $1010)_2$ ，需要先 set 成 $(0011$ $1111)_2$ ，再透過 x + 1 成為 $(0100$ $0000)_2$ 而因 x 為 64 位元的 uint64_t ，故最多需要右移 63 個位元。 因此程式碼為:

3/5/2023
Read more from yozz
Published on HackMD