# 2024q1 Homework1 (lab0)
contributed by < `tseng0201` >

# 開發環境

$ gcc -v
gcc version 12.3.0 (Ubuntu 12.3.0-1ubuntu1~23.04) 

$ 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):                  16
  On-line CPU(s) list:   0-15
Vendor ID:               GenuineIntel
  Model name:            12th Gen Intel(R) Core(TM) i7-12650H
    CPU family:          6
    Model:               154
    Thread(s) per core:  2
    Core(s) per socket:  10
    Socket(s):           1
    Stepping:            3
    CPU(s) scaling MHz:  39%
    CPU max MHz:         4700.0000
    CPU min MHz:         400.0000
    BogoMIPS:            5376.00

## 指定的佇列操作
> 延伸 [2023q1 Homework1 (lab0)](https://hackmd.io/6-xzV21LTWGz9I2uOnYSdg?view)，本頁面紀錄今年度的更改。

### `q_ascend`

:::danger
對照 Dictionary.com 對 [implement](https://www.dictionary.com/browse/implement) 一詞的解釋:
* to fulfill; perform; carry out:
* to put into effect according to or by means of a definite plan or procedure.
* Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
* to fill out or supplement

「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。

$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::

<s>實現</s> 與 q_descend 大致相同，只是將 if 判斷式由 (cmp >= 0) 改為 (cmp <= 0)

int q_ascend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;
    struct list_head *ptr = head->prev;
    while (ptr != head && ptr->prev != head) {
        int cmp = strcmp(list_entry(ptr, element_t, list)->value,
                         list_entry(ptr->prev, element_t, list)->value);
        if (cmp <= 0)
            q_delete_element(ptr->prev);
        else
            ptr = ptr->prev;
    }
    return q_size(head);
}

### `merge_two_sorted_list`

:::danger
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","
:::

加入 bool descend 參數，決定排序的方式是升序還是降序<s>, </s> 透過對 strcmp 的回傳值與 descend 進行 XOR 運算改變比較的結果。

- struct list_head *merge_two_sorted_list(struct list_head *q_1, struct list_head *q_2)
+ struct list_head *merge_two_sorted_list(struct list_head *q_1, struct list_head *q_2, bool descend)
{
    if (!q_1 || !q_2)
        return (struct list_head *) ((__UINTPTR_TYPE__) q_1 |
                                     (__UINTPTR_TYPE__) q_2);
    struct list_head *head = NULL, **ptr = &head, **node;
    for (node = NULL; (__UINTPTR_TYPE__) q_1 & (__UINTPTR_TYPE__) q_2;
         *node = (*node)->next) {
        node = ((strcmp(list_entry(q_1, element_t, list)->value,
-                       list_entry(q_2, element_t, list)->value) <= 0))
+                       list_entry(q_2, element_t, list)->value) <= 0) ^ descend)
                   ? &q_1
                   : &q_2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr =
        (struct list_head *) ((__UINTPTR_TYPE__) q_1 | (__UINTPTR_TYPE__) q_2);
    return head;
}

---

## 改進 dudect
### 引入 [oreparaz/dudect](https://github.com/oreparaz/dudect) 中 percentile 處理

### 修正排序後數據不匹配的問題
在原始論文中，prepare_percentiles 函數僅對 ctx->exec_times 進行排序，卻未對其相應的 ctx->classes 進行同步排序，這造成了排序後的時間和類別之間失去了一致對應關係。以下由 ChatGPT 提供的程式碼示例引入了一個新的結構體，用於在排序過程中保留 exec_times 與 classes 之間的關聯性。

:::danger
程式碼註解一律使用美式英語書寫。
:::

+// 定義一個結構體來存儲每次測量的時間和類別
+typedef struct {
+    uint64_t time; // 假設時間使用 uint64_t 類型
+    int class;     // 對應的類別
+} measurement_t;

+// 比較函數，用於根據時間排序
+int compare_measurements(const void *a, const void *b) {
+    const measurement_t *ma = (const measurement_t *)a;
+    const measurement_t *mb = (const measurement_t *)b;
+    return ma->time - mb->time;
+}


static void prepare_percentiles(dudect_ctx_t *ctx) {
-  qsort(ctx->exec_times, ctx->config->number_measurements, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
+    measurement_t *measurements = malloc(ctx->config->number_measurements * sizeof(measurement_t));
+    // 填充結構體數據
+    for (size_t i = 0; i < ctx->config->number_measurements; i++) {
+        measurements[i].time = ctx->exec_times[i];
+        measurements[i].class = ctx->classes[i]; 
+    }

+    // 對結構體數組進行排序
+    qsort(measurements, ctx->config->number_measurements, sizeof(measurement_t), compare_measurements);

+    // 將排序後的數據寫回 ctx 結構
+    for (size_t i = 0; i < ctx->config->number_measurements; i++) {
+        ctx->exec_times[i] = measurements[i].time;
+        ctx->classes[i] = measurements[i].class;
+    }

+    free(measurements); // 釋放臨時數組

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

:::warning
改進此部分程式後，以數學分析確認其效益。
:::