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
2024q1 Homework1 (lab0)
contributed by <
padaray
>開發環境
佇列實作和程式碼改進
q_new
建立新的「空」佇列
我們需要用
malloc
配置list_head
空間,並且使用list.h
檔案的INIT_LIST_HEAD
函式,讓 head 指向 head 本身避免非必要的項目縮排 (即
*
),用清晰、明確,和流暢的漢語書寫。q_free
釋放佇列所佔用的記憶體
使用
list.h
中的list_for_each_safe
函式,在 for 迴圈中呼叫list_entry
取得完整element_t
,當entry->value
不為空則 free,接下來 free 整個element_t
。for 迴圈結束時 free head程式碼改進:
command 的翻譯是「命令」,而非「指令」(instruction)
執行 make check 命令時回報以上錯誤,原因是在初始化
list_for_each_safe
函式的參數時,事先分配空間,造成不必要的記憶體空間配置,程式碼修改如下:q_insert_head
在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
malloc
一個element_t
大小的空間給新加入的節點new_node
,使用strdup
函式複製一個參數 char s 的副本給new_node->value
,最後呼叫list.h
中的list_add
函式傳入new_node
程式碼改進:
最一開始沒有為傳入參數s建立副本,直接使用造成重複存取錯誤,因此修改為以下版本:
最後發現使用
strdup
即可完成上述須求,因此修改為以下版本:q_insert_tail
在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
與
q_insert_head
的做法大致相同,差別在於呼叫list.h
中的list_add_tail
函式傳入new_node
q_remove_head
在佇列開頭 (head) 移去 (remove) 給定的節點
使用
list.h
中的list_first_entry
函式回傳第一個節點的完整element_t
,呼叫list_del
函式,斷開第一個節點與佇列,使用strncpy
函式複製element_t->value
到參數sp
,回傳element_t
q_remove_tail
在佇列尾端 (tail) 移去 (remove) 給定的節點
與
q_remove_head
的做法大致相同,差別在於呼叫list.h
中的list_last_entry
取得最後一個節點TODO: 提高程式碼的可重用程度。
q_size
計算目前佇列的節點總量
初始化
count
變數為 0,呼叫list.h
中的list_for_each
函式,在 for 迴圈中執行count++
,最後回傳變數count
q_delete_mid
移走佇列中間的節點。Leetcode 2095
根據 Dictionary.com 的解釋: (作為及物動詞和不及物動詞都有類似的意思,以下列出作為及物動詞的寓意)
其實這意思很好懂,就像我們「走過」/「穿越」校園一般,於是 traverse a linked list 就會是「(用某種手段) 存取多個鏈結串列的節點」,但這裡卻沒有必要「所有」的範圍:英語的 "move over/through" 用於某個區域時,根本沒有這樣的隱含意義。如果將 traverse 翻譯為「遍歷」,就會導致「超譯」,也就是跳脫「直譯」和「意譯」。
當我們回頭看 "traverse" 所在的技術描述內容,例如 "traverse every node",若翻譯為「遍歷每個節點」,那麼既然都「遍」(意即「全面」、「到處」),又何來「每個」節點呢?於是,合理的翻譯應改為「逐一走訪每個節點」 —— 差異在哪?在 "traverse every node" 的應用場景中,可能是我們嘗試在鏈結串列尋找特定的節點內含的資料,一旦找到就停止,或者我們要偵測給定的鏈結串列是否包含環狀 (circular) 結構 ,並沒有真的要「遍」(到處/全面)「歷」(意即「經過」) 每個節點。在我們的用語中,要區分「意圖」(intention) 和「實際作用」(reaction),濫用「遍歷」會使得語意不清,從而難以推測英語原文的訴求。
還有個更重要的原因是,「遍歷」這詞已在理工領域存在,且廣泛使用,即「遍歷理論」(Ergodic theory),後者是研究具有不變測度 (invariant measure) 的動力系統及其相關問題的一個數學分支。 遍歷理論研究遍歷變換,由試圖證明統計物理中的遍歷假設 (Ergodic hypothesis) 演進而來。
在統計學中,若單一個物理系統在不同時間內重複相同的實驗 (如丟擲一枚硬幣),其取樣數據所得的統計結果 (如硬幣出現正面的機率) 和極多個完全相同的物理系統的系集 (如丟極多個相同的硬幣) 在同時作相同的實驗取樣數據的統計結果假設為相同時,此種假設即稱為「遍歷性假設」或「遍歷假設」。基於這個假設,對時間平均的統計方式及結果,便可由對系集的平均及統計方式得到。在一般物理系統中,尤其在統計力學範圖中,均採用此遍歷性假設為基本的假設。在流體力學中對亂流的實驗分析,亦是採用此假設。
遍歷 (Ergodic) 源於以下二個希臘詞:
最初這是由奧地利物理學家波茲曼 (Ludwig Boltzmann) 於統計力學領域 (statistical mechanics) 提出的概念,其一廣為人知的結果是:在經過長時間後,時間平均將會趨近空間平均。此事實在動力系統扮演極重要的角色,在隨機分析領域亦然。
因此,若貿然將 traverse 翻譯為「遍歷」,一來語意不清,二來增加和理工多項領域專業人員的溝通成本,實在得不償失。
\(\to\) 資訊科技詞彙翻譯
宣告兩個
list_head
指標front
和back
,指標front
從第一個節點向後遍歷,指標back
從最後一個節點向前遍歷,當兩個指標指向同一個節點,或是指標front
的前一個節點是指標back
所指向的節點,跳出 while 迴圈,呼叫list_del
將front
所指向的節點從佇列中刪除q_delete_dup
在已經排序的狀況,移走佇列中具備重複內容的節點。Leetcode 82
初始化
flag
變數為 false,使用list.h
中的list_for_each_entry_safe
函式,逐一走訪每個節點,確認當前節點的value
是否和下一個節點的value
相同,若是相同則 free 當前節點,同時修改flag
為 true,最後一個重複節點雖和下個節點不相同,仍然會因flag
為 true 刪除節點q_swap
q_reverse
以反向順序重新排列鏈結串列,該函式不該配置或釋放任何鏈結串列節點,換言之,它只能重排已經存在的節點
使用
list_for_each_safe
函式,逐一走訪每個節點,對當前的節點使用list_move
函式,使其到佇列的最前方,走訪完後即可完成 reverseq_reverseK
類似
q_reverse
,但指定每 k 個節點為一組,進行反向順序排列。Leetcode 25新增兩個暫存佇列
tmp
、tmp_rev
,tmp
儲存 k 個變數後,執行q_reverse
函式,將儲存的變數反向重新排列,呼叫list_splice_tail_init
函式將佇列tmp
插入tmp_rev
尾端,若剩餘的節點少於 k ,呼叫list_splice
函式,將佇列tmp_rev
插入 head 前方程式碼改進:
使用精準的詞彙。
雖然兩種撰寫方式是
同義的,但是若使用刪掉部份的程式碼,測試時會讓佇列清空,目前還沒找到原因q_sort
以遞增順序來排序鏈結串列的節點,可參閱 Linked List Sort 得知實作手法
排序演算法選擇 Merge Sort,使用快慢指標的方式,讓兩個指標
slow
和fast
分別指向中間的節點和最後的節點,呼叫list_cut_position
函式,將佇列分為 head 到 slow,slow->next 到 fast,達成將佇列切成兩段的效果以遞迴的方式呼叫
q_sort
函式,當每個佇列剩下一個節點,使用q_merge_two_list
函式,將每個佇列排序且合併q_ascend
參閱 Leetcode 2487
呼叫
list_last_entry
函式取得佇列最後一個 entry ,比較最後一個 entrycur_entry
和倒數第二個 entrycomp_entry
條件一:
若 comp_entry 小於 cur_entry ,刪除 comp_entry
條件二:
若 comp_entry 大於 cur_entry ,cur_entry = comp_entry
q_descend
Chris Beams 在 How to Write a Git Commit Message 一文 (繁體中文翻譯: 如何寫一個 Git Commit Message) 提出,好的 Git commit message 應符合七條規則:
你沒有依循上述規範,請詳讀作業說明,以
git rebase -i
改正。參閱 Leetcode - 2487
呼叫
list_last_entry
函式取得佇列最後一個 entry ,比較最後一個 entrycur_entry
和倒數第二個 entrycomp_entry
條件一:
若 comp_entry 大於 cur_entry ,刪除 comp_entry
條件二:
若 comp_entry 小於 cur_entry ,cur_entry = comp_entry
q_merge
合併所有已排序的佇列,並合而為一個新的已排序佇列。LeetCode 23
實作方式:
在 qtest 提供新的命令
shuffle
以 Fisher–Yates shuffle 的方式實作洗牌演算法,以下為程式碼實作:
撰寫
shuffle
測試檔testShuffle.py
檔,複製教材所提供的 測試程式碼qtest.c
程式碼testShuffle.py
檔驗證
shuffle
1. 計算 Chi-square test statistic \(X^2 = \Sigma_{i=1}^n \frac{(O_i - E_i)^2}{E_i}\)
測試程式碼 中的串列有四個節點,共有 4!種排列組合,以亂數打亂 1000000 次後,每種排列的出現次數期望次數為 41666,Chi-square 是18.113。以下為結果:
2. 決定自由度
自由度的計算為 N 個隨機樣本減去 1,四個節點的隨機樣本數是 24,因此自由度為 23
3. 選擇顯著水準
顯著水準 α 代表在虛無假說為真下,型一錯誤發生之機率。
α = P(拒絕 | 為真),α 設定為 0.05
透過卡方分布表知道自由度 23,chi-square 18.113,P value 介於 0.25 和 0.5 之間
4. 統計檢定的結果不拒絕虛無假說

P value 大於 α,因此無法推翻虛無假說「shuffle 的結果發生的機率相同,遵守 Uniform distribution」
以 Massif 分析記憶體使用量
--tool=massif
產生 massif 檔執行命令後可在 lab0-c 資料夾中產生
massif.out.xxxx
檔安裝 massif-visualizer 插件,以視覺化工具查看記憶體使用狀況
massif.out.xxxx
檔研讀 Linux 核心原始程式碼的 lib/list_sort.c
程式碼
list_sort.c 所實作的排序演算法為 merge sort,程式碼分為三個函式,以下個別進行講解:
1. merge
此函式的功能為將串列 a,b 進行合併。合併的方式為若 a 的節點 <= b 的節點,則將 a 的節點放入串列 head 內; 若 a 的節點 > b 的節點,則將 b 的節點放入串列 head 內,最後回傳串列 head。
透過註解了解,此函式用在 merge sort 兩兩合併時所用,但並不是用來在生成最終 merge sort 的結果,因此不用實作 "prev" 來變成雙向鏈結串列
圖解實作方式如下:
若 a <= b:
程式碼理解
第 19 行宣告一個指標的指標
tail
,並將其指向head
,原因是可以透過更新tail
指向的位址,增加鏈節串列head
的節點,使head
指向的位址不用更動,最後直接回傳此串列即可。第 23 行的 <= 為此實作方式是 stable sort 的原因,因為 = 代表 a,b 兩個串列內的值相同,若是值相同的情況下,會將 a 的節點放入
head
中,而不是 b 的節點,以此達到 stable2. merge_final
此函式的功能是,當剩下最後兩個串列要進行合併時,才會使用此函式,並且會將串列恢復成雙向鏈節串列。註解中提到,實作兩個 merge 函式的原因是,在合併過程中不用維護 prev 會讓程式執行更快
圖解實作方式如下:
若 a <= b:
tail = a:
重複以上操作
程式碼理解
這段程式碼是當合併兩個串列時,其中一個串列已經為空,將剩下的串列直接放入
head
內,並且讓該串列變回雙向鍊結串列unlikely函式
第89行
likely
和unlikely
函式為 linux kernel 的巨集,被定義在 /include/linux/compiler.h 中,程式碼如下:_built_expect
是gcc的內建function,__builtin_expect((x),1)
的意思是 x 為真的機率較大,反之為假的機率較大。兩個 ! 運算符號的原因是,將輸入的參數 x 變為 0 或 1,因為本來 x 可以為非 0 整數。總結來說,使用likely
函式 assembly code 會提前執行發生機率較大的程式碼資料來源
3. list_sort( 主程式 )
這段註解描述,要進行合併的兩個 sublists,至少要維持著 2 :1 的大小比例,才能讓效能比較好,我們只需要注意 cache 大小是否低於 \(3 * 2^k\),即可避免發生 cache thrashing*,
cache thrashing 解釋:在低關聯度的 cache 中,若有兩個以上要取得的記憶體位置,它們需要用到的 cache line 相同,在輪流存取的過程中,就會一直發生 cache miss
合併機制
初始化變數
count
,當pending
中的節點數增加,count + 1
,當count
是 \(2^k\) 時不進行合併,反之則合併程式碼理解
第 219 行的 for 迴圈是為了找到
count
的 least significant clear bit,第 222 行判斷 bit 是否為 1,如果是的話進行 merge,之後將 list 的節點移到 pending 中。重複上述動作直到 list 清空。上面的程式碼在做的是將 pending 中的節點放到 list 中,並且做合併。
總結就是 214~237 行是將單個節點合併成部分排序的子串列,239~251 行是將這些子串列進一步合併成最後排序好的鏈結串列。