# [第一周作業排序部份](https://github.com/chishuo9810/lab0-c/blob/8112e166b041737e9408d9c5707d06b993cec9ff/queue.c#L274)
參考 Fundamentals Data Structures in C 2nd Edition 的第1.5章 Performance Analysis
## 前提假設
* 鏈結串列共有 n 個 element
* 每個字串長度為 k
## 使用到的函式
<!-- ### [connect_prev](https://github.com/chishuo9810/lab0-c/blob/8112e166b041737e9408d9c5707d06b993cec9ff/queue.c#L234)
* 作用 ： 將已排序好的鏈結串列的 `prev` 接好。
* 所需要的步數 (step) ： 1 + 1 + 4 * (n-1) + 1 + 1 + 1 = ==4n + 1== 步

struct list_head *connect_prev(struct list_head *head)
{
    struct list_head *cur, *prev;
    cur = head->next;       // 1
    prev = head;            // 1 
    // 迴圈共進行 n-1 次，每次 4 步，跳出迴圈那次要再加 1
    while (cur) {           // 1
        cur->prev = prev;   // 1
        cur = cur->next;    // 1
        prev = prev->next;  // 1
    }
    prev->next = head;      // 1
    return prev;            // 1 
}

### [mergeTwoLists](https://github.com/chishuo9810/lab0-c/blob/8112e166b041737e9408d9c5707d06b993cec9ff/queue.c#L247)
* 作用 ： 將兩個鏈結串列進行合併。
* 所需要的步驟 ：

**假設輸入的兩個鏈結串列長度分別為 a 和 b**
1. 若 a = b

最多需要比較
$$
2 + (2a - 1) \times [1 + (k + 1) + 1 + 1 + 1 + 1] + 1 + 1 + 1 = (2a - 1)(k + 6) + 4
$$

最少需要比較
$$
2 + (a) \times [1 + (k + 1) + 1 + 1 + 1 + 1] + 1 + 1 + 1 = a(k+6) + 4
$$
2. 若 a < b

最多需要比較
$$
2 + (2 \times a) \times [1 + (k + 1) + 1 + 1 + 1 + 1] + 1 + 1 + 1 = (2a)(k+6) + 4
$$
最少需要比較
$$
2 + a \times [1 + (k + 1) + 1 + 1 + 1 + 1] + 1 + 1 + 1 = a(k+6) + 4
$$

struct list_head *mergeTwoLists(struct list_head *first,
                                struct list_head *second)
{
    struct list_head *head = first, **result = &head;                  // 2
    while (1) {                                                        // 1
        if (strcmp(list_entry(first, element_t, list)->value,
                   list_entry(second, element_t, list)->value) <= 0) { // k + 1
            *result = first;                                           // 1
            result = &first->next;                                     // 1
            first = first->next;                                       // 1
            if (!first) {                                              // 1
                *result = second;                                      // 1
                break;                                                 // 1
            }
        } else {
            *result = second;                                          // 1
            result = &second->next;                                    // 1
            second = second->next;                                     // 1
            if (!second) {                                             // 1
                *result = first;                                       // 1
                break;                                                 // 1
            }
        }
    }
    return head;                                                       // 1
}

<!-- ### q_reverse
* 作用 ： 將鏈結串列順序反過來。

不過我這次的測試中完全不會使用到此一函式，因此暫時不加入討論。 -->

### strcmp

在 `/usr/include/string.h` 中找到

/* Compare S1 and S2.  */
extern int strcmp (const char *__s1, const char *__s2)
     __THROW __attribute_pure__ __nonnull ((1, 2));

1. `extern`
關鍵字表明這個函數在其他地方實現（通常在另一個源文件或庫中），並且告訴編譯器該函數的定義在這個翻譯單元之外。例如，這表示 strcmp 函數不是在這個文件中實現的，而是由標準庫提供的。
2. `__THROW`
是一個特定於 GNU C Library (glibc) 的 macro，表示該函數不會引發任何異常。在 glibc 的標頭文件中，__THROW 通常定義為空或 __attribute__ ((__nothrow__))，後者是一個告訴編譯器這個函數不會引發 C++ 異常的編譯器屬性。這對於優化和兼容性是有用的。
3. `__attribute_pure__`
是 GCC 的一個編譯器屬性，表明這個函數是“純粹”的。純粹函數是指不具有副作用，只依賴於其輸入參數的函數。這意味著在相同的輸入下，它總是返回相同的結果，且不修改任何全局狀態。這有助於編譯器進行更好的優化。
4. `__nonnull`
是另一個 GCC 編譯器屬性，表示特定參數不能為空指針。((1, 2)) 表示第一個和第二個參數（即 __s1 和 __s2）都不能為空。這有助於編譯器進行靜態分析並發出警告或錯誤，以確保在調用這個函數時，這些參數不會是 NULL。
:::warning
以上是參考 chatgpt 來解讀 string.h 中 strcmp 的部份，但我還是找不到 strcmp 的實際實做方法，這部份想請教老師要去哪裡找。
:::
參考網路上 strcmp 實做方法

int strcmp (const char *p1, const char *p2)
{
  const unsigned char *s1 = (const unsigned char *) p1;
  const unsigned char *s2 = (const unsigned char *) p2;
  unsigned char c1, c2;

  do
    {
      c1 = (unsigned char) *s1++;
      c2 = (unsigned char) *s2++;
      if (c1 == '\0')
        return c1 - c2;
    }
  while (c1 == c2);

  return c1 - c2;
}

參考 `C Programming: A Modern Approach second edition`，裡面有提到

 The characters in the first array are then compared one by one with the characters in the second array.
 All three functions return as soon as a mismatch is found.

因此 C99 規格的 strcmp 的 big O 確實為 O(k)。


## 進入正題 ： [q_sort](https://github.com/chishuo9810/lab0-c/blob/8112e166b041737e9408d9c5707d06b993cec9ff/queue.c#L274)

### 解釋我的程式運行以及預期效果
以往的合併排序效果如下

digraph G {
    node [shape = box, style=rounded]
   
    node0 [label="2  4  5  3"];
    node1 [label="2  4"];
    node2 [label="5  3"];
    node3 [label="2"];
    node4 [label="4"];
    node5 [label="5"];
    node6 [label="3"];
    node0 -> node1;  node0 -> node2;
    node1 -> node3;  node1 -> node4;
    node2 -> node5;  node2 -> node6;

    node7 [label="2  4"];
    node8 [label="3  5"];
    node9 [label="2  3  4  5"];
    node3 -> node7; node4 -> node7;
    node5 -> node8; node6 -> node8;
    node7 -> node9; node8 -> node9;
}

我改進後的程式預期效果如下

digraph G {
    node [shape = box, style=rounded]
   
    node0 [label="2  4  5  3"];
    node1 [label="2  4  5"];
    node2 [label="3"];

    node0 -> node1;  node0 -> node2;
    node1 -> node9;  
    node2 -> node9;  
    node9 [label="2  3  4  5"];

}

和傳統合併排序法不同在於 : 排列好的子序列不會進行拆分，可以大大降低合併次數。
實際操作後發現不如預期。

**猜測可能原因**
* 雖然降低了比較次數，但多出了判定是否為有序子串列的成本，若有序的子串列數量過多，可能導致花費時間不減反增。

以下進行
1. 討論 ``qtest.c`` 中的亂度
2. 逐步計算函式 ``q_sort`` 所需要的步數(僅討論修改前後會影響的部份，其他一樣的地方暫時不討論)

### qtest.c 中隨機生成字串亂度討論
透過 fill_rand_string 隨機生成長度 5-9 的字串

static void fill_rand_string(char *buf, size_t buf_size)
{
    size_t len = 0;
    while (len < MIN_RANDSTR_LEN)
        len = rand() % buf_size;

    randombytes((uint8_t *) buf, len);
    for (size_t n = 0; n < len; n++) 
        buf[n] = charset[buf[n] % (sizeof(charset) - 1)];
    buf[len] = '\0';
}

而字串內容是透過 `randombytes` 這個函式呼叫將 buf 內填充隨機數字，在藉由取餘數的方式指派每一個位置的英文字母。
`randombytes` 這個函式是透過 [random.c](https://github.com/chishuo9810/lab0-c/blob/master/random.c) 中的

ret = getrandom((char *) buf + offset, chunk, 0);

將 buf 填充隨機數，去參考了 `GETRANDOM(2)` 的 man page，其中提到
:::info
By default, getrandom() draws entropy from the urandom source (i.e., the same source as the /dev/urandom device).
:::
接著我去 `/dev` 資料夾找到 `urandom` 文件，其文件型態為 `crw-rw-rw-`，我完全不知道 `c` 是什麼樣的檔案，參考[網路資料](https://unix.stackexchange.com/questions/60034/what-are-character-special-and-block-special-files-in-a-unix-system)得知全名為 `character special files`，對 `character special files` 的讀寫操作是即時的，因此每次讀取或寫入操作都會立即回應，而不會被系統暫時存儲存。

接著參考 `RANDOM(4)` 的 man page
:::info
The random number generator gathers environmental noise from device drivers and other sources into an entropy pool. The generator also keeps an estimate of the number of bits of noise in the entropy pool. From this entropy pool, random numbers are created.

Linux 3.17 and later provides the simpler and safer getrandom(2) interface which requires no special files; see the getrandom(2) manual page for details.

When read, the /dev/urandom device returns random bytes using a pseudorandom number generator seeded from the entropy pool. Reads from this device do not block (i.e., the CPU is not yielded), but can incur an appreciable delay when requesting large amounts of data.
:::
可以得知 urandom 的隨機數據來自系統的熵池（entropy pool），熵池收集了各種系統的隨機事件，如鍵盤輸入、數標移動、磁盤操作等。
:::warning
所以我這樣要如何知道亂度如何？因為其熵池的隨機事件來自系統，不知道要如何去預測。
:::
### 逐步計算
#### 修改前

while (result != head) {
    if (result->next == head) {
        lists[k] = result;
        lists[k++]->next = NULL;
        break;
    }
    struct list_head *temp;
    lists[k] = result;
    result = result->next->next; 
    lists[k]->next->next = NULL;
    temp = lists[k]->next;
    lists[k]->next = NULL;
    lists[k] = mergeTwoLists(lists[k], temp);
    k++;
}
listsSize = k;
while (listsSize > 1) {
    for (int i = 0, j = listsSize - 1; i < j; i++, j--) {
        lists[i] = mergeTwoLists(lists[i], lists[j]);
    }
    listsSize = (listsSize + 1) / 2;
}

1. 第 1-16 行將鏈結串列的元素兩兩排序並串在一起
* 第 1 行每次迴圈都會進行 1 次比較，共 $\frac{n}{2}$ 次的迴圈。
* 當鏈結串列只有一個元素時才會進入第 2 行的 if statement，本次討論不包含此一情況，因此只有第 2 行的進行了 1 次比較。
* 第 7 至 14 行進行了 7 次指派，而本次迴圈的合併都是兩兩元素合併，比較次數為 k + 10 次。
* 第 16 行進行了 1 次的指派。

第 1-16 行總共進行了
$$
\frac{n}{2} \times [1+1+7+(k+10)] + 1+1 = \frac{n}{2}(k+19)+2
$$
2. 第 17-22 行進行後面的合併排序。
* 第 17 行及第 21 行每次迴圈進行 1 步驟，共 $\log_2(\frac{n}{2})$ 次迴圈，再加上離開迴圈時的步驟，共進行 $$2\times\log_2(\frac{n}{2})+1$$
* 第 18 行的迴圈以及第19行的指派各算 1 步驟，再加上離開迴圈時的步驟，共進行了 $$2\times\sum_{x=1}^{\log_2(\frac{n}{2})} \frac{n}{4 \times 2^x}+1=\frac{n+2}{4}$$
* 接著討論呼叫 mergeTwoLists 的部分，先假設其所需步驟數為 $\frac{最差情況+最好情況}{2}=\frac{3ak}{2}+9a-\frac{k}{2}+1$，總共進行了
$$\sum_{x=1}^{\log_2(\frac{n}{2})}[k(\frac{2+x}{2})+19](\frac{n}{2\times2^x})$$
$$= nk(1-2^{-n-1})-\frac{k}{2}(3-log_2(n)) + \frac{19}{2}n-19$$
第 17-22 行總共進行了
$$
nk(1-2^{-n-1})-\frac{k}{2}(3-log_2(n))+\frac{39}{4}n+\frac{37}{2}+2log_2n
$$
3. 改進前的排序所需要步數為
$$
nk(\frac{3}{2}-2^{-n-1})-\frac{k}{2}(3-log_2(n))+\frac{77}{4}n+\frac{41}{2}+2log_2n
$$
#### 修改後

while (result != head) {
    if (result->next == head) {
        lists[k] = result;
        lists[k++]->next = NULL;
        break;
    }
+    if (strcmp(list_entry(result, element_t, list)->value,
+               list_entry(result->next, element_t, list)->value) <= 0) {
+        lists[k] = result;
+        do {
+            result = result->next;
+        } while (result->next != head &&
+                 strcmp(list_entry(result, element_t, list)->value,
+                        list_entry(result->next, element_t, list)->value) <=
+                     0);
+        result = result->next;
+        result->prev->next = NULL;
+    } else {
-        struct list_head *temp;
-        lists[k] = result;
-        result = result->next->next;
-        lists[k]->next->next = NULL;
-        temp = lists[k]->next;
-        lists[k]->next = NULL;
-        lists[k] = mergeTwoLists(lists[k], temp);
+        lists[k] = result->next;
+        result = result->next->next;
+        lists[k]->next = lists[k]->prev;
+        lists[k]->next->next = NULL;
+    }
    k++;
}
listsSize = k;
while (listsSize > 1) {
    for (int i = 0, j = listsSize - 1; i < j; i++, j--) {
        lists[i] = mergeTwoLists(lists[i], lists[j]);
    }
    listsSize = (listsSize + 1) / 2;
}

1. 第 1-33 行將鏈結串列中有序的子串列串在一起
* 第 1 行每次迴圈都會進行 1 次比較，最糟情況為所有排序為顛倒，則進行 $\frac{n}{2}$ 次的迴圈，最好情況為鏈結串列為完整排序的串列，那只需要 1 次的迴圈。
* 當鏈結串列只有一個元素時才會進入第 2 行的 if statement，本次討論不包含此一情況，因此只有第 2 行的進行了 1 次比較。
2. 假設情況
- [x] 最糟(所有排序顛倒)
* 第 7 行 strcmp 時間複雜度為 O(k)，第 26-31 行進行了 5 次指派，則第 1-32 行共進行步驟數為
$$
\frac{n}{2}\times7\times\ k+1
$$
* 第 34-39 行所需步驟數和修改前一模一樣為
$$
nk(1-2^{-n-1})-\frac{k}{2}(3-log_2(n))+\frac{39}{4}n+\frac{37}{2}+2log_2n
$$
* 因此若遇上最糟情況，其時間複雜度和修改前的時間複雜度差距為
$$
(\frac{n}{2}\times7k + 1 )-\frac{n}{2}(k+19)+2
$$
$$
= n(3k-\frac{19}{2})-1
$$
如果 k，也就是字串長度大於 3，則其執行效率就會比原本的演算法還差。
查看 [qtest.c](https://github.com/chishuo9810/lab0-c/blob/8112e166b041737e9408d9c5707d06b993cec9ff/qtest.c#L169) 中注意到字串長度是這樣生成的

size_t len = 0;
while (len < MIN_RANDSTR_LEN)
    len = rand() % buf_size;

其中 MIN_RANDSTR_LEN 被設為 5，沒有出現有序子串列，也就是最糟情況時，改進後的排序方法會比原本一般的合併排序來的沒效率。