簡介

• 國立成功大學 資訊工程學系 113 級 (2020 ~ 2024)
• Github: randyuncle
• HackMD: rkhuncle

2024 Linux 核心設計/實作 春季班 自我評量

成果發表和貢獻

• [ksort]: commit 4fffe83
  • 針對專案中的錯字提出修正。

評分：3 分。

作業/隨堂測驗:

• lab0-c: Github / hackmd
• Homework2: hackmd
• assesment: hackmd

在這些作業中，我有了以下的收穫：

1. 熟練 git 操作（使用 git blame、git log 追蹤程式碼的歷史，以及使用 git rebase 等 git 操作）。

2. 查閱第一手資料，而非網路上別人所整理資料。

3. 撰寫測試程式，以測試指定程式的效能議題。

4. 使用效能評比工具，測量程式的效能。

5. 研讀 Linux lib/list_sort.c 的程式及參考論文，初步知道不同實作方法的合併排序演算法，有不同的分析結果。

6. 從閱讀 cpython 中的 listsort.txt，知道測試排序程式需要考量到不同的資料分佈，以及原作者設計 Timsort 的細節。

評分：6 分。

期末專題:

• 針對鏈結串列的資料排序改進: Github / hackmd

我在專題中提出在節點數較少的鏈接串列中實作 binary insertion sort 還是 linear insertion sort 究竟誰比較好的疑問，以及不同論文中對於 Timsort 的 merge_collapse 策略提出的改進方案做整理和實作，並於最後將它們於自製的 Linux 核心測試模組中做實驗，並歸納實驗的結果。在其中，有嘗試整理 Timsort 複雜度的證明，以及 xoroshiro128+ 亂數產生器和 Linux 亂數產生器的比較，不過最後沒能完成感到有些遺憾，因此我給自己 8 分。

評分：8 分。

與授課教師的互動:

• 5/1 下午 4:00 – 4:30 一對一討論
  • Linux 核心為何使用 circular doubly-linked list、確認期末專題的題目、討論 CS:APP 第二章中提及的 C 語言整數型態的議題。

評分：5 分。

所見所聞所感

回顧自己在這堂課的表現，雖然說起初會選修本課程，有很大一部份的原因是想要了解如何貢獻如 Linux 核心規模的開源專案，但是在修習這堂課的過程，我感受到我最大的進步不是開始做出貢獻，而是自己對於基本功的掌握（lab0-c 作業中使用測試工具驗證程式的問題、製作測試程式、git 操作的使用，和 assessment 作業的 CS:APP 第二章的閱讀筆記了解 C 語言的整數型態）、以及不要害怕失敗（期末專題的撰寫及實驗設計）。在〈因為自動飲料機而延畢的那一年〉的文章中，有幾句話說：「你最大的問題就是你太害怕失敗了」、「你該學習的不是看到事情就要完蛋了就去避免失敗，而是更應該學習如何處理及承受失敗，你才能變得比以前強大」。現在回想，我以前確實會因為害怕程式運作失敗會導致的各種問題，所以常常實作都會拖來拖去。但是，在這課程中，我在 Homework2 作業中開始在 lab0-c 環境嘗試改進課程中現有的 Timsort 程式碼，於其中增加 Tim Peter 原先在 cpython 實作中的合併排序改進手段（實作 galloping mode、run 填入策略），到後續期末專題中，對 Timsort 中的 binary insertion sort 是否合適在鏈結串列中提出實驗及討論、實作針對鏈結串列資料排序的核心測試模組並 debug 其對裝置所造成的死機問題、閱讀和整理多方對於 Timsort 的理論討論和實作他人對於 merge_collapse 架構的改進策略、以及後續嘗試在期末專題整理他人所做的 Timsort 複雜度證明及其證明基礎（succinct data structure、compressing permutations 對於 adaptive sorting 影響的整理）。當然，還有我對於本課程的專案 ksort 提出人生中的第一次 pull request。這也讓我知道，不害怕失敗，我也能做出不俗的成果。

不過，在閱讀〈因為自動飲料機而延畢的那一年〉的過程中，除了以上對於不要害怕失敗的體悟中，也有一個人無法懂所有知識。這體現在期末專題之中。我在上段有寫到，我嘗試整理其他研究者對於 Timsort 的複雜度的證明，會做這部的原因是方便自己或後續其他人，如果想要提交對 Linux lib/list_sort.c 的 Timsort 改進的 pull request，有一個可以參考的證明方向。但是，只是描述 Timsort 的複雜度，卻可以牽涉到非常多資訊領域的知識，例如說資訊理論的 succint data structure、sequence 資料壓縮議題、permutations 對排序演算法的理論含意等，這些很大部份我過去的學習中都沒接觸到，而需要大量時間去探究和閱讀相關的經典論文和書籍。我沒辦法在兼顧測試程式及 Timsort 完整策略的程式撰寫，和了解其他課程作業的情況下，而全面探討所有該證明會牽涉到的相關知識。所以，我先將測試程式撰寫完成，對其他研究者於 Timsort 的 merge_collapse 改進的研究先做了解，並配合鏈結串列中的 binary insertion sort 議題一同實驗，再回頭嘗試懂那些知識。

總體而言，我認為我在這門的投入，以及目前的學習成果，自評 8 分。

評分：8 分。

自我評量 (1 ~ 10)

幾何平均數：\(GEOMEAN = (3 \times 6 \times 8 \times 5 \times 8)^{1/5} = 5.65...\)

方案 B：\(1 + floor(GEOMEAN) = 6\)