# 2024q1 Homework5 (assessment)
contributed by < [jeremy90307](https://github.com/jeremy90307) >
:::danger
使用指定格式書寫，注意細節！
:::
## 閱讀 [因為自動飲料機而延畢的那一年](https://blog.opasschang.com/the-story-of-auto-beverage-machine-1/)
:::danger
留意書名號的使用。
:::
當我看到最後時讓我非常感動，在看這之前還想說 Linux 核心跟這到底有什麼關係，原本只是為了寫心得而去看，卻越看越認真的看完了，故事內容沒有什麼華麗的詞彙或有趣的劇情，用單純認真的態度去紀錄自己的故事，到故事的結尾那段 **我要選擇全世界第三杯的紅茶 !** 真的是打動到我，我的人生從未為了什麼目標放手一搏，我在想或許是我太過膽小害怕於改變。
在課程的後續我更應該要為自己負責，每個作業都很多可以學習的東西，若是中間有問題要做的不應該是拖延，而是當下解決問題，對每個實驗都應該更全面去思考問題，訓練自己對細節的重視!
## 檢視前六周學習狀況
### 作業回顧
[M01: lab0](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-a)
> [共筆](https://hackmd.io/GU68poa6RBqvgaM5PZ6UlA)
初次認識 Linux 核心 API 相關實作，當初還算認真的作完 queue 部分，後續補上 dudect 的論文研讀及實作及 list_sort 實作及 shuffle 命令等，過程中參考過很多人的共筆，當在看看自己打的程式碼時總覺得自己是一坨大便，因此在 lab0 還需待改進。
[M02: quiz1+2](https://hackmd.io/@sysprog/BkmmEQCn6)
> [共筆](https://hackmd.io/GQ3oKwkZTQuPu47UR46PRQ)
這份作業現在看來完整度非常差，尤其在 Timsort 部分，當初沒搞懂Timsort 卻被我的拖延症拖到現在，目前就決定先改進它。
[M03: review](https://hackmd.io/@sysprog/linux2024-review)
將 `jimmy01240397` 的 code review 意見加入到我的專案中。
[M03: ttt](https://hackmd.io/@sysprog/linux2024-ttt)
> [共筆](https://hackmd.io/GU68poa6RBqvgaM5PZ6UlA)
目前僅將 `ttt` 原封不動的加入到 `lab0` 中，且能順利運行井字遊戲，後續定點數相關實作待完成。
[M04: quiz3+4](https://hackmd.io/@sysprog/HkatSCZCT)
> [共筆](https://hackmd.io/iFUiIM-BQKCgxtWdOi0Tfg)
這份作業讓我初次真正認識到 bitwise 的有趣之處，像是僅依靠位移操作就能達到幾乎等效除十的答案，做著做著幾天就過去了，雖然延伸問題還未完全做到。
XTree 中還是有些許不懂，但卻讓我更認識 rb tree、AVL Tree、B tree 的概念，像是其中透過左旋、右旋來平衡樹的方法。
### homework5 預期目標
由於對自身評估，將全部作業完整將花費到大量時間，因此先將以下兩個作業完成，後續有多餘時間在繼續精進。
1. 將 quiz1+2 中的 Timsort 部份完整
2. 完成 ttt 作業要求，至少要作到參照〈並行程式設計：排程器原理〉，引入若干 coroutine
> [lab0-ttt](https://hackmd.io/GU68poa6RBqvgaM5PZ6UlA?view#Tic-Tac-Toe)
## 檢視想投入之專案
> [2023 年期末專題](https://hackmd.io/@sysprog/linux2023-projects)
:::danger
依據你的付出，還沒辦法看出「實力」
:::
根據我現在<s>實力</s> ，我認為還沒法對專案做出什麼實質貢獻，但我希望可以從做專案的過程學習到 Linux 相關工作技能，希望以後可以進入到這個行業中，因此我希望老師能給我個方向在之後的期末專案，謝謝。
TODO: 〈並行程式設計：排程器原理〉
紀錄問題
一對一討論:
**Timsort 在 Merge sort 的基礎之上，做了什麼改進？**
回顧 `測驗 2`
Timsort 結合 Merge sort 和 Insertion Sort，改進的目的有以下:
1. 加速 merge 的過程
2. 減少合併次數
3. 在處理有部分已排序的資料下，有更好的表現
值得一提的是， Timsort 將資料由 run 所構成，這裡的 run 由部分已排列的資料所構成。
那 run 的長度該怎麼決定，定義一個 minrun (最小運行長度)，用以表示每個 run 的最小長度。有幾點需要我們考慮到:
- minrun 不宜太長，會造成花費更多時間在執行插入排序
- minrun 不宜太短，否則在進行 merge 時次數變多
- 理想情況下 run 的數量等於或者略小於 2 的冪，效率會最高
在 `find_run` 函式會尋找符合遞增順序的元素，並組成一個 run ，接著使用 `merge_collapse` 來讓 run 的數量保持平衡，且須滿足以下條件:
- 假設有三個 run 分別為 A、B、C
- A > B + C
- B > C
只要有一項不符合則將 B 與 A、C 中較小者進行合併。
:::info
合併分成兩種:
- 在這我們假設有 run A 及 run B
```
A : [3, 7, 11, 12, 13, 31, 45]
B : [21, 22, 24, 24, 29, 300, 400]
```
1. merge sort 從 A、 B 的開頭逐一比較來進行合併，稱為 `one-pair-at-a-time`
2. Timsort 的合併基於 merge sort 做出改進，首先將 A 與 B 中長度較短者放入一塊臨時記憶區 `temp` (這裡 A 為較短者)
```
A : []
B : [21, 22, 24, 24, 29, 300, 400]
temp : [3, 7, 11, 12, 13, 31, 45]
```
接著 B 的第一個元素 $B_0$ 會去找在 A 的何處 ($A_4$ 與 $A_5$ 之間)，並將 $A_0$ ~ $A_4$ 放回 A 數組中
```
A : [3, 7, 11, 12, 13]
B : [21, 22, 24, 24, 29, 300, 400]
temp : [31, 45]
```
接著將 temp[0] 比對 B ，介於 B[4] 與 B[5] 之間
```
A : [3, 7, 11, 12, 13, 21, 22, 24, 24, 29]
B : [300, 400]
temp : [31, 45]
```
以此類推
```
A : [3, 7, 11, 12, 13, 21, 22, 24, 24, 29, 31, 45]
B : [300, 400]
temp : []
```
==>
```
A : [3, 7, 11, 12, 13, 21, 22, 24, 24, 29, 31, 45, 300, 400]
B : []
temp : []
```
這種合併方法被稱為 Galloping mode 。
:::
優劣:
數組若為隨機資料序列，可能會比逐對合併來的更慢。
Timesort 基於 mergesort 做了那些改進?
- 改善比較次數
Timsort 會將已排序的子序列組成 run 並透過一些規則使 run 的數量保持平衡，從而讓合併時使用 Galloping mode 來減少比較次數。
- 改善記憶體開銷
相較 merge sort ，我們僅需將以排序的兩個 run 重疊部分進行合併。
舉例 [2, 4, 6, 7, 8, 11] 與 [9, 10, 11, 15, 17]，僅須對重疊部分合併(即 [8, 11] 與 [9, 10, 11])，在配置額外空間，僅需配置合併部分及數組數量較小的那一方，因此只須配置 2 個空間即可。
:::info
這裡配置的空間為
[2, 4, 6, 7] 及 [8, 9, 10, 11, 11, 15, 17] 最後僅需將兩數組街上即可完成排序
=> [2, 4, 6, 7, 8, 9, 10, 11, 11, 15, 17]
:::
- 降低 cache miss
Timsort 不必走訪每個序列才進行合併，而是一邊走訪，就一邊把序列的元素加進待合併的 runs 當中，在適當時機就合併。對記憶體來說這些元素因近期存過，所以還在記憶體的上層中，能有效減少 cache miss。
:::warning
看`測驗 2` 過程中
>在連續記憶體的情境，其合併的順序相對於非遞迴版對 cache 較友善，但對鏈結串列一類非連續性記憶體而言，進行分治（divide) 的過程中，意即決定要切在哪一個點決定左右子樹，要走訪目前遞迴呼叫對應到合併樹中內部節點，所有待排序的元素，對 cache 不友善。
這段我無法理解為何是什麼原因導致的對 cache 不友善。
:::
**如何用 bitwise 運算做到 integer div/mod 10？**
> show me the code!
```c
/* a / b or a % b, b = 10 */
void divmod10(int a, int *div, int *mod)
{
int q,r;
q = ((a >> 3) + (a >> 1) + a) << 3) >> 7;
r = a - (((q << 2) + q) << 1);
*div = q;
*mod = r;
}
```
a = 23
10111
q = 2
r = 3
**數學證明**
(a >> 3) 等於 $\dfrac{a}{8}$
(a >> 1) 等於 $\dfrac{a}{2}$
最後再將結果加上 a 得到
```c
q_approx = (a / 8) + (a / 2) + a = a * (1/8 + 1/2 + 1) = a * 1.625
```
然後這個值會左移 3 位（乘以 8）再右移 7 位（除以 128）：
```c
q = ((a * 1.625) * 8) / 128 = (a * 13) / 128 = a * 0.1015625
```
根據餘數定理 $r = f-g\times Q$
```c
r = a - (((q << 2) + q) << 1);
```
可以看作
```c
r = a - (10 * q);
```
即可求出餘數 r
**驗證**
假設 a = 591
近似商計算
```c
q_approx = ((591 >> 3) + (591 >> 1) + 591) = (73 + 295 + 591) = 959
q = (959 * 8) >> 7 = 59
```
近似餘數計算
```c
r = 591 - (((59 << 2) + 59) << 1) = 591 - 590 = 1
```
Sign in with Wallet
Connect another wallet