2022q1 Homework1 (lab0)

# 2022q1 Homework1 (lab0) contributed by < `ShallowFeather` > ### Reviewed by `ItisCaleb` * 程式碼的改動可以附上 git commit 的連結 * 改動 dudect 時，應該去解釋改動的意義 ## 開發環境 Windows 11 WSL2 ```shell $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 Copyright (C) 2021 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. $ 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) i5-9300H CPU @ 2.40GHz CPU family: 6 Model: 158 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 Stepping: 10 BogoMIPS: 4800.01 ``` ## 開發過程 ### q_new 利用 `malloc` 來配置記憶體並使用 `list.h` 中的 `INIT_LIST_HEAD` 來初始化 `head` 並且進行回傳 ```c struct list_head *q_new() { struct list_head *head = malloc(sizeof(struct list_head)); if (!head) return NULL; INIT_LIST_HEAD(head); return head; } ``` ### q_free 如果使用 `list_for_each` 進行走訪，會導致當釋放掉目前的 `pos` 時會讓他無法找到下一個節點因此使用 `list_for_each_entry_safe` 巨集，此巨集會使用一個額外的 n 來暫時儲存下一個節點的 `entry` 值，讓他可以在刪除掉目前的節點以後還能夠繼續執行。 :::warning 改進漢語描述，特別是「每次循環時」這句。 :notes: jserv ::: 而在開始時，需先檢查 `l` 是否為空，如為空就無須額外處理。 ```c void q_free(struct list_head *l) { if (!l) return; element_t *pos, *n; list_for_each_entry_safe (pos, n, l, list) { q_release_element(pos); } free(l); } ``` ### q_insert_head / q_insert_tail 這兩段程式碼的實作方式很相似，都是利用 `malloc` 函數分配記憶體給新節點，若分配失敗則直接回傳 `false`。接著使用 `strdup` 函數為新節點的 `value` 成員分配記憶體空間，並將傳入的字串 `s` 複製到新分配的空間中。若分配失敗，則需要回傳 `false` 並釋放先前使用 `malloc` 分配的記憶體空間。最後，呼叫 `list_add` 或 `list_add_tail` 函數，將新節點加入到串列中。 :::warning 改進漢語描述。 :notes: jserv ::: ```c bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *tmp = malloc(sizeof(element_t)); if (!tmp) return false; tmp->value = strdup(s); if (!tmp->value) { free(tmp); return false; } list_add(&tmp->list, head); return true; } ``` ```c bool q_insert_tail(struct list_head *head, char *s) { if (!head) return false; element_t *tmp = malloc(sizeof(element_t)); if (!tmp) return false; tmp->value = strdup(s); if (!tmp->value) { free(tmp); return false; } list_add_tail(&tmp->list, head); return true; } ``` ### q_remove_head / q_remove_tail 跟上面一樣這兩段的實作很相像目標在於清除佇列的第一個元素，`sp` 是一個已分配記憶體空間的字元陣列，而 `bufsize` 是他的大小(長度)。首先利用 `list_del` 來刪除第一個元素，並利用 strncpy 去將剛剛刪除的元素中的 `value` 複製到 `sp` 中，並且也需要檢查 `bufsize` 為 0 的情況來避免 `bufsize - 1` 為 `-1` 的情況 ```c /* Remove an element from head of queue */ 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_entry(head->next, element_t, list); list_del(head->next); if (sp && bufsize != 0) { strncpy(sp, tmp->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return tmp; } ``` 而 remove_tail 只需要將 `head->next` 修改成 `head->prev` 即可 ```c /* Remove an element from tail of queue */ 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_entry(head->prev, element_t, list); list_del(head->prev); if (sp && bufsize != 0) { strncpy(sp, tmp->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return tmp; } ``` ### q_size 利用 `list_for_each` 來迭代整個串列並利用 `len` 變數來計算總共的數量，最後回傳 ```c /* Return number of elements in queue */ int q_size(struct list_head *head) { if (!head) return 0; int len = 0; struct list_head *li; list_for_each (li, head) len++; return len; } ``` ### q_delete_mid 利用兩個指標一個走的速度是另一個的兩倍，而當跑到最後一項時，較慢的那個指標便會是中間值，參考連結中 Leetcode 的解法 ```c /* Delete the middle node in queue */ bool q_delete_mid(struct list_head *head) { // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ if(head == NULL || head->next == NULL) return false; struct list_head *fastNode = head->next, *slowNode = head->next, *lastNode = head->prev; while(fastNode != lastNode && fastNode->next != lastNode) { fastNode = fastNode->next->next; slowNode = slowNode->next; } list_del(slowNode); return true; } ``` :::warning TODO:降低記憶體存取的數量。 :notes: jserv ::: 參考自 [Linux 核心實作 (2023): 第 1 週課程 (隨堂測驗)](https://www.youtube.com/watch?v=wwzxJx6lSFg) 根據 `1:46:30` 所說，由於是雙向的，所以可以從頭尾跑。 ```c /* Delete the middle node in queue */ bool q_delete_mid(struct list_head *head) { // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ if (head == NULL || head->next == NULL) return false; struct list_head *frontNode = head->next, *backNode = head->prev; while (frontNode != backNode && frontNode->next != backNode) { frontNode = frontNode->next; backNode = backNode->prev; } list_del(frontNode); q_release_element(list_entry(frontNode, element_t, list)); return true; } ``` ### q_delete_dup 由於該串列已「排序」，因此只需要利用 `strcmp` 去檢查目前的節點和下一個節點是否相同，需要注意: 1. 是否只有單個節點，如果沒有去檢查且只有單個節點也就是 `head->next` 等於 `head` 時，會將該節點刪除，導致不符合所求 2. 要求為刪除有重複的節點，而非讓整個串列不會出現重複的節點，因此需要多一個 `bool` 去紀錄紀錄上一個節點是否需要被刪除。 ```c /* Delete all nodes that have duplicate string */ bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if(head == NULL) return false; bool checkDup = false; element_t *pos, *n; list_for_each_entry_safe(pos, n, head, list) { if(&n->list != head && strcmp(pos->value, n->value) == 0) { checkDup = true; list_del(&pos->list); q_release_element(pos); } else if(checkDup) { list_del(&pos->list); q_release_element(pos); checkDup = false; } } return true; } ``` ### q_reverse 迭代整個串列並且對每個節點交換其 `next` 以及 `prev` 值 ```c /* Reverse elements in queue */ void q_reverse(struct list_head *head) { if (head == NULL) return; struct list_head *pos, *n, *tmp; list_for_each_safe (pos, n, head) { tmp = pos->next; pos->next = pos->prev; pos->prev = tmp; } tmp = head->next; head->next = head->prev; head->prev = tmp; } ``` ### q_reverseK 用一個 `cnt` 紀錄經過的節點數量，當等於 `k` 時利用 `list_cut_position` 去切割，而根據 `list.h` 當中函數的說明中可以得知當第二個參數非空時，會將第一格參數取代。最後再將執行過 `reverse` 操作的節點丟回去 `tmp` 的前面，並將 `tmp` 設定在 `n->prev` 的位置上也就是上次切割的點。 ```c void q_reverseK(struct list_head *head, int k) { // https://leetcode.com/problems/reverse-nodes-in-k-group/ if (head == NULL) return; struct list_head *pos, *n, *tmp = head; int cnt = 0; LIST_HEAD(tmp_head); list_for_each_safe (pos, n, head) { cnt++; if (cnt == k) { list_cut_position(&tmp_head, tmp, pos); q_reverse(&tmp_head); list_splice_init(&tmp_head, tmp); cnt = 0; tmp = n->prev; } } return; } ``` ### q_sort 參考 [itiscaleb](https://hackmd.io/@ItisCaleb/S1v9IQpai) 的程式碼 :::warning 附上對應的超連結。 :notes: jserv ::: 使用 `mergeSort` 來實作排序首先利用快慢指標找到中點並去做切割。而後進入遞迴，將其分割成小塊並利用 `strcmp` 來比較大小並合併。 ```c void merge2list(struct list_head *left, struct list_head *right, struct list_head *result) { while (!list_empty(left) && !list_empty(right)) { element_t *first = list_entry(left->next, element_t, list); element_t *second = list_entry(right->next, element_t, list); if (strcmp(first->value, second->value) <= 0) list_move_tail(&first->list, result); else list_move_tail(&second->list, result); } if (!list_empty(left)) list_splice_tail(left, result); else list_splice_tail(right, result); } void q_sort(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) return; struct list_head *slow = head, *fast = head; do { fast = fast->next->next; slow = slow->next; } while (fast != head && fast->next != head); LIST_HEAD(left); LIST_HEAD(right); list_splice_tail_init(head, &right); list_cut_position(&left, &right, slow); q_sort(&left); q_sort(&right); merge2list(&left, &right, head); } ``` ### q_descend 如果讓他由後跑到前，題目就變成了找出遞增數列。 ```c int q_descend(struct list_head *head) { if (!head || list_empty(head)) return 0; struct list_head *now = head->prev, *tmp = now->prev; while (tmp != head) { if (strcmp(list_entry(tmp, element_t, list)->value, list_entry(now, element_t, list)->value) < 0) { list_del_init(tmp); q_release_element(list_entry(tmp, element_t, list)); } else { now = tmp; } tmp = now->prev; } return q_size(head); } ``` ### q_merge 單純將所有 `list` 組合起來並直接 `sort`。 ```c int q_merge(struct list_head *head) { // https://leetcode.com/problems/merge-k-sorted-lists/ if (head == NULL || list_empty(head)) return 0; queue_contex_t *contex = list_first_entry(head, queue_contex_t, chain), *pos = NULL; int ret = q_size(contex->q); list_for_each_entry (pos, head, chain) { if (contex == pos) continue; ret += pos->size; list_splice_tail_init(pos->q, contex->q); } q_sort(contex->q); return ret; } ``` TODO 利用分治等手段加速該函式 --- ## 實作 Shuffle 命令在 `console.h` 中發現了 ``` /* Add a new command */ void add_cmd(char *name, cmd_func_t operation, char *summary, char *parameter); #define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param) ``` 之後在 `qtest.c` 中加入 `do_shuffle` 當中內容參考 `do_reverseK` 以及 `do_merge` 的檢查 ```c static book do_shuffle(int argc, char* argv[]) { if (argc != 1) { report(1, "%s takes no arguments", argv[0]); return false; } if (!current || !current->q) report(3, "Warning: Calling shuffle on null queue"); error_check(); 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` 需在 `queue.h` 中定義並於 `queue.c` 中實作 ```c void q_shuffle(struct list_head *head) { if(head == NULL || list_empty(head)) return; int len = q_size(head); struct list_head *tmp; while(len) { tmp = head->next; for(int i = 0; i < (rand() % len) - 1; i++) { tmp = tmp->next; }; list_move_tail(tmp, head); len--; } return; } ``` 不過由於修改到 `queue.h` <s>好像跑不過測試QQ</s> :::warning 避免帶有個人色彩的發言，更別說「好像」，理工人說話要精準。 :notes: jserv ::: ## dudect `dudect` 的檢查主要分成三部分 1. 反覆測量兩個不同的測資的運行時間，其一值固定，而另一值則在每次測量時皆為隨機值 2. 預處理以及將如 `process interupt` 之類無關的時間剪裁掉或丟棄大於固定的、無關閾值的測量值 3. 嘗試去推翻兩個時間分布相等的假設，利用以下兩種檢測 1. t-test: `Welch's t-test`(當 t 值超過某個閾值就能斷定可能存在性能方面的問題) 2. Non-parametric tests ### 改進 duduct 依據作業要求知道缺乏了 `percentile` 因此將 `oreparaz/dudect` 當中的程式碼移植到 `dudect/fixure.c` 當中 ```c static int cmp(const int64_t *a, const int64_t *b) { return (int) (*a - *b); } static int64_t percentile(int64_t *a, double which, size_t size) { qsort(a, size, sizeof(int64_t), (int (*)(const void *, const void *)) cmp); size_t array_position = (size_t) ((double) size * (double) which); assert(array_position >= 0); assert(array_position < size); return a[array_position]; } /* set different thresholds for cropping measurements. the exponential tendency is meant to approximately match the measurements distribution, but there's not more science than that. */ 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); } } static void update_statistics(const int64_t *exec_times, uint8_t *classes, int64_t *percentiles, t_context_t *ttest_ctxs[]) { for (size_t i = 0; i < N_MEASURES; i++) { int64_t difference = exec_times[i]; /* CPU cycle counter overflowed or dropped measurement */ if (difference <= 0) continue; /* do a t-test on the execution time */ t_push(ttest_ctxs[0], difference, classes[i]); // t-test on cropped execution times, for several cropping thresholds. for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES; crop_index++) { if (difference < percentiles[crop_index]) { t_push(ttest_ctxs[crop_index + 1], difference, classes[i]); } } // second-order test (only if we have more than 10000 measurements). // Centered product pre-processing. // if (ctx->ttest_ctxs[0]->n[0] > 10000) { // double centered = (double)difference - // ctx->ttest_ctxs[0]->mean[ctx->classes[i]]; t_push(ctx->ttest_ctxs[1 + // DUDECT_NUMBER_PERCENTILES], centered * centered, ctx->classes[i]); // } } } ```

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.