# 2020q3 Homework6 (quiz6)
contributed by <`joe-U16`>
###### tags: `sysprog2020`

## 測驗 `1`

## 測驗 `2`

## 測驗 `3`

### 1. 解釋程式碼的運作機制。

/* clang-format off */
#define cons(x, y) (struct llist[]){{y, x}}
/* clang-format on */

[Disabling Formatting on a Piece of Code](https://clang.llvm.org/docs/ClangFormatStyleOptions.html#disabling-formatting-on-a-piece-of-code)
上面將巨集包住的方法，可以避免巨集因為格式改變而導致程式錯誤。

#### 看到下面 cons 這個 Macro:

#define cons(x, y) (struct llist[]){y, x}

* 利用 ==compound literal== 建立 static linked list
* 可針對未知大小的 array/struct 初始化，也可以直接對特定位置的 array 或 struct 的內容賦值
* compound literal 可以做 lvalue ，可以傳特定型別或自己定義的 struct

> C99 [6.5.2.5] Compound literals
> * The type name shall specify an object type or an array of unknown size, but not a variable length array type.
> * A postfix expression that consists of a parenthesized type name followed by a braceenclosed list of initializers is a compound literal. It provides an unnamed object whose value is given by the initializer list.
> * If the type name specifies an array of unknown size, the size is determined by the initializer list as specified in 6.7.8, and the type of the compound literal is that of the completed array type. Otherwise (when the type name specifies an object type), the type of the compound literal is that specified by the type name. In either case, the result is an lvalue.

將上述程式碼的 `struct llist *list = cons(cons(cons(cons(NULL, A), B), C), D);` 展開如下:

// 展開 cons(cons(cons(cons(NULL, A), B), C), D);
llist.val = 9;
llist.next = &cons(cons(cons(NULL, A), B), C);

// 展開 cons(5, cons(4, cons(7, NULL)))
llist.val = 5;
llist.next = &cons(cons(NULL, A), B);

// 展開 cons(4, cons(7, NULL))
llist.val = 4;
llist.next = &cons(NULL, A);

//展開 cons(7, NULL)
llist.val = 7;
llist.next = NULL;

// A = 7
// B = 4
// C = 5
// D = 9

便會得到如下的 linked list

+------+------+     +------+------+     +------+------+     +------+------+
|      |      |     |      |      |     |      |      |     |      |      |
|  9   | next +---->|  5   | next +---->|  4   | next +---->|  7   | NULL |
|      |      |     |      |      |     |      |      |     |      |      |
+------+------+     +------+------+     +------+------+     +------+------+
   ^
   |
  head

#### 先觀察 `sort` 的行為：

void sort(struct llist **head)
{
    struct llist *sorted = NULL;
    for (struct llist *current = *head; current;) {
        struct llist *next = current->next;
        sorted_insert(&sorted, current);
        current = next;
    }
    *head = sorted;
}

會依序走訪 list ，並將 node 加到 sorted list。
使用 `sorted_insert` 將 node 加到 sorted list。

#### 觀察 `sorted_insert` 的行為：

void sorted_insert(struct llist **head, struct llist *node)
{
    if (!*head || (*head)->val >= node->val) {
        SS1;
        SS2;	
        return;
    }
    struct llist *current = *head;
    while (current->next && current->next->val < node->val)
        current = current->next;
    node->next = current->next;
    current->next = node;
}

// SS1: node->next = *head
// SS2: *head = node

**已知 sort 須將 list 由小到大排序。**
* 第一個判斷式 `if (!*head || (*head)->val >= node->val)` 當 `node->value` 較小時做 `SS1` `SS2`
* 因為 node 較小，故將 node 接在 `head` 前面。
* 不難得知 `SS1` `SS2`
* `while (current->next && current->next->val < node->val)`
* 當 node 不為最小，需依序走訪 `sorted list` 尋找適當的插入位置。

### 3. 練習 LeetCode [148. Sort List](https://leetcode.com/problems/sort-list/)

#### 使用 MergeSort

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode ListNode;

ListNode* merge(ListNode* l1, ListNode* l2) {
    // merge with recursive
    if(!l1) return l2;
    if(!l2) return l1;


    if(l1->val<l2->val) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

ListNode* sortList(ListNode* head) {
    // merge sort
    if(!head || !head->next) return head;
    
    ListNode* fast = head->next;
    ListNode* slow = head;
    
    // split list
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;

    // sort each list
    ListNode* l1 = sortList(head);
    ListNode* l2 = sortList(fast);
    
    // merge sorted l1 and sorted l2
    return merge(l1, l2);
}

Leetcode Result:

#### 嘗試將 [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort) 的手法引入到 C 程式中實作
在現代電腦上要做 [software optimization](https://en.wikipedia.org/wiki/Software_optimization) 時，因為用到了 multilevel [memory hierarchies](https://en.wikipedia.org/wiki/Memory_hierarchy)，需要考慮到 [locality of reference](https://en.wikipedia.org/wiki/Locality_of_reference)，來提高效率。
必須想辦法減少在 memory cache 間的 pages 搬運，有些 Cache-aware 的 merge sort algorithm 被提出。
* e.g. the tiled merge sort algorithm
* 在 subarrays 大小為 `S` 時，停止分割 subarrays， `S` 為 CPU's cache 最大可容納的數量，
* subarrays 可使用 in-place sorting algorithm(e.g. [insertion sort](https://en.wikipedia.org/wiki/Insertion_sort))

Implement:
[tiled_merge_sort.c](https://github.com/joe-U16/NCKU-SYSTEM-SOFTWARE-Quiz6/blob/main/tiled_merge_sort.c)

// Insertion Sort 使用測驗題的程式碼

ListNode* merge(ListNode* l1, ListNode* l2) {
    // merge with recursive
    if(!l2) return l1;
    if(!l1) return l2;
    
    if(l1->val<l2->val) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}


#define THR 64

ListNode* sortList(ListNode* head, int count) {
    // merge sort
    if(!head || !head->next) return head;
    
    ListNode* fast = head->next;
    ListNode* slow = head;

    int half_list = count / 2;
    if (half_list < THR)
    {
        Insertsort(&head);
        return head;
    }

    // split list
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;
	
    // sort each list
    ListNode *l1 = sortList(head, half_list);
    ListNode *l2 = sortList(fast, half_list);

    // merge sorted l1 and sorted l2
    return merge(l1, l2);
}

Leetcode Result:

Todo: 用其他方法測試時間變差的原因

## 測驗 `4`
CCC = c1 < c2