contributed by < wu81177 >
q_new
實作 q_new
過程中,我學習到 list.h
中 list_head
和 INIT_LIST_HEAD
的部份
LIST_HEAD
從結構成員可以發現 list_head
組成的佇列是雙向佇列,同時我也理解到 list_head
除了獨立當作佇列的頭,也會嵌入佇列成員結構體中,佇列成員在這份作業中為 element_t
INIT_LIST_HEAD
此函數 函式是用來初始化已存在的 list_head
,如果要同時宣告並初始化可用 LIST_HEAD()
無論標題和內文中,中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
list_for_each_safe
和 list_for_each_entry_safe
都能確保釋放當前節點不會遺失下一個節點,然而後者有使用 list_entry
,選用它就能輕鬆獲得元素的指標並釋放成員
迴圈中使用 q_release_element
來釋放空間,最後再釋放 head
改進你的漢語表達。
而在運行 q_test
的時候發現有問題因此使用 Valgrind 檢查,以下為檢察結果 :
發現少檢查 head 為空的情況
原先 value
是直接使用 s
的空間,後來參考別人的發現應該使用 strdup
,因為 s
可能會被改動
使用 list_add
可以將新元素放置在 head 後面, list_add_tail
則可以放到 head 前面
發現應該要檢查 strdup
是否成功,如果失敗應該要釋放當前元素,如下
從 list.h
中可以發現 container_of
和 list_entry
的功能完全相同,我選擇了前者來獲取 element_t
的指標
移除元素有 list_del
和 list_del_init
可用,我選用後者,否則再次使用已移除的元素時可能會出錯
使用 list_for_each
走訪佇列並且計數
我使用的方法是從鏈結串列頭 head 出發,同時使用兩個指標進行走訪,一個指標順行,另一個指標則逆行,直到它們相遇(奇數個元素情況)或者在交會前一步(偶數個元素情況)再刪除順行指標所指向的元素
q_release_element
後再用 free
釋放元素內容是多餘的使用兩層迴圈比對,原本都想用 list_for_each
,後來發現會重複比對,改成以下這樣
發現當沒有元素或單元素應該 return true
原先的寫法一直無法順利運作
bool q_delete_dup(struct list_head *head)
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head
struct list_head *outer, *inner, *tmp;
element_t *outer_ele, *inner_ele;
for (outer = (head)->next; outer != (head)->prev; outer = outer->next) {
for (inner = (outer)->next; inner != (head);) {
outer_ele = container_of(outer, element_t, list);
inner_ele = container_of(inner, element_t, list);
if (strcmp(outer_ele->value, inner_ele->value) == 0) {
tmp = inner->next;
list_del(inner);
q_release_element(inner_ele);
inner = tmp;
} else {
inner = inner->next;
}
}
}
return true;
}
明確標注同學的 GitHub 帳號名稱
於是換了寫法,經過同學 kkkkk1109 提醒發現輸入的佇列是已排序的,因此改用他的寫法
你的洞見和檢討呢?
原先針對為排序的串列要使用兩層迴圈檢查有沒有重複,但由於輸入串列已排序,相同的鍵值一定會相鄰,因此只需要檢查相鄰的節點,如果和前者相同即刪除,如此一來可以將時間複雜度降低 N 倍
使用 list_for_each_safe
走訪佇列,沿途使用 list_move
將元素移至首位,如此一來就能倒轉順序
原先想將 q_reverse
視為 q_reverseK
的特例,後來覺得在 q_reverseK
中呼叫 q_reverse
比較好實作
使用 list_cut_position
剪下子佇列,用 q_reverse
倒序後再用 list_splice
接回去
list_cut_position(head_to, head_from, node)
剪下的部份並不包含 head_from
和 node
兩個節點
視為 q_reverseK
k 為2的特例
從 head 逆向走訪佇列,如果下一個元素大於當前元素則使用 list_del
刪除下個元素,如此一來就能留下遞增元素
學會 strcmp ()
怎麼用,此函數會開始比較每一個字串的第一個字元。 如果它們彼此相等,會繼續往下進行配對,直到字元不同或到達較短字串的結尾
從 head 逆向走訪佇列,如果下一個元素小於當前元素則使用 list_del
刪除下個元素,如此一來就能留下遞減元素
由於我在 q_merge
中會使用這個函式,在使用的前一步它已經是分段排序的佇列,這時候如果用 merge sort 會有不錯的效果,所以我選擇用 merge sort實作之
用來合併兩以排序佇列的函式我定義為 merge_two
,在裡面原先判斷是否遞減和兩元素比較大小的部份使用兩層 if
,後來改為以下較緊湊的寫法
而在 q_sort
中,使用先前 q_delete_mid
函式中的方法找到中點,再使用 list_cut_position
剪下後半段,用遞迴的方式分別排序前後兩段再用 merge_two
合併
我首先去理解 queue_contex_t
的運作原理
每個 queue_contex_t
代表了一個佇列,其中 q
會指向佇列的頭,而 chain
則是用來連接不同的 queue_contex_t
在這個函式中,我將所有的佇列使用 list_splice
拼接到第一個佇列,並且使用 list_del_init
移除已合併的佇列,最後再使用 q_sort
排序
list_entry
,後來使用 list_first_entry
有時會出現 merge 完佇列消失的情況
後來發現在清空佇列後不移除當前 queue_contex_t
就好了
使用 make test
測試,只剩 trace-17 無法通過
可以看到唯 it
和 ih
無法通過,有時候 it
會通過,分數為95
最後經由底下修改 lab0/dudect 後可以得到100分
先前使用 Valgrind 發現了實作 q_free
的暇疵,而最後我也嘗試使用它來找出 trace-17
中 it
和 ih
無法通過的原因,使用過程如下
Valgrind 沒有找到記憶體使用問題,同時也發現可能在通過邊緣,上面單獨測試it
和 ih
沒問題
在 queue.c
中加上 q_shuffle
函式, q_test
中加上 do_shuffle
函式檢查是否為空或單節點,還有 console_init
中加上 ADD_COMMAND(shuffle, "Do Fisher-Yates shuffle", "");
使用 git diff
或 diff -u
來產生程式碼之間的變異清單,不要憑感覺填入,注意位移量。
首先在外層迴圈把 len 減少,裡面抽出要交換的 index 後用 list_for_each
找到要交換的 old
和 new
,最後交換節點
,交換的部份原先的寫法沒考慮到兩節點相鄰的狀況
測試 [1, 2, 3, 4] 做 shuffle 1,000,000 次的直方圖,可以看到結果很平均
避免非必要的項目縮排 (即 *
和 -
),以清晰、明確,且流暢的漢語書寫。
檢查程式是否為常數運行時間很重要是因為如果不是,有機會受到時序攻擊,資安上存在疑慮
而作者提出了 dudect 工具來測試程式是否為 constant time ,且相較於其他常見工具, dudect 不需要對硬體行為進行建模,也使用了 cropping 預處理,捨棄掉大於 p percentile 的資料,避免離群值過分影響統計結果,而 t value 的計算是使用 Welch’s t 檢定法。
檢查 fixture.c
發現沒有進行 cropping ,因此從作者的原始碼以 percentile 為關鍵字找到 percentile
和 prepare_percentiles
函式,接著將前述兩個函式和他們會使用到的函式複製到 fixture.c
裡面,再修改 data type 就可以通過 trace-17-complexity,得到滿分
研讀 Linux 核心原始程式碼的 lib/list_sort.c (commit b5c56e) ,首先覺得陌生的就是__attribute__((nonnull()))
,後來了解到__attribute__
是 gcc 中用來附加屬性給函式或結構的用法,提供編譯器額外的訊息,而 nonnull(2,3,4,5)
是用來表示函式內的第 2,3,4,5 個參數不能為空,如此一來就不用在函式內檢查,接下來逐一記錄研讀 list_sort.c
中函式的心得。
不要「舉燭」,你該質疑 Linux 核心開發者「如果不這樣做,會怎樣?」
merge
此函式是用來合併已排序鏈結串列,過程中走訪兩個傳入的串列並且使用 cmp(priv, a, b)
來比較 a, b 節點中 priv
的大小,決定誰要排在前面,最後回傳合併的串列
值得注意的是,根據註解的說法,此函式回傳的是單向並且非環狀的串列,這樣比較適合多次合併使用。
merge_final
前面的 for 迴圈中,除了將兩個串列合併之外,也建立了雙向的連接,然而就算是 b 先結束, a 剩下部份的開頭也統一改名為 b
這段主要是將 b 剩下的部份改成雙向串列,並且在最後將頭尾相接使其形成環狀,但 if (unlikely(!++count))
這段看不懂,經過查找資料後了解 unlikely
是一個巨集被定義為 # define unlikely(x) __builtin_expect(!!(x), 0)
,其中 !!(x)
會確保輸入值轉變為布林值 ,而 __builtin_expect
是 gcc 的內建函式,查看手冊中 Built-in Function: long __builtin_expect (long exp, long c) 舉例:
當 foo ()
被執行的情況很罕見的時候可以這樣寫,幫助編譯器最佳化
而在 merge_final
中 count
增加,就會變非 0 ,執行 cmp(priv, b, b)
,但我還是不知道為什麼要執行 cmp(priv, b, b)
比較 b 自己,而且由於 ++ 是在前面,所以在執行第一次的時候 count
就會是非 0
list_sort
for 迴圈會逐位尋找二進位 count
,直到遇到第一個 0 結束迴圈,接下來判斷如果剩餘的位數存在 1 就進行合併,這樣做相當於當 count+1 不為 時合併,參考何時合併的表格:
count 變化 | count 二進位 | merge | pending 上的節點 |
---|---|---|---|
0 1 | 0000 0001 | no() | 1 |
1 2 | 0001 0010 | no() | 1 1 |
2 3 | 0010 0011 | yes | (2) 1 |
3 4 | 0011 0100 | no() | 2 1 1 |
4 5 | 0100 0101 | yes | 2 (2) 1 |
5 6 | 0101 0110 | yes | (4) 1 1 |
6 7 | 0110 0111 | yes | 4 (2) 1 |
7 8 | 0111 1000 | no() | 4 2 1 1 |
8 9 | 1000 1001 | yes | 4 2 (2) 1 |
9 10 | 1001 1010 | yes | 4 (4) 1 1 |
10 11 | 1010 1011 | yes | 4 4 (2) 1 |
11 12 | 1011 1100 | yes | (8) 2 1 1 |
12 13 | 1100 1101 | yes | 8 2 (2) 1 |
13 14 | 1101 1110 | yes | 8 (4) 1 1 |
14 15 | 1110 1111 | yes | 8 4 (2) 1 |
15 16 | 1111 10000 | no() | 8 4 2 1 1 |
而整個函式會逐一把原始串列 list
的節點移到待處理串列 pending
, 而 pending
中已排序的子串列會以前段提到的規則合併,直到原始 list
輸入完,接著在最後的 for 迴圈中會繼續合併 pending
中子串列,在這個階段是取最後一個和倒數第二個子串列合併成一個,直到只剩兩個子串列就結束迴圈,執行 final_merge
完成全部的合併
Merge sort 可分成 bottom-up 和 top-down , top-down 為課本典型的演算法,將待排序序列分成左右兩個子序列,左右又繼續分裂直到子序列長度是一再合併,適合遞迴處理; bottum-up 則是將待排序序列元素逐一處理,在適當的時機合併,適合非遞迴實作,commit b5c56e 屬於 bottom-up 的一種變形,也是逐一將元素讀入,差別在於合併的時機不同。
下表為 bottom-up 和 top-down 的性能較比較:
Case | Best Case | Average Case | Worst Case |
---|---|---|---|
Top-Down | 1 | 2N lg N - 0.146N | N lg N - 1.248N |
Bottom-Up | 1 | 2N lg N - 0.146N | N lg N - 0.965N |
雖然 bottom-up 的最差情況效能略輸 top-down , 但是 bottom-up 不需要預先知道序列長度,適合 link-list 實作的序列,這點使得它的實用性大於 top-down。
這篇文章主要介紹一種合併排序的變體稱為 Queue Mergesort ,使用佇列存放待合併序列,先將每個元素單獨作為一個待排序序列存放於佇列,之後不斷從頭部取出兩個進行合併後放到尾部,直到佇列中剩下一個序列即完成排序。
作者也證明這種方法是 optiml mergesort ,也就是對任何待排序元素個數 N ,最差情況下比較次數不比其他 mergesort 算法 演算法多
algorithm 是「演算法」,而「算法」是 the way you calculate,也就是你在國中小學數學測驗卷上的「計算過程」,二者不同。
當兩個要合併的序列長度比值是2的冪時,也就是使用 power-of-2 rules ,有機會使得整體的時間複雜度隨著 N 變大時線性成長,既使合併兩序列的複雜度是超線性,因此相較於 half-half rules ,使用 power-of-2 rules 可以在 N 很大的時候顯著降低運算時間,而在 commit b5c56e 中選用合併序列長度比值上限為 2 是因為不論 N 多少每一步合併都能限制在這個比值以下。
經過了上面的理解,我意識到自己之前實作 q_sort
的方法是多麼天真且愚蠢,因此我引入 lib/list_sort.c 的算法 演算法到 lab0-c (commit 9837691)。
過程中做了一些改寫,為了簡化實作,刪去了編譯器優化的部份__attribute__((nonnull())
, likely
和 unlikely
,還有以 strcmp
取代 cmp
函式,因此也刪減了有關函式的傳入參數 prev
, cmp
。