## 2024q1 Homework5 (assessment)
contributed by < `Leo5307` >

### 紀錄閱讀〈因為自動飲料機而延畢的那一年〉的啟發
**和課程有關的佳句與洞見：**
1. > 一項產業進步的速度，很大程度取決於做實驗修正問題的速度。

這讓我回想起我們在實驗室組裝機器人時，常常需要耗費大量時間等待零件加工完成。相較之下，軟體問題的發現與解決通常能更迅速地進行，這一差異或許正揭示了不同產業技術進步的步伐不一致的根本原因。

2. > 要是現在就放棄的話，你這輩子日後遇到這種等級的困難，就只會想逃避而已。

對這句話深有感觸，在學習上做選擇時我經常不計後果地挑簡單的做，最後的結果就是變成對什麼事情都有一些了解但同時又都不精通，我想就是因為在學各學科較困難的部分時都直接放棄，抱著能夠應付考試就好心態的緣故吧。反觀在這堂課時因為有在持續學習、始終不放棄的緣故，逐漸紓解了一開始的逃避心理，但因為欠下的技術債實在太多，只能**哪裡不夠就補哪裡**將其慢慢補足。

3. > 「這個問題的 constraint 太多了,冰塊大小不能調整、又要穩定、又要保溫，你根本解不掉。」Jserv 頓了頓：「但我相信這個問題絕對不會沒有人碰過，一定有人解決過，所以你不該卡在這裡，因為這件事卡在這裡是相當不值得的。市面上應該有專門做冰塊分配的機器，雖然很貴，但是這是最快的作法，這樣你才能夠繼續下去。而且機器買來也不是立刻沒價值，必要時你還可以看看能不能用二手價賣回去。」

讓我聯想到有時必須適當的捨去一些規格或要求，才有辦法讓事情明朗化。有時候在開發一個程式時，會因為想要什麼都一次做到好，反而自縛其手，沒辦法推進進度。或許應該適當的把規格捨棄或拆開，先專注於特定的規格，才能讓整個開發能夠順利進行。

4. > 創業就是在一連串情況不明朗的情況下做決定，而且金錢有限、時間更貴，你必須很清楚自己要什麼、不要什麼。

和考試有所謂的標準答案不同，長大後我也逐漸體悟到生活也是如此。很多時候都要急著做決定，但往往我都對當時的情況相當不理解，更不知道什麼才是好的，只能一直不停的修正，希望讓事情越來越好。我相信寫程式、建立系統也會是同樣的道理。

5. > 「你最大的問題在太害怕失敗了，既然都已經決定要延畢做飲料機了，那就要好好做，才不會辜負當初自己的期望。你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大。

決定好了就要好好做，才不會辜負當初自己的期望。
[**其他佳句**](https://hackmd.io/@Leo0123/Hk-H9cP-C)

## 從前 4 週的測驗題選出 3 題改進
1. [對第一週測驗題的原理解釋與改進](https://hackmd.io/-mSlxVt5S0edf-2F1TH1yA)

## 參照 2023 年期末專題，簡述你想投入的專案 (亦可建立新專案)，至少選出 (或訂出) 二個。

由於我的實驗室主要是研究將算法類（深度學習、強化學習、啟發式算法）與機器人做結合，因此這堂課的期末專題首選也是和以上研究方向有所相關的。（這其中有想過嘗試學習 ROS 系統並為 ROS 系統作出貢獻，但因為能力還很菜，因此還不能很好的覺察出有哪些地方能夠改進）

**依照有興趣程度排序：**
1. **實現並改善 2024 年 Linux 核心實作的井字遊戲作業。**
實作並改進**井字遊戲作業**，改進/增加更多可跟電腦對弈的演算法（算法/人工智慧），彙整其他學員的成果，連同延伸問題。

2. **並行程式設計**
參照 2023年 的方式，回顧〈並行和多執行緒程式設計〉教材和相關測驗題，強化對延伸問題的掌握。

3. **紅黑樹 / XTree 實作改進**

**二選一**：
- 依照**2023年紅黑樹實作改進**的方式，重做 2023 年第 3 週測驗題 的測驗一及第 4 週測驗題的測驗一，彙整其他學員的成果，連同延伸問題
- 重做並改進 2024 年第 4 周測驗 3 的 XTree ，將其與紅黑樹、 AVL 樹進行比較，彙整其他學員的成果，連同延伸問題

4. **Linux 排程器研究**
參照 **2023 年 <Linux 排程器研究>** 的形式,探討 Linux 排程器內部設計，改進《Demystifying the Linux CPU Scheduler》，並尋求貢獻程式碼到 Linux 核心的機會

---

除此之外Timsort還採用多種方式來避免佔用太多記憶體
詳見:
- [2024q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)
- [最貼近現實的排序演算法- Timsort](https://jason18153.medium.com/%E6%9C%80%E8%B2%BC%E8%BF%91%E7%8F%BE%E5%AF%A6%E7%9A%84%E6%8E%92%E5%BA%8F%E6%BC%94%E7%AE%97%E6%B3%95-timsort-a75da75b65a2)
Timsort中的合併可分為兩種：
1. one pair at a time(即是合併排序所采用的模式)
2. Galloping mode
- 假設A,B兩個 run ，且A run比 B run 短
- 尋找A[0] 在 B中哪個位置的後面，假設是B[k]
- 把B[0]~B[k]放到輸出的序列
- 尋找B[0]在A中哪個位置的後面，假設是A[j]
- 把A[0]~A[j]放入輸出的序列
- 循環以上步驟直到完全合併
- Galloping mode 只有在序列具有部分排序時才會有優勢，因此 Tim 規定只有當兩個序列比較到第七次（`min_gallop = 7`）都是由同一個序列取值時，才啟動 Galloping mode
- 因此如是隨機序列，則永遠也不會觸發 Galloping mode
#### Timsort 程式碼運作原理
1. 以下程式碼需組合起來看:

static inline size_t run_size(struct list_head *head)
{
    if (!head)
        return 0;
    if (!head->next)
        return 1;
    return (size_t) (head->next->prev);
}

// 截取自 find_run
head->next->prev = (struct list_head *) len;

算法透過將每個 run 的長度```len```強制轉型後儲存在```head->next->prev```，來儲存每個 run 的長度
::: warning
但我不確定說這樣強製轉型是否在維護程式碼上是一個好的做法
:::
這段程式碼負責找尋順序/逆序的序列，但和我所了解的Timsort不同，在這裡並沒有考慮把每個run都補成一樣最小長度

TODO: 重新發問，附上實驗、規格書描述、推測

IEEE 754; Assume float is 32-bit width

float float_div2(float x)
{
    // using bitwise, no mul/div
    
}

TODO: 實作程式碼並驗證，整理在 HackMD 筆記，貼到課程討論區，誠實面對自己！
TODO: 除 2 之後的浮點數，是否仍有效？ (x 在什麼數值，會因除 2 而導致非有效的 float)

TODO: 第 4 周測驗 3 的 XTree ，將其與紅黑樹、 AVL 樹進行比較: 量化分析 (演算法分析: tree height, 數學！)，提出 XTree 的改進方案