or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
2024-02-{20,27} 問答簡記
不同長度的 linked list 是否可以合併?
從 案例探討: LeetCode 21. Merge Two Sorted Lists 延伸,我們將討論文中程式碼對不同長度的單向鏈結串列可否做合併?可以的話怎麼做到的?
回顧 C99 規格書(ISO/IEC 9899:TC3)
6.5.13 Logical AND operator
這邊要注意的是經由 && 邏輯運算子後,得到的型態是 int
6.8.5 Iteration statements
C99規格書中描述 controlling expression 的限制為
這邊 scalar type 根據 C99 6.2.5 Type 第 21 項 (page 36) 定義為
而 Arithmetic types 在同個 section 下,第 18 項定義為
有意思的是在C++11規格書中, 5.14 Logical AND operator 下的規定是
bool
型態可以看到文中
mergeTwoLists(*L1, *L2)
輸入只有兩個ListNode
結構體的指標。而內部實作的部分則由while(L1 && L2)
實踐,所以當兩者皆非 null pointer 時,比較完大小順序就可以將兩者合併。考慮其控制表達式的否命題即為:
說明停止條件為 L1 或是 L2 指向 null。兩者同時指向 null 的情形只會發生在傳入函式的 L1 和 L2 皆是 null pointer 。
以下圖例簡易說明兩不同長度的單向串列是如何合併的,
L1=[4, 5]
,L2=[1, 6, 7]
,ptr
就像針線的針,會依據節點數值大小把針頭(指標)穿過比較後的節點:比較 L1 和 L2 大小。
ptr->next
指向 4 ,ptr
串接後的數列為[4]
比較 L1 和 L2 大小。
ptr->next
指向 5 ,ptr
串接後的數列為[4, 5]
跳出迴圈,判斷
ptr->next
該接到哪裡。由於 L1 目前為 null ,ptr->next
指向 L2 串接後的數列為[4, 5, 1, 6, 7]
合併完成。能否使用 linked list 去實作 quicksort
針對 Linux 核心的場景,強調是否可以達成 in-place algorithm
何時用到 bubble sort 或 insertion sort?
Linus 提到的 bad taste
The mind behind Linux | Linus Torvalds | TED 中的程式碼為何是 bad taste?
head
為null
。排序程式碼練習
考慮以下程式碼,使用 list.h
為什麼不用在環狀鏈結串列中使用 swap 就可以做到交換?
最簡單實作的 swap 如下:
可以看到上述的部分需要額外一個變數
tmp
來暫存交換的值。而在單向鏈結串列中,不用做到額外變數,只要使用間接指標( indirect pointer )。參見你所不知道的 C 語言: linked list 和非連續記憶體——Merge Sort 的實作:
merge sort 實作何處可用
list_splice
?Timsort 什麼時候用到
list_splice
?在 Python 官方文件中 listsort.txt 紀錄這個由 Peters, Tim 開發的 Timsort 跟實驗內容,以下摘入自開頭片段:
在 Timsort 中,討論的基本單位稱作為 run ,為一非遞減或是嚴格遞減的數列。例如:
可以拆解成兩個 run:
而向上述原始數列就已經有排序的子數列,這些子數列稱作為 natural run ,而其餘沒有排序過的元素,會先蒐集起來至一定數量後,藉由插入排序( insert sort )來排序成為一個 run 。同時為避免比較次數過多, Tim 在實作的過程中有限制每個 run 的上限為 64。
在過往學員 yanjiew1 紀錄中,詳述 Timsort 流程。
回頭來看
list_splice(*list, *head)
,由兩個輸入組成*list
跟*head
,兩者皆是list_head
結構體的指標,作用為將list
這個節點包含其後續節點,繫( splice )於head
之後。所以在進行合併各個 run 的過程中,list_splice
就在此時上場。在 Linux list_sort.c 中合併的實踐是由
*merge(void *priv, list_cmp_func_t cmp, struct list_head *a, struct list_head *b)
達成。由於並非環狀鏈結串列的合併,跟我們預期list_splice
的運作不一樣,list_splice
針對環狀結構操作。注意:在此的
*a
和*b
為 null-terminated singly-linked list 。詳見原始碼中list_sort()
的部分。在
merge_final()
部分中,則還原了原本串列的環狀結構。在函數的一開始先把單向串列改成雙向串列
函式的最後將雙向串列頭尾相連形成環狀結構
整個過程簡化的話,就是
list_splice
的功能。lib/list_sort.c
為何
list.h
選定 0x00100100 與 0x00200200 作為無效的地址?我在做
git log | grep <address>
之類的操作後依然沒有詳細說明。只知道該 address 第一次出現是在 commit9a69abf80edf2ea0dac058cab156879d29362788
"menuconfig: Add "breadcrumbs" navigation aid" 的位置linux/poison.h 的註解:
當
list_del
執行時,會將節點的的 prev 和 next 指向一個特定的地址,當存取到該地址時,會觸發 page fault。在《Linux Device Drivers 3/e》第四章 Debugging Techniques 的引言提到,Linux 核心的程式碼不易在除錯器中運作、錯誤也不易重現,不過一旦引發錯誤時,可能會讓整個系統崩潰,而造成錯誤的證據則隨之消失。
除錯的的其一手法就是將這種有毒 (poison) 的值設在使用前後,當該數值變更時,我們就會知道非預期的狀況發生。
有了這樣的設計,我們便可在除錯時知道 : 若
node->next
與node->prev
分別指向LIST_POISON1
與LIST_POISON2
的話,就代表發生 use-after-free 的情況,像是 lib/list_debug.c 便是 Linux 核心中對應的除錯程式碼。若無
LIST_POISONING
的設計,在list_del()
時將node->next
和node->prev
都指向 NULL,除錯階段就無法得知此時的 NULL 代表的是 uninitialized 抑或被釋放後才指派的。至於不直接釋放節點的原因,可參閱 Kernel Self-Protection 中 Memory poisoning 的部份得知:
2024q1 第 2 週測驗題第 1 題
建立二元樹需要有透過得知中序(in-order)與前序 (pre-order) 或是後序 (post-order)才能具體說明一個獨一無二的二元樹的原因說明舉例如下。
前序是
[A B C]
透過前序知道
A
是 中間的那個點,但卻無法透過前序知道B
C
相對於A的左邊還是右邊。因此產生的二元樹可能如下中序分別是
[B C A]
,[B A C]
,[A B C]
第一個樹:由中序知道
A
是 中間的那個點,B
C
相對於A
在左邊。所以都在A
的左子樹中。第二個樹:由中序知道
A
是 中間的那個點,B
相對於A
在左邊,所以在A
的左子樹中。C
相對於A
在右邊,所以在A
的右子樹中。第三個樹:由中序知道
A
是 中間的那個點,B
C
相對於A
在右邊。所以都在A
的右子樹中。所以 DFS 中的實作是透過 preorder 會藉由
find
找到preorder[pre_low]
在inorder
中的位置idx
。由圖得知在
idx
左邊的都會被放到左子樹,在idx
右邊的都會被放到右子樹。因此對應到左子樹的在中序涵蓋的範圍 :
[in_low,idx-1]
,右子樹在中序涵蓋的範圍 :[idx+1,in_high]
而觀察剛剛的前序可以知道他的分佈的規則就是
[中點 左子樹 右子樹]
,從這裡就可以看到只要知道左子樹有多少個,右子樹有多少個,就可以知道在前序的範圍了。而因為
pre_low
是中點左子樹在前序的涵蓋範圍 :
[pre_low + 1, pre_low + (idx - in_low)]
其實就是pre_low
往後左子樹的在中序涵蓋的範圍 :[in_low,idx-1]
右子樹在前序的涵蓋範圍 :
[pre_high - (in_high - idx - 1), pre_high]
其實就是pre_high
往前右子樹的在中序涵蓋的範圍 :[idx+1,in_high]
也因此從這樣的分析其實知道如果題目提供的只有後序與中序,我只要從後序的最後一個往前讀。
改變範圍即可因為後序的分佈是
[左子樹 右子樹 中點]
,post_high
是中點。所以左子樹在後序的涵蓋範圍:
[post_low, post_low + (idx - 1 - in_low)]
右子樹在後序的涵蓋範圍:
[post_high - 1 - (in_high - (idx+1)) , post_high-1]
所以這樣也就明白中序在建立二元樹中缺一不可的角色,而前序與後序則是可以只挑其中一個。
而
find
函式則是用 hash table 去紀錄in-order
的位置而已,可換成其他資料結構來實作。