contributed by < Jimmy01240397
>
jujuegg
工程人員說話要明確,避免說「感覺」
與其談「心法」,不如設想「如果我是你」,我會怎麼做,示範一次給同學看,而且檢討自己哪裡沒做好,從而呼應原本學員的不足處。
軟體工程師要學會說故事,本作業要求學員從良性詳盡的批評開始。繼續檢討!
python labtest.py config.yml labtest.png
實作建立一個空的佇列,建立一個 list_head
用來連結佇列的第一個節點以及最後一個節點。
避免過多的中英文混用,已有明確翻譯詞彙者,例如「鏈結串列」(linked list) 和「佇列」(queue),就使用該中文詞彙,英文則留給變數名稱、人名,或者缺乏通用翻譯詞彙的場景。
已修
實作佇列的釋放,當佇列被釋放,裡面的所有節點理應被釋放,如果佇列為空的 for 便不會執行,直接釋放佇列本身。
建立一個新節點並且加入到鏈結串列的頭部或尾部。
考慮到堆疊釋放的情況,因此要對字串做複製。
考慮到兩者有高度相似,可運用巨集來代替減少重複程式。
從鏈結串列的頭部或尾部移除一個節點。
同理,可以運用巨集來代替減少重複程式。
實作時也產生一個疑問是為甚麼 list_del
的無效記憶體位址一定要是 0x00100100 與 0x00200200 而不是其他數字如:0x00100101、0x00200202、0x0 之類的。
這問題很好,你可參見 Linux 核心原始程式的 git log 來解讀。
實作計算佇列的長度。
由於計算需要迭代計算,如果一次走兩步或許可以加快運行的速度。
所以真的有比較快嗎? 真心發問
雖然迴圈次數減少一半,但是實際上指標還是前進了整個佇列,條件也相對變多,請問真的會比較快嗎?
jujuegg
不要書寫「真心發問」,詳盡提出你的疑慮和佐證,這樣才能有效溝通。
真誠地分享你的專業知識,讓溝通能夠達到共鳴,才是真正展現禮貌的方式。
測資產生器
「產生器」不是精準的詞彙,因為你應當有明確的測試計畫,並從數學分析 (或已有的論述) 證實該計畫可行,接著才用程式碼去產生對應的資料輸入。否則,你只是「憑感覺」做事,根本不能算是「工程」。
設定檔
結果:
結論:在 size 高的情況兩步兩步算真的比較快一點點
需要更多的解讀,從電腦科學的基礎學科的角度去陳述,避免說「真的比較快一點點」。
參考「你所不知道的 C 語言: linked list 和非連續記憶體」,使用快慢指標並且由於使用環狀鏈結串列因此終止判斷會以 = head
為標準。
q_delete_dup
由於 github action 上的 ubuntu 以及我自己的 debian 版本所使用的 glibc 版本皆低於 2.38,而 2.38 後的 strcmp 有做優化,在這之前的 strcmp 都是一個字元做比較,效能不佳。
某些濫用「優化」的語境,根本與「改良」和「改善」無異,那為何不直接講「改良」和「改善」呢?
\(\to\) 資訊科技詞彙翻譯
因此這邊將優化後的 strcmp 做移植,作為 newstrcmp。
for 迴圈同時使用兩個節點,一次移動兩步,當其中有一個為 head 時停止。
一個一個的把 head->prev 移到 head->next 後面。
從頭迭代 k 次並把這個範圍的節點取出來另外存成一個鏈結串列以後做一次 q_reverse
再放回來原來的位置。
從後面往前迭代,當出現大於/小於前一個節點時,便刪除該節點。
參考 Linux 核心的鏈結串列排序 並且閱讀 lib/list_sort.c,這邊採用 Queue-Mergesort。
先寫一個巨集來處理合併兩個列表
sort 總共有兩個階段,第一個階段是將 list
移到 pending
並且對部分節點做合併,第二階段是將所有 pending 做合併。
第一階段的每個迴圈先做 count++
接著判斷是否做合併最後將原本的 pending
放到 list
上並且 list
成為新 pending
然後切到下一個 list
。當需要合併時,對 count
做 ffs
得到需要對哪兩個列表做合併,使用 mergelist
處理合併,最後更新 *ppending
。
第二階段時先對 head
做初始化,並且使用 mergelist
對 head
與目前的 pending
做合併。
每兩個鏈結串列一組做合併,遇到長度為 0 就跳過,持續到只有一條鏈結串列有東西為止。
當你選定合併排序,現有的測試案例要如何涵蓋合併排序的最差狀況呢?
與 dudect 原始程式搭配對照。
其中缺少 percentile
相關用來去除極端值的程式碼。將該功能寫入即可。
指出論文和實作的出入之處,尚有其他!