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
2023q1 Homework1 (lab0)
contributed by <
kart81604
>開發環境
完善 queue.c
q_new
回傳
NULL
的條件要加進去,要如何判別配置失敗。- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →q_free
這是一開始的想法,利用 indirect pointer
cur
來指向l->next
然後利用list_del
將該點獨立出來,再將它釋放,接著cur
再指向l->next
,直到l->next == l
最後再釋出l
的空間。但這樣的話,我每次釋出的都是

list_head
大小的空間,中間不包含任何資訊,對於一種儲存結構來說太弔詭了,於是我再次拜讀 你所不知道的 C 語言: linked list 和非連續記憶體 。看完這張圖意識到,佇列形式應為此圖表示的, Head 型別為
list_head
,而 Node 0, Node 1, Node 2 的型別為element_t
。element_t
的結構由char *value
與struct list_head list
組成,因此圖上 Node 中的int Data_A
、int Data_B
、int Data_C
替換成char *value
會更完整代表此題的形式。於是將程式碼更改為
使用
list_for_each_safe
走訪每個element_t
並進行q_release_element
做完之後只會剩下最開頭的list_head
,然後free(l)
,就完成了。q_insert_head
值得注意的是要將 input 中的
*s
複製到新配置的空間。考慮到執行
make valgrind
會發生插入失敗但有記憶體空間被分配而切沒有被釋放出去,發現原因是因為report.c
中有allocate_cnt
及free_cnt
參數,會隨著free
以及malloc
指令來增減, insert 分配順序為先分配new
再來是new_s
,要是分配new_s
失敗時,但沒有釋出new
已配置的空間,則會造成失敗。q_insert_tail
基本上就是照著
q_insert_head
的方法作,單純的把q_insert_head
中的第 9 行改成list_add_tail(&new->list, head)
。q_remove_head
偶然查詢到 [ 資料 ](https://skylinelimit.blogspot.com/2018/02/c-2.html),了解到使用 `strncpy` 來處理 buffer overflow 的問題。查閱 C 語言標準和 man page 這類第一手材料!
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →q_remove_tail
也是照著
q_remove_head
的方法作,只是把q_remove_head
中的第 5 行中的第一個參數改成head->prev
。思考進一步縮減程式碼的方式,善用前置處理器。
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →q_delete_mid
2 月 16 號晚上上課時,多虧老師的指點,利用 doubly-linked list 的特性,設置兩個 indirect pointer 為
forward
與back
,如命名,一個是往前走,另一個則是往後走,直到兩個指到同一點,或是back
在forward
後面,之後對forward
指到的位置進行list_entry
,找出包含forward
(forward
的型別為list_head
)的element_t
的位置,接著再進行
list_del_int
以及q_release_element
。之後重新審視程式碼,發現所有取用 indirect pointer 都有透過
*
來操作,就代表根本沒有必要使用 indirect pointer 來操作,這樣反而還使程式碼變更複雜,因此改成沒有使用 indirect pointer 的版本。q_delete_dup
以上為之前的想法,跑 test 會失敗,是因為疏忽了有出現重複的全部都要刪掉,以上程式碼會造成只有出現第二次的元素會被刪除,而導致結果錯誤。
而更改的結果如下。
善用
diff
,只列出變更的部分程式碼。- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →除了跟
q_delete_mid
一樣,不再使用 indirect pointer ,其餘與以上方法相似,只是多使用了一個參數count
來判斷該元素是否有出現重複,如果有的話,就在把那個元素刪除。q_swap
先紀錄
tmp
為cur
的下一個,再把cur
孤立出來。而第 10 ~ 13 行,把
cur
插進tmp
的後面。q_reverse
把 queue 中的每一項都進行
list_move
移到 queue 的第一項就完成了。q_reverseK
與上題類似的方法,每一段進行 k 次的
list_move
,再用個cur_head
紀錄等等誰要當新的 head 。q_sort
不用張貼完整程式碼,開發紀錄著重於你的想法、中間遭遇到的問題、分析和試驗等等。程式碼僅為輔助性質。
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →merge_two_list
設計這個
merge_two_list
是希望我的 input 是保留原本的 doubly-linked list 結構, output 也是 doubly-linked list 結構。其他 function 是把一開始的
head
僅視為 queue 的開頭,不包含資料的,而merge_two_list
的兩個 input 都是某個element_t
的list
也就是對 input 執行list_entry
是找的到其element_t
的位子的, output 也是同理,輸出的 queue 中的每個 head ,都是找得到其element_t
的位子,主要執行方式還是參考 你所不知道的C語言-Merger Sort 的實作 。因為 input 的結構,所以對 input 作。q_size
時,要多加上 1 ,才會是 queue 正確的長度而結束判定方式是使用哪個 queue 的長度先歸零。跳出迴圈的條件為判定是否node
所指或是他的下一個為head
。list_h
中的splice
功能是因為 input 的格式,所以只能自己寫上去。更正的目的是為了保證測試案例 14 能順利通過。
merge_sort
input 與 output 的格式與
merger_two_list
一樣,指得都是某個 queue 的開頭,但這個開頭也是某個element_t
的list
。值得一提的是這邊採用的是 do-while 的迴圈,處理 input 為長度為 2 的 queue 就不會出錯。
q_sort
了解
merge_two_sort
與merger_sort
,就知道一開始要先把 input 的 head 孤立出來,等做完排序後,再把他接上。q_descend
比較在意的問題是,題目描述是用 remove ,但如果沒有加入第 12 行的
q_relaese_element
會造成ERROR: Freed queue, but 4 blocks are still allocated
。文字訊息不要用螢幕截圖展現,尊重視障者閱讀的權益。
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →而加入之後就會正確執行了。
q_merge
重用了
q_sort
中使用的merge_two_list
,將chain
上每個 queue 的head
斷開,再與第一個 queue 進行merge_two_list
,之後再接上chain
上的第一個head
。更改 dudect
主要參考 willwillhi 的方法。
考慮測試案例 17 中,
q_insert_tail
與q_insert_head
都不能在常數時間內完成。測試案例和測試資料不同,前者是若干筆測試資料的集合。
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →作業要求有提到,
lab0-c
並沒有具備 percentile 的處理,參考 oreparaz/dudect 後,新增 percentile 功能,trace-17 已能通過,目前分數為100分。由於原始碼有使用結構
dudect_ctx_t
, lab0-c 則沒有,因此原始碼有些 input 裡有ttest_ctx_t *ctx
,在 lab0-c 會用到結構裡的那些參數,就要自己加進去。以下為 oreparaz/dudect 的原始碼中的一個 function 。
以下為 lab0-c 中的
fixture.c
中參考後的程式碼。將 lib/list_sort 引入至 lab0-c 專案
將 lib/list_sort.c 中函式放入
queue.c
。函式中的參數,
priv
表示是私密資料,這邊用不到,所以將其移除,cmp
是比較大小所需的函式,這邊改用以下的方式代替,因此也不需要此參數。移除不需要的 callback
在
qtest.c
加入新命令藉由
console.h
中可以知道會呼叫
do_list_sort
這個函式,因此我們要在qtest.c
新增do_list_sort
函式這個函式的內容與原本的
do_sort
幾乎一模一樣,差別只有差在do_sort
執行q_sort
,而do_list_sort
執行list_sort
。由上可知,我們在
qtest.c
會執行list_sort
指令,因此要先宣告,原本是在queue.h
宣告,但在 git commit 時會發出錯誤,系統表示不允許更改list.h
以及queue.h
,因此雖然在queue.c
引入 list_sort ,但qtest.c
只會#include <queue.h>
,沒有先行宣告的話, compile 階段就不會過,解決方法為在#include <queue.h>
下一行手動加入宣告。(在執行 list_sort 之前加入其實就可以)測試
將
qtest.c
裡的do_sort
稍作更改,來確認是否能正確執行。儲存後執行以下指令。
所得分數為 100 , 代表此方法為正確的排序。
與自行實做的 sort 進行比較
兩者都使用以下指令來測試性能
在使用 perf 來觀察差異。
但這樣兩者對不同的 queue 進行排序,考慮到公平性,對同一個queue排列是最好的,因此在
qtest.c
中新加入兩條命令,分別是write_in
及write_out
,前者是將data.txt
中的資料加入當前的 queue 中,後者則是將目前的 queue 的資料寫進data.txt
裡面。先執行以下指令,將隨機 300000 筆資料寫進
data.txt
裡。這時候
data.txt
已被寫進了密密麻麻的資料,就可以來進行比較了。執行以下指令
以下為不同 sort 的效能分析。
新增 shuffle 命令
透過閱讀 Fisher–Yates shuffle 演算法, shuffle 的原理如下圖所示。
設一開始資料如下,長度為 9 的陣列。
隨機選擇 1 ~ 9 中隨機一個數
roll
,以及最後一項cur
。此例
cur = 4
(陣列第一個位置為 1 )。roll
與cur
交換位子。之後在從 1 ~ 8 中選擇一個數
roll
,以及還未換過得cur
,以此類推,直到cur
指向陣列的開頭,這樣下來就會得到與之前不同排列的陣列。(如果某一輪roll
恰好等於cur
則不交換,進到下一輪)以下為實做的程式碼。
之後再加進命令裡,作法與之前加入新命令的方法一致,就不多作贅述。
以下是測試是否會得到與之前不同的 queue 。
測試可得與之前不同排列的 queue 。