contributed by < yu-hisennn
>
yy214123
你的 q_delete_mid
以快慢指標的策略進行實作,為找出串列的中間節點:
快指標須走訪 次
慢指標須走訪 次
總共 次
考慮到使用的資料結構為雙向環狀鍊結串列,可改以下方方式實作:
僅走訪 次即可找到串列之中間節點。
無論標題和內文中,中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
在實作過程中,發現有些程式碼已經在 list.h
檔中實作出來了,所以直接呼叫即可,這樣一來可以讓程式碼更精簡,可讀性也會有所提昇,像是︰
上述 diff 的內容,應該以 git diff
或 diff 命令產生,注意修改行數的位移量。
或是直接呼叫之前寫好的 q_insert_head
同理,q_remove_tail也可以呼叫之前寫好的 q_remove_head
commit 7ab86a7
避免非必要的項目縮排 (即 *
和 -
),以清晰、明確,且流暢的漢語書寫。
原本利用 strdup
的方式來實作,測試時發現會報出 ERROR: Probably not constant time or wrong implementation
的錯誤,於似乎就去確認 strdup
的實作方式,發現可能是因為多次呼叫需要跑遍整條字串長度的函式而造成的,於是就先把它改成自行宣告的作法。
第一次修改時,沒有使用一個變數來紀錄 strlen(n)
的回傳值,而是要用時才作呼叫,結果也會發生 ERROR: Probably not constant time or wrong implementation
,最後利用一個變數來紀錄避免多次呼叫 strlen(n)
來降低整體的時間複雜度。
slow
即為整條鏈結串列的中點。commit 488930d
commit db89b47
先判斷目前的值與下一個的值是不是重複的,重複的話就將下一個值給刪除,並且用一個旗標來紀錄目前的值有出現重複的情形,最後再將其刪除即可。
commit 504c744
list_move
的方式來實作commit 47abac9
q_reverse
及 q_reverseK
commit a30283b
避免濫用詞彙,此「核心」非彼「核心」(還記得課名嗎?),可改說「二者實作手法相似,唯 ___ 不同」
這兩個實作核心概念差不多,都是利用到巨集裡的 list_move
,利用一個指標定在第一個值上(最後會變成最後一個值),把它後面的都移到head/start後面即可達成反轉的效果
這兩個實作手法也是大同小異,只差在裡面的判斷是 >=
或是 <=
,這邊利用一個變數 result
來儲存佇列沒有被變動幾次,最後直接回傳即可(不需要在呼叫 q_size
)
commit 32571b7
將中心的實作內容拉出來成一個函式,呼叫時再把要遞增或是遞減傳入,減少兩個函式重複的程式碼
commit f7a6c27
這邊的實作是利用 merge sort 的方式去進行,一開始先利用快慢指標的方式去找到中點,找到中點後切一刀來分成左半邊及右半邊,在利用 merge
函式來完成合併的動作。
用 list_move
來串接節點,當有一邊串列為空且另一邊不為空時,再把不為空的串列接回 current
後方。
避免非必要的項目縮排 (即 *
和 -
),以清晰、明確,且流暢的漢語書寫。
commit 23062f2
不理解就說不理解,不要說「不太理解」,理工人說話要精準。
你若有疑慮,就嘗試提交修改,從而確認對整個專案的衝擊。
不太了解 descend
參數的用意,因為已經拿到 k 個 sorted 的佇列了,合併時還有需要管是不是 descend
嗎?還是說有可能給的 sorted 佇列跟 descend
兩邊是不一樣的排序方式
先將所有的內佇列串起來,再執行 q_sort
來進行排序。
避免非必要的項目縮排 (即 *
和 -
),以清晰、明確,且流暢的漢語書寫。
commit 6d8e3db
詳見作業說明。
了解!
目前分數還是卡在 95/100 ,因 q_insert_head
及 q_insert_tail
,有機會變成 ERROR: Probably not constant time
在原先的 lab0-c
中,percentile 被拔掉了,於是先研讀論文看 percentile
會對測量造成什影響,發現到
commit 4f98446
分數紀錄
commit 6d3cad3
無論標題和內文中,中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
作者開發了一套工具 dudect ,使其可以檢驗程式是否是常數時間複雜度。
fix-vs-random
來做測試。其中,第一種類別是常數,第二種則為隨機選取positively skew
),示意圖如下Welch's t-test.
來檢驗平均值的等價性Kolmogorov-Smirnov
等方式來測試Welch's t-test
與 Welford's
的變異數去改善數值的穩定性是一種機率分佈的類型,與常態分佈相似,常應用在估計樣本少或是不知道變異數的情況下
degree of freedom(df)
所控制指出論文和程式碼實作出入之處。
list_sort.c
及 list_sort.h
#include
,以及 list_sort.h
的內容list_sort.o
加入至 MakeFile
的 OBJS
中qtest.c
中,新增 do_sort_list
的函式以及指令commit d16586c
為防止只使用一次比較可能會有不公平的情形發生,我採用每個大小個測3次來取其平均。
使用 Metric prefix,而非漢語的「萬」。
資料數 | round 1 | round 2 | round 3 | 平均 |
---|---|---|---|---|
0.067 | 0.067 | 0.068 | 0.0673 | |
0.151 | 0.143 | 0.149 | 0.1476 | |
0.239 | 0.233 | 0.240 | 0.2373 | |
0.331 | 0.334 | 0.334 | 0.333 | |
0.425 | 0.432 | 0.428 | 0.4283 |
資料數 | round 1 | round 2 | round 3 | 平均 |
---|---|---|---|---|
0.059 | 0.061 | 0.063 | 0.061 | |
0.136 | 0.127 | 0.130 | 0.131 | |
0.219 | 0.207 | 0.223 | 0.2163 | |
0.297 | 0.296 | 0.311 | 0.3013 | |
0.385 | 0.382 | 0.384 | 0.3836 |
可以發現資料數量 100000 ~ 500000 時間差從 0.0063 -> 0.0447
提供更多解讀,闡述你的啟發。
shuffle
此函式用於打亂串列的順序
利用 Fisher-Yates shuffle 演算法來實作
流程如下:
size
0
~ size - 1
的節點與 last
作交換size
數減 1
,並將 last
更新為 current
的前一位size
== 1
時,即完成亂序圖示(為了圖片簡潔,這邊不畫最後一個節點連到 head
的線):
Round 1:
Round 2:
size
== 1
, 函式結束
採用 python script 來對此隨機函式作測試,總共執行 1000000
次
統計如下:
順序 | 觀察到的頻率 | 期待的頻率 | |
---|---|---|---|
123 | 166653 | 166666 | 0.00101 |
132 | 166775 | 166666 | 0.07128 |
213 | 167066 | 166666 | 0.96000 |
231 | 166651 | 166666 | 0.00135 |
312 | 166440 | 166666 | 0.30645 |
321 | 166415 | 166666 | 0.37800 |
Total | 0.71812 |
亂序 1234
的如圖所示