第 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

floyd's tortoise and hare algorithm 最早是用來判斷一個 linked list 中是否存在 cycle 用的。演算法的步驟以及證明可以參考 nelsonlai1 同學寫的文章
(私心推薦 JomaTech 的介紹 影片 ,從 07:10 開始有以數學證明該演算法)

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

NULL 的發音為何?
怒偶?
正確發音應為 [nʌl](音近no) 請不要發「怒偶」,他沒有怒。

可以聽聽看 外國人都怎麼念NULL

不連續的記憶對對計算機架構的什麼東西不友善?
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,下列為輸出真值表:

input 1 input 2 output
0 0 0
0 1 1
1 0 1
1 1 1

那麼在這裡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

Select a repo