contributed by < aa860630
>
allenlial666
q_swap
可以使用 list_move 簡化程式碼。$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Vendor ID: GenuineIntel
Model name: 11th Gen Intel(R) Core(TM) i5-11300H @ 3.10GHz
CPU family: 6
Model: 140
Thread(s) per core: 1
Core(s) per socket: 4
q_new
在任何佇列操作前都需要一個 head 當作引數傳入,因此我們需要先 malloc 一個記憶體區塊並將其雙向鏈結(prev 和 next)都指向自己,用以之後操作空的佇列。
「空」(empty) 的佇列是指向有效結構,開頭 (head) 的值為 NULL。
在每次 malloc 時都須確認配置記憶體區塊是否成功,使用以下程式碼做確認。
struct list_head *head = malloc(sizeof(struct list_head));
+ if (!head)
+ return NULL;
輸入 ./qtest
後進行操作
cmd> new
l = []
q_free
commit 39ea8d0
填入自己帳號對應的 git commit 超連結,例如 https://github.com/aa860630/lab0-c/commit/c3fce364112666dac1d66cd916e040e29fa3b829
q_free()
用以釋放佇列在記憶體的空間,包括 head 及每個 entry 的 value 跟 list,資料型別如下
typedef struct {
char *value;
struct list_head list;
} element_t;
在刪除每個節點的同時必須記得下一個刪除的物件,這裡透過 list_for_each_entry_safe (node, safe, l, list)
可以利用 safe 去記錄下一個被刪除的節點
輸入./qtest
後進行操作
l = [a b c]
cmd> free
l = NULL
q_insert_head()
在佇列的第一個位置插入新的節點,在 malloc 一個 element_t 之後一樣要確認記憶體空間是否被創造,確認方法如下
element_t *new_node = malloc(sizeof(element_t))
+ if (!new_node)
+ return false;
透過 list_add(&new_node->list, head)
可以直接將 new_node 插入在第一個位置,但由於其形態為 element_t,因此要將指標位置改為指向 new_node 的 list
兩個 function 的操作方法一致,差別只在於插入位置
避免過多的中英文混用,已有明確翻譯詞彙者,例如「鏈結串列」(linked list) 和「佇列」(queue),就使用該中文詞彙,英文則留給變數名稱、人名,或者缺乏通用翻譯詞彙的場景。
輸入./qtest
後進行操作
l = []
cmd> ih a
l = [a]
cmd> ih b
l = [b a]
q_remove_head()
用來 pop 佇列的第一個節點,可以透過 list_del_init()
來移除 head 的下一個節點,但無法同時移除該節點的 value,因此需要以下程式碼來完整 pop 整個節點
if (sp) {
strncpy(sp, node->value, bufsize);
strcat(sp, "\0");
}
將 node->value
的字串複製到由指標 sp 指向的空間,空間大小為 bufsize,記得在字串後方加入"\0"
,才能知道字串結束位置
兩個 function 的操作方法一致,差別只在於 pop 節點的位置
輸入./qtest
後進行操作
l = [a b c]
cmd> rh
Removed a from queue
l = [b c]
cmd> rh
Removed b from queue
l = [c]
用作刪除佇列中重複的字串,詳情見Remove Duplicates from sorted list II
段落中的程式碼標注,使用 1 個 backtick,而非 3 個。
利用 list_for_each_entry_safe (cur, safe, head, list)
去比較 cur
與 safe
是否一樣。若不一樣,則雙雙移至下個節點,若一樣,則將 cur
刪除,並將布林常數 cmp
改為 1,雙雙移至下個節點
if (cmp == 1) {
list_del_init(&cur->list);
free(cur->value);
free(cur);
}
由上述程式碼可知當cmp
為 1 時,無論比較結果為何都需刪除當前節點,確保刪除連續重複字串的最後一個字串。
輸入./qtest後進行操作
l = [a b b c c c d]
cmd> dedup
l = [a d]
commit c3cef8f
將佇列中兩兩節點進行反轉,詳情見 Swap Nodes in Pairs
無論標題和內文中,中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
輸入./qtest後進行操作
l = [b a d c e]
cmd> swap
l = [a b c d e]
commit a371b33
將整個佇列做反轉
輸入./qtest後進行操作
l = [a b c d e]
cmd> reverse
l = [e d c b a]
commit 72bd7b4
佇列根據引數k為一個單位進行反轉,詳情見Reverse Node In K-Group
使用q_size
可知佇列長度,比較 len 與 k 的大小,若 len >= k 就進行反轉(呼叫副函式 q_reverse()
),否則不做任何操作,在反轉後都會將 len - k,直到 len < k
len = q_size(head);
while (len >= k) {
...
len = len - k;
}
輸入./qtest後進行操作
l = [a b c d e f g]
cmd> reverseK 2
l = [b a d c f e g]
cmd> reverseK 3
l = [d a b e f c g]
commit c3cef8f
將佇列做排序,在嘗試過 Bubble Sort 後,由於其時間複雜度為 O(n2),不符合系統預計時間,因此以下使用時間複雜度為 O(n\log{n})的 Merge Sort
將 Merge Sort 分為兩個步驟
mergeSortList
:利用 slow 指標與 fast指標將佇列拆成兩個等長的佇列,用地回呼叫的方式反覆執行上述動作直至佇列無法再被分割while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
merge
:兩兩佇列利用strcmp
去比較字串大小並由小排到大,反覆執行直至合併成原先佇列大小使用 Graphviz 重新製圖,並嵌入到 HackMD 筆記中。
參考文件來自Linked List Sort
在做合併的同時,由於每個佇列已排序,因此當其中一個佇列為空時,只要把另一個佇列剩餘部分接回正在合併的佇列即可
if (t1->next == t1) {
list_splice_tail(&tmp2, &new_queue);
} else if (t2->next == t2) {
list_splice_tail(&tmp1, &new_queue);
輸入./qtest後進行操作
cmd> ih RAND 4
l = [ndqavs pmdkzpsti dmectanx coowpn]
cmd> sort
l = [coowpn dmectanx ndqavs pmdkzpsti]
commit a96cac6
你如何確保目前的測試已涵蓋排序演算法的最差狀況?
q_descend
的功能為在不移動節點的情況下將佇列從最大排到小,過程中勢必會刪除掉一些節點,並回傳佇列剩餘節點數,詳情見Remove Nodes From Linked List
兩個 function 的操作方法一致,差別只在於由小到大或由大到小
輸入./qtest
後進行操作
l = [f c d a b]
cmd> descend
l = [f d b]
將不同佇列,按照順序合併回一個佇列,詳情見Merge k Sorted Lists
特別需要注意的是,此處使用的資料型別為queue_contex_t
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
commit e759807
在qtest.c
裡並沒有可執行 "shuffle" 的指令,為此我們可以新增一個名為 "shuffle" 的命令,同時附上指令說明
ADD_COMMAND(shuffle, "Shuffle the queue","");
在同個檔案下新增一個名為do_shuffle
的 function,在使用者輸入shuffle
命令的同時呼叫do_shuffle
利用 Fisher–Yates shuffle 演算法來實作洗牌(shuffle)
for (tail = head->prev; tail != head; tail = tail->prev, len--) {
rnd = head->next;
int j = rand() % (len);
for (int k = 0; k < j; k++) {
rnd = rnd->next;
}
if (tail == rnd) {
continue;
}
tmp = rnd->prev;
list_move(rnd, tail);
list_move(tail, tmp);
tail = rnd;
}
執行 lab0-d 提供的腳本後,輸出結果如下:
$ ./scripts/shuffle.py
Expectation: 41666
Observation: {'1234': 41525, '1243': 41663,'1324': 41579,
'1342': 41841, '1423': 41658,'1432': 41388,'2134': 41665,
'2143': 41717,'2314': 41754, '2341': 41622, '2413': 41814,
'2431': 41890, '3124': 41731, '3142': 41295, '3214': 41560,
'3241': 41845, '3412': 41551, '3421': 41440, '4123': 41516,
'4132': 41858, '4213': 41659, '4231': 41712, '4312': 41493,
'4321': 42224}
chi square sum: 20.929774876398024
為了測試洗牌是否足夠隨機,我們透過使用佇列中的4個節點 (l = [1 2 3 4]) 去做測試。在做了\(10^6\)次發牌,由於出現的可能為 \(4!\),因此可得期望值\(E = 41666 (= 10^6 / 24)\),chi square sum \(X^2 = 20.929774\)
在list_sort
函示開始前可見一行指令__attribute__((nonnull(2,3)))
,避免參數head
或cmp
為NULL
指標。__attribute__
其實是GCC的一種編譯器指令,當其設定為函數屬性時,可以使編譯器在錯誤檢查方面增強
參考自GNU GCC compiler()
__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp){}
將head->prev
的next
指向NULL
,也就是最後一個節點指向NULL
,若只觀察next
方向的串列,從原先的環狀鏈結串列變成了單向鏈結串列
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
list sort 在做合併時,兩個要被合併的 sublist必須是 \(2^{k+1}\):\(2^k\) ( 2 : 1 ) 的平衡狀態,並使用二進制的count
作為合併與否的依據
上述例子來自 yinghuaxia
在 while 迴圈裡看到的 for 迴圈用來尋找count
中的least-significant clear bit,藉此將tail
移到待合併的位置上,當bits
不為 0 時,sublist 進行排序合併
if (likely(bits)) {}
用以判斷count
是否為2的冪,若為2的冪,則bits
早在 for 迴圈時就被改成0,不會進行合併; 若不為2的冪,bits
不為0,則會進行排序合併
do {
size_t bits;
struct list_head **tail = &pending;
/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
/* Do the indicated merge */
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
}
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
} while (list);
其中likely
與unlikely
用在提升程式碼運行效率,這兩個巨集被定義在 /include/linux/compiler.h ,按照__builtin_expect
的定義,要用第一個參數和第二個參數比較,它期望的值是true。第二個值是1。這裏的!!(x)就是為了保證當x本身作為邏輯值為true的時候,其!!(x)值為1
# ifndef likely
# define likely(x) (__branch_check__(x, 1, __builtin_constant_p(x)))
# endif
#define __branch_check__(x, expect, is_constant) ({ \
long ______r; \
static struct ftrace_likely_data \
__aligned(4) \
__section("_ftrace_annotated_branch") \
______f = { \
.data.func = __func__, \
.data.file = __FILE__, \
.data.line = __LINE__, \
}; \
______r = __builtin_expect(!!(x), expect); \
ftrace_likely_update(&______f, ______r, \
expect, is_constant); \
______r; \
})
在一些明確的條件下,我們比編譯器更了解哪個分支更有可能發生,gcc 在編譯時會在程式引導下調整 if 分支內程式碼的位置,如果是likely
修飾過的就調整到前面,因此可以節省跳轉指令帶來的時間開銷
使用 perf 進行效能比較,參考至GNU/Linux 開發工具
perf stat --repeat 5 -e instructions,cycles ./qtest -f traces/trace-sort.cmd
定義測資
option fail 0
option malloc 0
new
ih RAND 500000
time
<sort>
time
比較 q_sort
與 list_sort
這兩個排序的 system time(s),測試資料筆數分別為10萬筆、50萬筆、100萬筆跟500萬筆資料,如下表所示 :
資料數 | q_sort | list_sort |
---|---|---|
100,000 | 0.035 | 0.027 |
500,000 | 0.111 | 0.116 |
1,000,000 | 0.226 | 0.240 |
5,000,000 | 0.654 | 0.653 |
比較 q_sort
與 list_sort
這兩個排序的效能差別,測試資料筆數為10 萬筆
項目 | q_sort | list_sort |
---|---|---|
cache-misses | 78,5773 | 78,9353 |
cache-references | 114,0532 | 114,5490 |
% of all caches refs | 68.90% | 68.91% |
instructions | 3,7345,3621 | 3,7352,0238 |
cycles | 1,8751,4000 | 1,8724,0725 |
insn per cycle | 1.99 | 1.99 |
duration time | 0.035 s | 0.027 s |