# 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]);
// }
}
}
```
Sign in with Wallet
Connect another wallet