contributed by < Jackiempty
>
jimmy01240397
量化分析上述更動到底可省下多少次分支,工程人員說話要有證據。
jservImage Not Showing Possible ReasonsLearn 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
我在寫的過程中發生了一件事,那就是即便我已經做了 clang-format 的校正,以及單獨用 cppcheck 做了靜態測試,卻還是在提交 commit 時跳出了 Failed to pass static analysis
於是我和同學討論可能的原因並互相比對 cppcheck 的版本後,發現同學的是 2.7 版,而我的則是 2.11 版,且看見了 lab0 的 commit message: Fix cppcheck failed since after version 2.9
,猜測有可能又是 cppcheck 版本的問題後,在重新安裝 cppcheck 至 2.7 版,就沒有再發生了。
我將單純照著原始碼底下排列的順序做修改
q_new
先說我一開始的做法,由於我是在一知半解的情況下跌跌撞撞地開始寫這份作業,所以在我看到註解中對於這個函式的說明之後我當下馬上想到的作法如下:
command 的翻譯是「命令」,而非「指令」(instruction)
然後我就很不爭氣地去看了歷屆同學們 的實作方式看看我的想法有沒有問題,不出意外我馬上注意到INIT_LIST_HEAD(list_head)
這個函式的存在,並使用grep
指令 命令找到了這段:
列出你參照過的 GitHub 帳號名稱。
原來將頭尾的指標指向自身的功能居然是用另一個函式實作,於是我調整程式碼如下:
commit 6a92331
修改的有以下三點
sizeof()
裡面的資料型態加上宣告INIT_LIST_HEAD()
head
q_free
在一開始,我並不知道list_for_each_safe
的存在,所以差點自身從頭寫一個語法非常初級的 for 迴圈去逐一 free 整個佇列的記憶體
列出你參照過的 GitHub 帳號名稱。
好在我會參考古聖先賢 ,在得知的list_for_each_safe
的存在之後,便只需要處理兩種例外,剩下的都可以交由這個函式解決
說到兩種例外,這兩種例外分別是:
面對這兩種狀態,我使出了在 Linus 口中沒有品味的解決方法:if 判斷式
d3f63ac
在今年的測試中
列出你參照過的 GitHub 帳號名稱。
我觀摩 komark06 和 chiangkd 的兩種實作方式,由於在這個函式裡面後要 construct 出新的節點,所以有同學將建構節點的功能獨立出來寫成一個函式,並且可以在不同個需要建構節點的其他函式中重複使用;同時,也有同學為了整體架構的乾淨簡潔,選擇將建構節點的功能嵌入在每個獨立的函式裡面,雖然這樣會寫到重複的程式碼,卻能夠避免標頭檔函式組成的更動。而我個人也是偏好後者,所以會採取後者的做法。
最後,在實作的部分,我所參考的寫法是這個:
我先是將memcpy()
的功能以更白話 的方式寫了出來,希望能藉由不直接使用既有的函式來增加可閱讀性。
何謂「更白話」?與前後文的關聯在哪?
然而,上次的評論中老師說不要使用 memcpy()
來實作複製內容的功能,於是那位同學變將多個功能像是計算 len
還有手動 malloc
記憶體的空間以及複製值的功能全部整合進 strdup()
,而既然 strdup()
是同個專案裡面的函式,並且還將那麼多功能都整合進去了,沒有不用的理由,所以我後來也選擇使用 strdup()
來使程式碼更精練。
在一開始我選擇直接從 q_insert_head()
複製整段的程式碼過來只修改最後一行:
然後我就在 chiangkd底下的老師評論中看見老師的提醒,所以變使用了同樣的手法,既然功能都和q_insert_head()
雷同,何不直接使用它來完成這個函式。當然,要能夠區別這兩者的差別,就得要修改函式所使用的引數。
關於這點,由於這個專案所使用的linked list
是以頭尾相連的方式實作的,所以技術上我只要調換q_insert_head()
的引數,將其換成 head->prev
就可以巧妙地讓本該完成在佇列頭部的工作套用在尾部上。
像這樣
明確列出參考的 GitHub 帳號名稱
另外,我發現我所參考的對象 他在使用q_insert_head()
之前保留了if (!head){return false;}
,但其實這個功能在q_insert_head()
裡面就有了,只要head
是壞掉的,不用在外面先排除,到內部函式裡面照樣會回傳我們本要回傳的false
,所以我就不多此一舉了。
q_remove_head
不理解就說不理解,不要不懂裝懂,沒有「不太懂」這回事。
關於這題,我很慚愧地說在沒有參考來源的情況下,我沒有頭緒,我不太理解 為什麼這個函式的參數裡面會有 bufsize
,在將節點從佇列移出的過程中,我不理解為什麼會需要一個 buffer,自然就不了解 bufsize
的功能為何。
所以我看了一下 chiangkd的程式碼:
從他的程式碼中,我看出幾件事情
value
的bufsize
是該節點的value
的尺寸bufsize
會在使用q_remove_head
的另外一個函式中先算好再傳進去第三點是因為看見qtest.c
中的string_length
,是使用者可以自訂的,不然就是在queue.c
裡面預設為max_buffer_size
無論標題和內文中,中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)。
留意各式細節,唯有重視小處並步步為營,方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心。
同q_remove_head()
,唯獨將原本傳入值為head
的部分改成跟tail
有關:
另外,我發現就算將 sp 的判斷移到上面的 if 條件式也過得了測資,雖然在標頭檔裡面只有註明說如果 sp 非 NULL 的情況下就將要被移除的節點值給放進去,但我不確定的是這段程式的初衷有沒有包含如果 sp 是 NULL 的情況下需不需要報錯。
由於測試資料沒有 sp 是 NULL 的情況讓我驗證,所以我只能以我的理解去實作這部分的判斷,最後我決定維持讓 sp 是 NULL 的情況下不回傳 NULL,並讓它正常移除節點,雖然我覺得移到上面比較好看。
如果 sp 的判斷式上移(e.g., q_remove_tail
):
我參考了兩種實作方式,分別為:
而我選擇了後者:
列出你的考量因素,你如何做這樣的決策?你的洞見又在哪?
這個函式我參考 komark06 並針對他所得到的建議進行了調整,拿掉strcmp
並用strlen
和memcmp
取代,目前看起來功能是沒有損失的。
原本也是想要自己宣告一堆 local variables 硬幹,但參考 chiangkd 後發現 list API 很好用,所以就照用了。
參考 chiangkd 的方法,非常直觀簡潔
參考 chiangkd 使用內建的list_cut_position()
和list_splice_init()
來實作,我覺得很聰明。
工程人員說話要精準,當你發現好的做法,要說出其好在哪?是否有副作用 (side effect) 呢?你是否可做更好?
參考 chiangkd 並改進程式碼外觀,並且加上當初沒有的 descend
參數來決定排序的升降。
這邊也是直接參考 chiangkd 的實作方式。有趣的是,由於這次多了 ascend 的功能,於是我是將其 descend 的功能中的所有 prev
和 next
對調達成了 ascend 的功能,並且是確定可以執行的。
接著來到q_descend
的部分,這部分我原本以為可以像reversek
那邊一樣在裡面使用ascend
之後再反轉就可以達到descend
的效果。然而,經過一番嘗試之後,我發現了以下問題:
grep 'ascend' ./traces/
命令找不到東西可知測資中沒有測試到 ascend 功能由以上發現可以推論幾件事情:
reverse
來達到用一個函式實作另一個函式的功能,因為會刪到相反邊的節點make test
運用上次實作好的 sort
來實作這次的merge
,並搭配在 qtest 裡的呼叫方式做前後處理。
到目前為止,make test 已經可以達到 95/100 了,剩下的第 17 個測試要去修改 dutect 才能通過,在此先跳過。接著,我用 Valgrind 去做動態測試,看有沒有雖然功能有通過測試但卻存在著邏輯和記憶體管理漏洞的地方,而就在我測到第 14 和 16 時出現了以下訊息:
這很奇怪,照理來說同一個功能都已經通過其他測資的 valgrind 測試了,沒道理到這邊會突然壞掉。
讓我們先來看看測試的內容為何:
由於壞掉的斷點是發生在new
完之後的ih dolphin 1000000
,隨後便跳出許多 memory leak 的錯誤訊息。看到一百萬這個數字和Time limit exceeded
的錯誤訊息,我不由得地想到會不會是執行一百萬次導致時間太長被系統認定為 runtime error,所以我就將測資修改了一下,將原本的一百萬一口氣降到一萬,隨後再執行一次 valgrind 測試,而這次就有通過。
看來我的推測沒有錯,於是我便開始來回測試他大概要多少的資料才不會觸發 runtime error,而我最後測出來的數據為:
這離測資所要求的 1000000 還有一段距離,我不確定這是有意的還是測試以外的內容,因為如果這是有意的話我勢必得要去修改上述幾個函式使其效率提升才能通過 runtime pass,若這並不在原本測試的範圍的話,實際上 make test 是有辦法通過的,所以 valgrind 的測試問題可以忽略,而我決定相信後者,畢竟 valgrind 只是一個除錯工具而已,並不是一個我們要通過的測試。
95/100
時間複雜度無法通過,應研究 論文 後改進 dudect 。
評分 95/100。
雖然說作業要求只要我們修改queue.[ch]
,但要解決第 17 筆測試要去修改dudect
的檔案內容,並搭配研讀論文〈Dude, is my code constant time?〉,引用論文內容改進程式碼,使其通過第 17 筆測試案例。
明確列出你參照的 GitHub 帳號名稱。
在讀了一些同學的筆記 之後,我瞭解了幾件事情:
我直接找出了兩者程式碼的相同處,並把 lab0 缺失的部分補足,並順利通過 make test
shuffle
在這個部分要做兩件事情:
透過觀察其它的 command 實作方式我們可以發現 qtest 裡面的 command 主要是由幾個要素所組成:
console init
裡面的ADD_COMMAND
do_##cmd
來展該函式名稱並辨識qtest.c
裡面的函式第二點可以由位於console.h
的巨集得知:
後續的do_shuffle
是參考了 chiangkd 的 handler
由於queue.h
是無法編輯的,所以無法像其他的函式一樣先在queue.h
定義完之後再實作在queue.c
,於是就要作在qtest.c
裡面
最一開始的實作方式是想實作作業說明裡所解釋的方法,也就是 Fisher–Yates shuffle 裡面的 Modern method,但嘗試了幾次之後都是失敗的,結果要不是會記憶體操作錯誤不然就是 shuffle 出來的結果並沒有徹底打亂,會有固定位置的字元不會被操作到,以下分享兩個失敗的例子:
何謂「連結佇列」?工程人員說話要精準。
用字要精準,你仍未改好。
乍看下邏輯好像沒有什麼問題,但實際逐行將數字帶進去手算之後,發現由於連結串列 雙向鏈結串列的特性,在做被抽到的節點與尾部的節點交換的時候,我必須要用一個變數紀錄從後面開始往前走訪的尾部節點,而這個變數會在該迴圈時前後連結的節點資訊被紀錄之後就繼續往下一個節點前進
改進你的漢語表達。
問題就是出在這裡,由於被它在進行交換前所紀錄的節點有可能是該次迴圈被抽到要去跟尾部交換的節點,所以這個要走訪尾部節點的變數就會錯誤地指向被交換到的最尾端的位置,而不是應該所要在的還沒被交換過的尾部位置,進而導致錯誤
解決的方法也很簡單,在 Fisher–Yates shuffle 裡面除了有 Modern method 以外也有一個方法叫 Pencil-and-paper method,而這個方法就對 List API 非常地友善,完全可以利用現成的函式就可以完成這個方法所需要的操作,實作的方法如下: