第 1, 2 週課堂問答簡記

fennecJ

我們做 quick sort 分而治之，要做 partition，第一週測驗題 partition 的策略是什麼？
一般來說 pivot 可以隨機選也可以從頭拿，本測驗提的作法為從頭拿。
挑第一個 element 作為 pivot，將剩下的 element 分為比 pivot 大和 pivot 小兩個 partition

為何在選出 pivot 後要做 list_del?
因為要把它作為斷點從 list 移出來。後面在執行 list_for_each_entry_safe 時才不會存取到 pivot 這個 element。

Quicksort 先排序小的或先排序大的會有差嗎? (考慮到 single thread 與 multiple thread）

你為什麼會覺得它會有差呢？在 single thread 的情形下 list_less 和 list_greater 都需要被排序完，無論先排序 less 還是先排序 greater 都不會影響程式結果。

在 multiple thread 下多了 threads 間的同步和會合等情形需要考慮，此時誰先誰後就會有影響。

list_splice 是做什麼用的？
將2個 list 接在一起
splice 這個字是什麼意思，有其他同義字可以替代嗎？
意思是拼接，可以 merge 代替？
merge 是較不精確的說法
concat?
對，就是這個字，同學們要對同義字有所了解，因為有時候 API 名字會換但用途是不變的。

為何 FFF 要用 list_splice_tail ？
因為我們做的排序是由小排到大，因此 greater 必須被放在後面，所以只能用 list_splice_tail 把 greater 接在後面。

這和前面遞迴用 Quicksort 是不同的，前面是分兩堆去做，但如果是同一個人做（單執行續），執行順序不影響結果，但這裡是 less 、 greater 方向不同的問題。

那 CCC 是什麼？
list_for_each_entry_safe
這個 for_each_safe 和 for_each 有一個很大的差別在於它做了一個副本！ 這個 safe 版本適用在哪裡呢？ 當我從開頭走到結尾時可能會把開頭去掉，為了避免 head 被拿掉發生問題，所以它做了一個副本。

如果 partition 的時候我想在 linked list 中間對半切的話可以怎麼做？
可以用 Floyd's tortoise and hare algorithm，這個 alg 的概念是，設兩個 ptr turtle 和 hare，turtle 每走一步；hare 就走兩步，直到 hare 把整個 list 走完，因為 list 是 circular list，所以 hare 走完整個 list 後會回到 head 或是 head->next，依 list 的 node 數為奇數或偶數個而定。程式碼示意如下:

node *slow, *fast;
slow = head;
fast = head->next->next; // If fast is init to head, 
                         // it will eventually move L/2 + 1 steps
                         // (assume there are L nodes in list)
do{
    fast = fast->next->next; // The list is a circular linked list, there is no need to consider if fast->next is NULL
    slow = slow->next;
}while(fast != head && fast != head->next)
    //slow will be mid point of list

如果本題是 doubly linked list 且我們知道 tail，則我們也可以一個從 head 往後走，一個從 tail 往前走，最後他們相遇的地方也會在 list 中間。

NULL 的發音為何？
怒偶？
正確發音應為 [nʌl]（音近no） 請不要發「怒偶」，他沒有怒。

不連續的記憶對對計算機架構的什麼東西不友善？
cache
所以 cache 會希望它 access 是連續的，那連續的除了空間連續外還有什麼？
時間連續，即 temporal locality
也就是一個是 temporal locality 一個是 spatial locality。
Locality of reference

你#覺得 L1 cache 和 L2 cache 速度差幾倍
實際上是約 10 倍，你剛剛說的 100 倍是用到 RAM 的時候，而 1000 倍則是網路資料傳輸等級的速度，約為 L1 cache 1000～10000

想請問若 DDD 從 list_move_tail 改為 list_move 對程式執行會有什麼影響？
題目要求的是 Stable quick sort ，可以想想一個 sort alg 什麼情況下會被稱為 stable ？ 還有為什麼 quick sort 通常不 stable ？

stable sort alg 指若有多個 elements 有相同的 key value，則 sort 前後其相對關係不變。
e.g
有一 list 5, 3, 3*, 4
其中有兩個 elements 有相同的 key value 3 ，這裡用 3 以及 3* 作為區別。他們兩個的相對關係為 3 在 3* 前面
則經過穩定排序後的結果必為：
3, 3*, 4, 5
若使用不穩定的 sort alg 排序，則結果可能為：
3*, 3, 4, 5
可以看到兩個 3 的相對關係發生改變了。
由於程式是取從開頭 pivot 後往後比較，所以用 list_move_tail 可以確保後面的 ele 被放在後面。
以剛剛提到的 list 5, 3, 3*, 4 為例，則若使用 list_move 的話程式執行會變為：

remained list: 3, 3*, 4
               ^
              item
pivot (5)
less_list: 3

---
remained list: 3*, 4
               ^
              item
pivot (5)
less_list: 3*, 3
---
remained list: 4
               ^
              item
pivot (5)
less_list: 4, 3*, 3
---

可以看到 3* 和 3 的相對位置改變了。

quicksor在怎樣的狀況下效能會有很大的疑慮
quicksort在worstcase的時候為什麼是O(n^2)
quicksort的bestsort是O(nlogn)，worstcase是(n^2)，當quicksort遇到已經排序好的狀況，那他就會變成worstcase，如果偵測到worst的時候現在的程式就會切換成heapsort或是insertion sort，因為這兩個排序遇到快排序完的時候都不會有很差的情況，insertion sort平常看起來不實用，但在快排序好的資料裡表現還不錯，現在的排序法都會截長補短，讓程式能夠體現出比較好的效能

yeiogy123

MergeTwoLists 議題

struct ListNode *mergeTwoLists(struct ListNode *L1, struct ListNode *L2) {
    struct ListNode *head = malloc(sizeof(struct ListNode));
    struct ListNode *ptr = head;
    while (L1 && L2) {
        if (L1->val < L2->val) {
            ptr->next = L1;
            L1 = L1->next;
        } else {
            ptr->next = L2;
            L2 = L2->next;
        }
        ptr = ptr->next;
    }
    ptr->next = L1 ? L1 : L2;
    return head->next;
}

上述是我們利用新節點來合併兩list作法，
這個程式碼中有什麼可以察覺的隱藏問題呢?

可以看到一開始使用了新的結構指標，有使用到malloc的函式，
那他會有什麼隱含的問題?
沒有使用到free()函式
對，沒有使用到free的話，會形成我們所謂的memory leak，
但這裡我們可以使用free去釋放先前指標所存的記憶體空間嗎?
如果使用free的話，那最後副函式的回傳位址可能會有錯誤。
所以在這個地方會因為程式碼順序的問題，而無法使用free去釋放已經動態規劃的記憶體空間，而有可能造成隱含的memory leak問題。
因此我們下面會介紹另外一個

struct ListNode *mergeTwoLists(struct ListNode *L1,
                               struct ListNode *L2) { 
    struct ListNode *head;
    struct ListNode **ptr = &head;
    for (; L1 && L2; ptr = &(*ptr)->next) {
        if (L1->val < L2->val) {
            *ptr = L1;
            L1 = L1->next;
        } else {
            *ptr = L2;
            L2 = L2->next;
        }
    }
    *ptr = (struct ListNode *)((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}

這裡使用了pointer pointer指向head，可以解決無法釋放記憶體配置空間的問題，想問倒數第二行的程式碼中的"|"用途為合?

這裡的"|"為bitwise的OR，下列為輸出真值表：

那麼在這裡bitwise-or的用途為合?

先前for-loop中，會判斷分支是否跳躍直到L1&&L2為False才會跳出。
因此這裡是將剩餘的那條list後半段加入到輸出的list中。

我們可以在把if-else簡化，使用條件三目運算子，
可以簡潔化程式碼，降低cache在block swap時的負擔。

YangYeh-PD

Linux 核心的 hash table 實作

若考慮以下 doubly linked list 的宣告

struct dll_node { 
    struct dll_node *next, *prev;
}

並將它應用在以下刪除節點的函式

void dll_delete_node(struct list_head *l, struct dll_node *n)
{
    struct dll_node *prev = n->prev,
                    *next = n->next;
    
    if (next)
        next->prev = prev;
    
    // Delete and update where list_head points to,
    // which requires the list_head to be passed in.
    if (!prev) {
        l->first = next;
    } else {
        prev->next = next;
    }
}

前面的 struct list_head *l 代表 list 的開頭，而 struct dll_node *n 是準備要被刪除的節點。

沒錯，所以我們可以看到這段函式需要兩個參數，並且需要針對刪除開頭的特殊狀況做額外處裡。
不過倘若我們改用以下的 hlist_node 的宣告

struct hlist_node { 
    struct hlist_node *next, **pprev;
}

並實作刪除節點的函式

void hlist_delete_node(struct hlist_node *n)
{
    struct hlist_node *next = n->next;
                      **pprev = n->pprev;
	
    // Since there is always a pointer which points to node n,
    // no special case is needed to deal with.
    *pprev = next;
    if (next)
        next->pprev = pprev;
}

若我們先不看演算法，請問此函式現在剩哪一個參數？
其中 struct hlist_node **pprev 是什麼意思？
現在參數只剩下待刪除的節點，不需要再給它 list 的開頭位置。
**prev 是一個指向 n 上一個節點的 next 的間接指標。

我們上一週 Linux Torvalds 在 TED 訪談中，提到使用間接指標可以使例外消失。在這個例子當中，*next 一樣是指向下一個節點的指標。但是 **prev 則是使用間接指標。

好… *pprev = next 在做什麼事情？
喔！把下一個節點的指標傳給 *pprev。
如果被刪除掉的節點後面還有節點的話，才會將下個節點的 prev 指回上一個節點的 next。